# Overcomplete Tensor Decomposition via Koszul-Young Flattenings

arXiv: https://arxiv.org/abs/2411.14344 · HTML: https://mlsanity.com/paper/2411.14344/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 70 references that are in the map.
- First posted on arXiv 21 Nov 2024.

## Builds on (most cited first, 24 of 24)

- [Introduction to Tensor Decompositions and their Applications in Machine Learning](https://mlsanity.com/paper/1711.10781/) (2017)
- [Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors](https://mlsanity.com/paper/1512.02337/) (2015)
- [Polynomial-time Tensor Decompositions with Sum-of-Squares](https://mlsanity.com/paper/1610.01980/) (2016)
- [Smoothed Analysis of Tensor Decompositions](https://mlsanity.com/paper/1311.3651/) (2013)
- [The Kikuchi Hierarchy and Tensor PCA](https://mlsanity.com/paper/1904.03858/) (2019)
- [Decomposing Overcomplete 3rd Order Tensors using Sum-of-Squares Algorithms](https://mlsanity.com/paper/1504.05287/) (2015)
- [Fourier PCA and Robust Tensor Decomposition](https://mlsanity.com/paper/1306.5825/) (2013)
- [A Robust Spectral Algorithm for Overcomplete Tensor Decomposition](https://mlsanity.com/paper/2203.02790/) (2022)
- [Learning sums of powers of low-degree polynomials in the non-degenerate case](https://mlsanity.com/paper/2004.06898/) (2020)
- [Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials](https://mlsanity.com/paper/2211.05274/) (2022)
- [Classical and Quantum Algorithms for Tensor Principal Component Analysis](https://mlsanity.com/paper/1907.12724/) (2019)
- [Fast algorithm for overcomplete order-3 tensor decomposition](https://mlsanity.com/paper/2202.06442/) (2022)
- [How to refute a random CSP](https://mlsanity.com/paper/1505.04383/) (2015)
- [Exact nuclear norm, completion and decomposition for random overcomplete tensors via degree-4 SOS](https://mlsanity.com/paper/2011.09416/) (2020)
- [Algorithms and Certificates for Boolean CSP Refutation: "Smoothed is no harder than Random"](https://mlsanity.com/paper/2109.04415/) (2021)
- [Overcomplete order-3 tensor decomposition, blind deconvolution and Gaussian mixture models](https://mlsanity.com/paper/2007.08133/) (2020)
- [Efficient Tensor Decomposition](https://mlsanity.com/paper/2007.15589/) (2020)
- [A simple and sharper proof of the hypergraph Moore bound](https://mlsanity.com/paper/2207.10850/) (2022)
- [Complete Decomposition of Symmetric Tensors in Linear Time and Polylogarithmic Precision](https://mlsanity.com/paper/2211.07407/) (2022)
- [Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond](https://mlsanity.com/paper/2212.03851/) (2022)
- [An efficient uniqueness theorem for overcomplete tensor decomposition](https://mlsanity.com/paper/2404.07801/) (2024)
- [On the uniqueness and computation of commuting extensions](https://mlsanity.com/paper/2401.01302/) (2024)
- [New Tools for Smoothed Analysis: Least Singular Value Bounds for Random Matrices with Dependent Entries](https://mlsanity.com/paper/2405.01517/) (2024)
- [X-arability of mixed quantum states](https://mlsanity.com/paper/2409.18948/) (2024)

## Abstract (arXiv)

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.