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 n1 × n2 × n3 tensor as the sum of a minimal number of rank-1 terms, and certifying uniqueness of this decomposition. For n1 ≤ n2 ≤ n3 with n1 → ∞ and n3/n2 = O(1), our algorithm is guaranteed to succeed when the tensor rank is bounded by r ≤ (1-ε)(n2 + n3) for an arbitrary ε > 0, provided the tensor components are generically chosen. For any fixed ε, the runtime is polynomial in n3. When n2 = n3 = n, our condition on the rank gives a factor-of-2 improvement over the classical simultaneous diagonalization algorithm, which requires r ≤ n, and also improves on the recent algorithm of Koiran (2024) which requires r ≤ 4n/3. It also improves on the PhD thesis of Persu (2018) which solves rank detection for r ≤ 3n/2. We complement our upper bounds by showing limitations, in particular that no flattening of the style we consider can surpass rank n2 + n3. Furthermore, for n × n × n tensors, we show that an even more general class of degree-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.