论文标题
用于过度张量分解的可靠光谱算法
A Robust Spectral Algorithm for Overcomplete Tensor Decomposition
论文作者
论文摘要
我们给出一种用于分解过度订单4张量的频谱算法，只要它们的组件满足代数的非降级条件，几乎所有（除了一组代数$ 0 $ $ 0 $）张量（\ mathbb {rathbb {r} r}^d）^d）^d）我们的算法对有界光谱规范的对抗扰动是可靠的。 我们的算法的灵感来自该算法的灵感，该算法使用了SemideSemingSminite编程层次结构（MA，Shi和Steurer Stoc'16，Arxiv：1610.01980），我们实现了可比的鲁棒性，并在类似的代数假设下实现了可比的鲁棒性。但是，我们的算法避免了半决赛编程，并且可以作为一系列基本的线性代数操作实现。因此，我们获得的运行时间比半决赛编程方法要快得多：我们的算法在时间上运行$ \ tilde o（n^2d^3）\ le \ tilde o（d^7）$，这是输入尺寸$ d^4 $（我们已经抑制了与输入数量的条件编号相关的输入尺寸$ d^4 $）。
We give a spectral algorithm for decomposing overcomplete order-4 tensors, so long as their components satisfy an algebraic non-degeneracy condition that holds for nearly all (all but an algebraic set of measure $0$) tensors over $(\mathbb{R}^d)^{\otimes 4}$ with rank $n \le d^2$. Our algorithm is robust to adversarial perturbations of bounded spectral norm. Our algorithm is inspired by one which uses the sum-of-squares semidefinite programming hierarchy (Ma, Shi, and Steurer STOC'16, arXiv:1610.01980), and we achieve comparable robustness and overcompleteness guarantees under similar algebraic assumptions. However, our algorithm avoids semidefinite programming and may be implemented as a series of basic linear-algebraic operations. We consequently obtain a much faster running time than semidefinite programming methods: our algorithm runs in time $\tilde O(n^2d^3) \le \tilde O(d^7)$, which is subquadratic in the input size $d^4$ (where we have suppressed factors related to the condition number of the input tensor).
