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.

Intro
Why Study Power Sums?
Tensor Decomposition with Symmetries
Decomposing Generic Polynomials
Main Prior Works
Application: Mixture of Gaussians
GHK Approach
Algorithm Outline
Span Finding
Outline of Algorithm
Noise Resilience
Rest of the talk
Linear Dependencies of V
Singular Value Lower Bounds
Trace Moment Method
Example: Gaussian Matrix
Graph Matrices
Summary of the talk