Find Functions That Can Be Inverted from Their Sums

Question

I have the following situation:$$ f_1(x_1) + f_1(x_2) + f_1(x_3) + \cdots + f_1(x_n) = c_1\\ f_2(x_1) + f_2(x_2) + f_2(x_3) + \cdots + f_2(x_n) = c_2\\ \vdots\\ f_n(x_1) + f_n(x_2) + f_n(x_3) + \cdots + f_n(x_n) = c_n $$These formulae are evaluated at a particular vector $\vec{x}$, producing a vector $\vec{c}$ of constants. Now, given this vector $\vec{c}$, I want to reconstruct the original $\vec{x}$. What $f_i$s should I choose that will let me do this?

There are two constraints: $f_i$ is bounded on $(0,1)$ and $\left[f_i(x_j)=0\right] \rightarrow \left[x_j \in \{0,1\}\right]$ (and $f_i(x_j)$ is $0$ in at least one point).

There are, however, some simplifying assumptions. Each $x_i \in [0,1]$ and $\left[x_i=x_j\right] \rightarrow \left[\left[i=j\right] \vee \left[f_k(x_i)=f_k(x_j)=0\right]\right]$. Furthermore, the order of the components of $\vec{x}$ is irrelevant (that is, reconstructing any permutation of $\vec{x}$ is fine).

A closed-form solution is ideal, but a numerical solution scaling gracefully with $n$ is acceptable too. Partial solutions for $n \geq 4$ will be accepted if there is no general approach.

---

I have tried a number of things, but my best attempt so far is the rather basic:$$ f_i(x_j) := x_j^{i} $$So that we have:$$ f_1(x_j) := x_j^1\\ f_2(x_j) := x_j^2\\ \vdots\\ f_n(x_j) := x_j^n $$Viewed this way, each equation represents an $n$-dimensional superquadric. For $n=2$, a closed form exists (intersection of line with circle quadrant). For $n=3$, I used multidimensional Newton iteration. However, for $n=4$, the solver fails to converge (or at least has numerical issues).

---

The question again: What is a good choice of $f_i$ such that I can reconstruct $\vec{x}$ given $\vec{c}$?

Answer 1

The idea of setting $f_i(x)=x^i$ actually works quite well:

Observation 1: The $n$ sums $$c_i=\sum_{j=1}^n f_i(x_j)$$ with $1\leq i\leq n$ can be used to express all the elementary symmetric polynomials $$e_k(\vec{x})=\sum_{\substack{A\subseteq \{x_1,x_2,\ldots,x_n\} \\ |A|=k}}\prod_{x\in A}x$$ with $0\leq k\leq n$.

Observation 2: The polynomial $$P(X)=\prod_{i=1}^n (X-x_i)$$ can be expressed using these elementary symmetric polynomials as $$P(X)=\sum_{k=0}^n (-1)^k e_k(\vec{x}) X^{n-k}$$

Observation 3: The roots of polynomial $P(X)$ are precisely the numbers $x_i$. Since it is a polynomial of single variable, its roots can be obtained either explicitly (for $n\leq 4$) or one can use any of the numeric algorithms quite easily (especially if all of them are distinct).

A few small examples of observation 1 look as follows (borrowing the notation used for $c_k$ and omitting the vector $\vec{x}$ in $e_k(\vec{x})$). $$\begin{eqnarray} e_1 & = & c_1 \\ e_2 & = & \frac{1}{2}\left(c_1^2-c_2\right)\\ e_3 & = & \frac{1}{6}\left(c_1^3-3c_1c_2+2c_3\right) \\ e_4 & = & \frac{1}{24}\left(c_1^4-6c_2c_1^2+3c_2^2+8c_3c_1-6c_4\right)\\ \end{eqnarray}$$

It might look surprising at the first glance, but the expressions on the right-hand side really do not depend on the number of variables.