Polynomial-Time Power-Sum Decomposition of Polynomials - Efficient Algorithms and Applications

Explore polynomial-time power-sum decomposition of polynomials in this 51-minute conference talk by Jun-Ting (Tim) Hsieh at the Workshop on Tensors: Quantum Information, Complexity and Combinatorics. Delve into an efficient algorithm for finding power-sum decompositions of input polynomials, comparing it to tensor decomposition problems and non-spherical Gaussian mixture identifiability. Examine the algorithm's ability to handle a sum of generic quadratic polynomials and its improvements over previous work. Learn about the algorithm's reliance on basic numerical linear algebraic primitives, its exactness, and noise handling capabilities. Discover applications in tensor decomposition with symmetries, mixture of Gaussians, and graph matrices. Gain insights into span finding, singular value lower bounds, and the trace moment method throughout this comprehensive mathematical exploration.