Undercomplete Decomposition of Symmetric Tensors in Linear Time, and Smoothed Analysis of the Condition Number

Pascal Koiran, Subhayan Saha

We study symmetric tensor decompositions, i.e., decompositions of the form $T={\sum }_{i=1}^r{u}_i^{\otimes 3}$ where $T$ is a symmetric tensor of order 3 and $u_i\in {\mathbb{C}}^n$.…