# Smoothed Analysis of Tensor Decompositions

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

## Key facts

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

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

- [How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation](https://mlsanity.com/paper/2310.04064/) (2023)
- [Clustering Mixtures with Almost Optimal Separation in Polynomial Time](https://mlsanity.com/paper/2112.00706/) (2021)
- [Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation](https://mlsanity.com/paper/2106.08537/) (2021)
- [Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activations](https://mlsanity.com/paper/2107.10209/) (2021)
- [Computational Complexity of Learning Neural Networks: Smoothness and Degeneracy](https://mlsanity.com/paper/2302.07426/) (2023)
- [A Robust Spectral Algorithm for Overcomplete Tensor Decomposition](https://mlsanity.com/paper/2203.02790/) (2022)
- [Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials](https://mlsanity.com/paper/2211.05274/) (2022)
- [Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error](https://mlsanity.com/paper/2302.12289/) (2023)
- [Identification of Mixtures of Discrete Product Distributions in Near-Optimal Sample and Time Complexity](https://mlsanity.com/paper/2309.13993/) (2023)
- [Robust Model Selection and Nearly-Proper Learning for GMMs](https://mlsanity.com/paper/2106.02774/) (2021)
- [Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures](https://mlsanity.com/paper/2203.15150/) (2022)
- [Tractable Optimality in Episodic Latent MABs](https://mlsanity.com/paper/2210.03528/) (2022)
- [Algorithms from Invariants: Smoothed Analysis of Orbit Recovery over SO(3)](https://mlsanity.com/paper/2106.02680/) (2021)
- [Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond](https://mlsanity.com/paper/2212.03851/) (2022)
- [Smoothed Differential Privacy](https://mlsanity.com/paper/2107.01559/) (2021)
- [Diagonally-Weighted Generalized Method of Moments Estimation for Gaussian Mixture Modeling](https://mlsanity.com/paper/2507.20459/) (2025)
- [Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transforms](https://mlsanity.com/paper/2601.05157/) (2026)
- [Johnson-Lindenstrauss embeddings for noisy vectors -- taking advantage of the noise](https://mlsanity.com/paper/2209.01006/) (2022)
- [Overcomplete Tensor Decomposition via Koszul-Young Flattenings](https://mlsanity.com/paper/2411.14344/) (2024)

## Abstract (arXiv)

Low rank tensor decompositions are a powerful tool for learning generative models, and uniqueness results give them a significant advantage over matrix decomposition methods. However, tensors pose significant algorithmic challenges and tensors analogs of much of the matrix algebra toolkit are unlikely to exist because of hardness results. Efficient decomposition in the overcomplete case (where rank exceeds dimension) is particularly challenging. We introduce a smoothed analysis model for studying these questions and develop an efficient algorithm for tensor decomposition in the highly overcomplete case (rank polynomial in the dimension). In this setting, we show that our algorithm is robust to inverse polynomial error -- a crucial property for applications in learning since we are only allowed a polynomial number of samples. While algorithms are known for exact tensor decomposition in some overcomplete settings, our main contribution is in analyzing their stability in the framework of smoothed analysis. Our main technical contribution is to show that tensor products of perturbed vectors are linearly independent in a robust sense (i.e. the associated matrix has singular values that are at least an inverse polynomial). This key result paves the way for applying tensor methods to learning problems in the smoothed setting. In particular, we use it to obtain results for learning multi-view models and mixtures of axis-aligned Gaussians where there are many more "components" than dimensions. The assumption here is that the model is not adversarially chosen, formalized by a perturbation of model parameters. We believe this an appealing way to analyze realistic instances of learning problems, since this framework allows us to overcome many of the usual limitations of using tensor methods.