Optimization over symmetric polynomials

Question

Consider the following constraint satisfaction problem: Let $\alpha_1 , \ldots, \alpha_k \in \mathbb{R}$ be given as well as an error parameter $\epsilon$. Find $p_1, \ldots, p_n$ such that

(i) $0 \le p_1, \ldots, p_n \le 1$

(ii) For $1\le j \le k$, $|(\sum_{i=1}^n p_i^j) - \alpha_j|\le \epsilon$.

Here $k \ll n$. I am interested in the time complexity of this problem: In particular, based on some symmetry considerations, one can show that it suffices to restrict one's search to the case where $p_1, \ldots, p_n$ all come from a set of size at most k. Based on this observation, one can consider all possible ways of partitioning $p_1, \ldots, p_n$ into k sets (which takes time $n^k$) and subsequently solve a problem which requires one to solve polynomial equations over the reals (in k variables and of degree bounded by k). This takes time $k^k$. The dependence of n^k is prohibitive for me and I was wondering if there is a way to solve this in time $O(n^{O(1)} \cdot k^{k})$ or at least better than $n^k$.

Answer 1

The system has a very special structure, that prompts a different approach (classically known as Prony method): one can parametrise the $p_i$ as the roots of a polynomial $f(t)=\sum_{\ell=0}^n f_\ell t^\ell.$ Then for the case $\epsilon=0$ and $k\gg n$ one has that $(f_0,\dots,f_n)$ is in the kernel of the Hankel matrix $$ \begin{pmatrix}a_1&a_2&\dots &a_n\\ a_2& a_3&\dots &a_{n+1}\\ \dots\\ a_n& a_{n+1}&\dots & a_{2n-1} \end{pmatrix} $$ as you can multiply the (truncated) Vandermonde matrix depending on $p_i$ by $(f_0,\dots,f_n)^\top$ (and by the corresponding vectors of coefficients of $tf(t)$, $t^2 f(t)$, etc.) on the left, obtaining zeros, which should equal to the scalar product of $(f_0,\dots,f_n)^\top$ (and by the corresponding vectors of coefficients of $tf(t)$, $t^2 f(t)$, etc.) and $(a_1,a_2,\dots)$.

Perhaps this kind of parametrisation will give a much for efficient procedure.