Decomposing Overcomplete 3rd Order Tensors using Sum-of-Squares Algorithms
Decomposing Overcomplete 3rd Order Tensors using Sum-of-Squares Algorithms
复制标题
使用平方和算法分解超完备三阶张量
DOI：
10.4230/lipics.approx-random.2015.829
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Tengyu Ma
中科院分区：
文献类型：
--
作者：
Rong Ge;Tengyu Ma
张量秩和低秩张量分解在学习和复杂性理论中有许多应用。大多数已知算法使用张量的展开，并且对于$\mathbb{R}^{n^p}$中的$p$阶张量，只能处理高达$n^{\lfloor p/2 \rfloor}$的秩。以前，当秩相对于维度是超线性时，没有有效的算法能够分解三阶张量。利用平方和层次结构的思想，我们给出了第一个拟多项式时间算法，当秩高达$n^{3/2} / \text{多对数}n$时，该算法能够分解随机三阶张量。
我们还给出了一个多项式时间算法，用于验证随机低秩张量的单射范数。我们的张量分解算法利用了单射范数和张量分量之间的关系。证明依赖于用于解耦随机变量的有趣工具，以证明更好的矩阵集中界，这在其他情形中可能是有用的。
Tensor rank and low-rank tensor decompositions have many applications in learning and complexity theory. Most known algorithms use unfoldings of tensors and can only handle rank up to $n^{\lfloor p/2 \rfloor}$ for a $p$-th order tensor in $\mathbb{R}^{n^p}$. Previously no efficient algorithm can decompose 3rd order tensors when the rank is super-linear in the dimension. Using ideas from sum-of-squares hierarchy, we give the first quasi-polynomial time algorithm that can decompose a random 3rd order tensor decomposition when the rank is as large as $n^{3/2}/\textrm{polylog} n$.
We also give a polynomial time algorithm for certifying the injective norm of random low rank tensors. Our tensor decomposition algorithm exploits the relationship between injective norm and the tensor components. The proof relies on interesting tools for decoupling random variables to prove better matrix concentration bounds, which can be useful in other settings.
影响因子：
2.5
作者：
Harrow, Aram W.;Montanaro, Ashley
通讯作者：
Montanaro, Ashley