论文标题
快速算法，用于超级订单-3张量分解
Fast algorithm for overcomplete order-3 tensor decomposition
论文作者
论文摘要
我们开发了第一个快速频谱算法，用于分解$ \ mathbb {r}^d $排名的随机三阶张量，最高为$ o（d^{3/2}/\ text {polylog}（d））$。我们的算法仅涉及简单的线性代数操作，并且可以在当前矩阵乘法时间下在时间$ o（d^{6.05}）$中恢复所有组件。 在这项工作之前，只能通过方形的总和[MA，Shi，Steurer 2016]实现可比的保证。相反，快速算法[Hopkins，Schramm，Shi，Steurer 2016]只能分解$ O的排名张量（d^{4/3}/\ text {polylog}（d））$。 我们的算法结果取决于两种关键成分。将三阶张量的清洁提升到六阶张量，可以用张量网络的语言表示。将张量网络仔细分解为一系列矩形矩阵乘法，这使我们能够快速实现该算法。
We develop the first fast spectral algorithm to decompose a random third-order tensor over $\mathbb{R}^d$ of rank up to $O(d^{3/2}/\text{polylog}(d))$. Our algorithm only involves simple linear algebra operations and can recover all components in time $O(d^{6.05})$ under the current matrix multiplication time. Prior to this work, comparable guarantees could only be achieved via sum-of-squares [Ma, Shi, Steurer 2016]. In contrast, fast algorithms [Hopkins, Schramm, Shi, Steurer 2016] could only decompose tensors of rank at most $O(d^{4/3}/\text{polylog}(d))$. Our algorithmic result rests on two key ingredients. A clean lifting of the third-order tensor to a sixth-order tensor, which can be expressed in the language of tensor networks. A careful decomposition of the tensor network into a sequence of rectangular matrix multiplications, which allows us to have a fast implementation of the algorithm.
