# An efficient uniqueness theorem for overcomplete tensor decomposition

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Apr 2024.

## Built on by (most cited first, 2 of 2)

- [Identifiability of Nonnegative Tucker Decompositions -- Part I: Theory](https://mlsanity.com/paper/2505.12713/) (2025)
- [Overcomplete Tensor Decomposition via Koszul-Young Flattenings](https://mlsanity.com/paper/2411.14344/) (2024)

## Abstract (arXiv)

We give a new, constructive uniqueness theorem for tensor decomposition. It applies to order 3 tensors of format n × n × p and can prove uniqueness of decomposition for generic tensors up to rank r=4n/3 as soon as p ≥ 4. One major advantage over Kruskal's uniqueness theorem is that our theorem has an algorithmic proof, and the resulting algorithm is efficient. Like the uniqueness theorem, it applies in the range n ≤ r ≤ 4n/3. As a result, we obtain the first efficient algorithm for overcomplete decomposition of generic tensors of order 3. For instance, prior to this work it was not known how to efficiently decompose generic tensors of format n × n × n and rank r=1.01n (or rank r ≤ (1+ε) n, for some constant ε >0). Efficient overcomplete decomposition of generic tensors of format n × n × 3 remains an open problem. Our results are based on the method of commuting extensions pioneered by Strassen for the proof of his 3n/2 lower bound on tensor rank and border rank. In particular, we rely on an algorithm for the computation of commuting extensions recently proposed in a companion paper, and on the classical diagonalization-based "Jennrich algorithm" for undercomplete tensor decomposition. This is an updated version of a paper presented at SODA 2025. As a new result, we answer a question from that paper by giving a NP-hardness result for the computation of commuting extensions. The proof relies on a recent construction by Shitov. After the paper appearing in the SODA proceedings was written, another algorithm for the overcomplete decomposition of generic tensors of order~3 was proposed by Kothari, Moitra and Wein.