# Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Apr 2013.

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

- [Reconstructing Training Data from Model Gradient, Provably](https://mlsanity.com/paper/2212.03714/) (2022)
- [Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activations](https://mlsanity.com/paper/2107.10209/) (2021)
- [Identifiability of Deep Polynomial Neural Networks](https://mlsanity.com/paper/2506.17093/) (2025)
- [Joint Sensing, Communication, and AI: A Trifecta for Resilient THz User Experiences](https://mlsanity.com/paper/2305.00135/) (2023)
- [On the Role of Channel Capacity in Learning Gaussian Mixture Models](https://mlsanity.com/paper/2202.07707/) (2022)
- [Towards Identifiability of Interventional Stochastic Differential Equations](https://mlsanity.com/paper/2505.15987/) (2025)
- [Low-Rank Tensor Recovery via Variational Schatten-p Quasi-Norm and Jacobian Regularization](https://mlsanity.com/paper/2506.22134/) (2025)
- [Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transforms](https://mlsanity.com/paper/2601.05157/) (2026)
- [Data Understanding Survey: Pursuing Improved Dataset Characterization Via Tensor-based Methods](https://mlsanity.com/paper/2510.14161/) (2025)

## Abstract (arXiv)

We give a robust version of the celebrated result of Kruskal on the uniqueness of tensor decompositions: we prove that given a tensor whose decomposition satisfies a robust form of Kruskal's rank condition, it is possible to approximately recover the decomposition if the tensor is known up to a sufficiently small (inverse polynomial) error. Kruskal's theorem has found many applications in proving the identifiability of parameters for various latent variable models and mixture models such as Hidden Markov models, topic models etc. Our robust version immediately implies identifiability using only polynomially many samples in many of these settings. This polynomial identifiability is an essential first step towards efficient learning algorithms for these models. Recently, algorithms based on tensor decompositions have been used to estimate the parameters of various hidden variable models efficiently in special cases as long as they satisfy certain "non-degeneracy" properties. Our methods give a way to go beyond this non-degeneracy barrier, and establish polynomial identifiability of the parameters under much milder conditions. Given the importance of Kruskal's theorem in the tensor literature, we expect that this robust version will have several applications beyond the settings we explore in this work.