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$
12
  • $\begingroup$ It almost looks like you want a real-valued Fourier transform. (Except for the permutation bit.) $\endgroup$
    – Brian Tung
    Apr 23, 2015 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$ Apr 25, 2015 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$ Apr 30, 2015 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$
    – geometrian
    Apr 30, 2015 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$ May 2, 2015 at 8:10

1 Answer 1

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$
1
  • $\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$
    – geometrian
    May 4, 2015 at 19:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .