Unique powers-of-forms decompositions from simple Gram spectrahedra

We consider simultaneous Waring decompositions: Given forms of degrees k*d, (d=2,3), which admit a representation as d-th power sums of k-forms, when is it possible to reconstruct the individual terms from the power sums? 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≤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→∞. Some evidence is given that the algorithm also succeeds on instances of rank quadratic in the dimension.

• View at Publisher

Free Full Text ( Final Version , 1mb )