论文标题
在线性时间和聚类精度中完全分解对称量
Complete Decomposition of Symmetric Tensors in Linear Time and Polylogarithmic Precision
论文作者
论文摘要
我们研究对称张量分解，即3阶输入对称张量t的分解为u_i的r 3级张量幂的总和，其中u_i是\ c^n中的向量。为了获得有效的分解算法，必须需要U_I的其他属性。在本文中，我们假设U_I是线性独立的。这意味着r最多是n，即t的分解是底层的。此外，我们将假设r = n（我们计划将此工作扩展到严格少于即将发表的纸张的n的情况）。我们给出了以下问题的随机算法：给定t，准确性参数epsilon和张量的条件数上的上限b，输出向量u'_i u'_i使得u_i和u'_i在大多数epsilon上都有差异（在l_2 norm中，在l_2 norm中，并以较高的概率为单位和乘以乘以置换和乘法）。我们算法的主要新颖特征是：（1）我们为此问题提供了第一种算法，该算法在有限算术的计算模型中起作用，并且仅需要poly-logarithmic（在n，b和1/epsilon中）许多精度。 （2）此外，这也是第一个以线性时间在输入张量的线性时间内运行的算法。对于所有精度参数epsilon = 1/poly（n），它需要O（n^3）算术操作。
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 u_i where u_i are vectors in \C^n. In order to obtain efficient decomposition algorithms, it is necessary to require additional properties from the u_i. In this paper we assume that the u_i 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 u_i and u'_i differ by at most epsilon (in the l_2 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(n^3) arithmetic operations for all accuracy parameters epsilon = 1/poly(n).
