We give fast algorithms for low-rank tensor decomposition.
Over $\mathbb R$ and $\mathbb C$ we give a deterministic algorithm that takes as input an order-$d$, width-$n$, rank-$k$ tensor, gets measurement access to the tensor, runs in time
$k^{O(k^2)}\cdot \mathrm{poly}(n,d)$, and finds a minimal decomposition as a sum of rank-one tensors. This algorithm also immediately gives an algorithm for tensor rank computation with similar time complexity.
This improves upon the previous best runtime of $k^{O(k^{16})}\cdot \mathrm{poly}( n,d)$ by the work of Bhargava and Shringi.

In particular, we get the first subexponential time algorithms for tensor decomposition of order-$d$ tensors of rank as large as $\sqrt n/\log n$. One interesting consequence is that the run time of our algorithm for decomposing order-$d$ tensors approaches the fastest algorithms we know for decomposing order-3 tensors ($2^{O(k^2)}\cdot \mathrm{poly}(n)$). Moreover, known NP-hardness results for tensor rank computation suggest that an exponential dependence on $k$ is necessary.

Our approach is via the equivalent problem of proper learning for the class of set multilinear depth-3 circuits of top fan-in $k$. The main technical tools involve iteratively applying appropriate pseudorandom projections combined with solving multivariate polynomial systems.