5
$\begingroup$

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}$?

$\endgroup$
  • $\begingroup$ It almost looks like you want a real-valued Fourier transform. (Except for the permutation bit.) $\endgroup$ – Brian Tung Apr 23 '15 at 17:26
  • $\begingroup$ What's the use of your <sup><sub> tags? On my computer, it has only the effect of making text so small that it's almost unreadable. $\endgroup$ – Han de Bruijn Apr 25 '15 at 19:31
  • $\begingroup$ I don't understand if the constrains and the "simplifying" assumptions make this problem either trivial or impossible. Your attempt opens some weird questions about what you can/cannot do. Let me explain. Can the following: $f_j(x_i) = x_i \delta_{ij}$, where $\delta_{ij}$ is Kronecker's delta, be used? Is it compatible with your constraints? Your answer will answer my (unwritten) questions. $\endgroup$ – PseudoRandom Apr 30 '15 at 10:14
  • $\begingroup$ @PseudoRandom The functions $f_j$ are not themselves functions of the values they are given. So, a (bounded) delta function is acceptable, but useless. $\endgroup$ – imallett Apr 30 '15 at 18:06
  • $\begingroup$ @imallett: I don't think I get your point: isn't the index considered part of the input? The $f_j(x_i)$ I choosed use both $x_i$ and the indices. Kronecker's delta is strictly bounded (in fact, it is either 1 or 0, $\delta_{ij}=1 \iff i=j$, 0 otherwise) and when $i=j$, the output of $f_j$ is $x_i$, otherwise it's 0. For example, $f_1(x_1) = x_1$, but any other index $k \neq 1$ makes $f_1(x_k) =0$. With this trick, you get the numerical values directly in the vector $\vec{c}$. It's everything based on indices, that's why I don't know if it is acceptable. $\endgroup$ – PseudoRandom May 2 '15 at 8:10
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ +1 for teaching me about elementary SP (and for being only responder).¶ So the idea is to compute $\vec{c}(\vec{x})$ using $f_i(x_j):=x_j^i$, then convert to ESP with some simple function $\vec{e}:=\vec{g}(\vec{c}(\vec{x}))$. Then we can calculate coefficients of $P(X):=\sum\cdots$. Then, since $P(X)$ also is $\prod (X-x_i)$, the roots of $P(X)$ (found numerically) are exactly $\vec{x}$. Right? If so, I think this is just a permutation of what I already tried. If it makes $P(X)$ better conditioned ($n\ge 4$), then it would be an acceptable partial solution. Could you show that? $\endgroup$ – imallett May 4 '15 at 19:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.