Unique powers-of-forms decompositions from simple Gram spectrahedra

Abstract

We consider simultaneous Waring decompositions: Given forms $f_d$ of degrees $kd$, $(d=2,3)$, which admit a representation as $d$-th power sums of $k$-forms $q_1,\dots ,q_m$, when is it possible to reconstruct the addends $q_1,\dots ,q_m$ from the power sums $f_d$? Such powers-of-forms decompositions model the moment problem for mixtures of centered Gaussians. The novel approach of this paper is to use semidefinite programming in order to perform a reduction to tensor decomposition. The proposed method works on typical parameter sets at least as long as $m\le n-1$, where $m$ is the rank of the decomposition and $n$ is the number of variables. While provably not tight, this analysis still gives the currently best known rank threshold for decomposing third order powers-of-forms, improving on previous work in both asymptotics and constant factors. Our algorithm can produce proofs of uniqueness for specific decompositions. A numerical study is conducted on Gaussian random trace-free quadratics, giving evidence that the success probability converges to $1$ in an average case setting, as long as $m=n$ and $n\to \infty$. Some evidence is given that the algorithm also succeeds on instances of rank $m=\Theta (n^2)$.

25 pages, 2 figures. Accompanying code may be found on GitHub