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.

使用sum-of-squares层次结构的思想，我们提供了第一个几乎多项式时间复杂度的算法，可以在分解随机3阶张量时，将秩提高到$n^{3/2} / 	extrm{polylog} n$。我们还提出了一种检验低秩张量的injective norm的多项式时间复杂度算法，并证明了这个算法的正确性。

使用平方和算法分解超完备的三阶张量