Decomposing Overcomplete 3rd Order Tensors using Sum-of-Squares
  Algorithms
  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.
