Complete Decomposition of Symmetric Tensors in Linear Time and Polylogarithmic Precision

We study symmetric tensor decompositions, i.e. decompositions of the input symmetric tensor T of order 3 as sum of r 3rd-order tensor powers of ui where ui are vectors in Cn. In order to obtain efficient decomposition algorithms, it is necessary to require additional properties from the ui. In this paper we assume that the ui are linearly independent. This implies that r is at most n, i.e., the decomposition of T is undercomplete. We will moreover assume that r=n (we plan to extend this work to the case where r is strictly less than n in a forthcoming paper). We give a randomized algorithm for the following problem: given T, an accuracy parameter epsilon, and an upper bound B on the condition number of the tensor, output vectors u'i such that ui and u'i differ by at most epsilon (in the l2 norm and up to permutation and multiplication by phases) with high probability. The main novel features of our algorithm are: (1) We provide the first algorithm for this problem that works in the computation model of finite arithmetic and requires only poly-logarithmic (in n, B and 1/epsilon) many bits of precision. (2) Moreover, this is also the first algorithm that runs in linear time in the size of the input tensor. It requires O(n3) arithmetic operations for all accuracy parameters epsilon = 1/poly(n).