Abstract

We give efficient algorithms for finding power-sum decomposition of an input polynomial P(x)=\sum_i p_i(x)^d with component p_is. The case of linear pis is equivalent to the well-studied tensor decomposition problem while the quadratic case occurs naturally in studying identifiability of non-spherical Gaussian mixtures from low-order moments. Unlike tensor decomposition, both the unique identifiability and algorithms for this problem are not well-understood. For the simplest setting of quadratic p_i and d=3, prior work of Ge, Huang and Kakade yields an algorithm only when m≤Õ(n‾√). On the other hand, the more general recent result of Garg, Kayal and Saha builds an algebraic approach to handle any m=nO(1) components but only when d is large enough (while yielding no bounds for d=3 or even d=100) and only handles an inverse exponential noise. Our results obtain a substantial quantitative improvement on both the prior works above even in the base case of d=3 and quadratic p_i. Specifically, our algorithm succeeds in decomposing a sum of m∼Õ(n) generic quadratic pis for d=3 and more generally the dth power-sum of m∼n^{2d/15} generic degree-K polynomials for any K≥2. Our algorithm relies only on basic numerical linear algebraic primitives, is exact (i.e., obtain arbitrarily tiny error up to numerical precision), and handles an inverse polynomial noise when the pis have random Gaussian coefficients.