Overcomplete Tensor Decomposition via Koszul-Young Flattenings

Motivated by connections between algebraic complexity lower bounds and tensor decompositions, we investigate Koszul-Young flattenings, which are the main ingredient in recent lower bounds for matrix multiplication. Based on this tool we give a new algorithm for decomposing an $n_{1} \times n_{2} \times n_{3}$ tensor as the sum of a minimal number of rank-1 terms, and certifying uniqueness of this decomposition. For $n_{1} \leq n_{2} \leq n_{3}$ with $n_{1} \rightarrow \infty$ and $n_{3} / n_{2}=O(1)$, our algorithm is guaranteed to succeed when the tensor rank is bounded by $r \leq(1-\epsilon)\left(n_{2}+n_{3}\right)$ for an arbitrary $\epsilon \gt 0$, provided the tensor components are generically chosen. For any fixed $\epsilon$, the runtime is polynomial in $n_{3}$. When $n_{2}=n_{3}=n$, our condition on the rank gives a factor-of- 2 improvement over the classical simultaneous diagonalization algorithm, which requires $r \leq n$, and also improves on the recent algorithm of Koiran (2024) which requires $r \leq 4 n / 3$. It also improves on the PhD thesis of Persu (2018) which solves rank detection for $r \leq 3 n / 2$. We complement our upper bounds by showing limitations, in particular that no flattening of the style we consider can surpass rank $n_{2}+n_{3}$. Furthermore, for $n \times n \times n$ tensors, we show that an even more general class of degree- $\boldsymbol{d}$ polynomial flattenings cannot surpass rank Cn for a constant $C=C(d)$. This suggests that for tensor decompositions, the case of generic components may be fundamentally harder than that of random components, where efficient decomposition is possible even in highly overcomplete settings.