Fast algorithm for overcomplete order-3 tensor decomposition

Jingqiu Ding, Tommaso d'Orsi, Chih-Hung Liu +2

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…