# Fast and robust tensor decomposition with applications to dictionary learning

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jun 2017.

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

- [Clustering Mixtures with Almost Optimal Separation in Polynomial Time](https://mlsanity.com/paper/2112.00706/) (2021)
- [SoS Degree Reduction with Applications to Clustering and Robust Moment Estimation](https://mlsanity.com/paper/2101.01509/) (2021)
- [The Complexity of Sparse Tensor PCA](https://mlsanity.com/paper/2106.06308/) (2021)
- [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)
- [Fast algorithm for overcomplete order-3 tensor decomposition](https://mlsanity.com/paper/2202.06442/) (2022)
- [Closed-Loop Transcription via Convolutional Sparse Coding](https://mlsanity.com/paper/2302.09347/) (2023)
- [Efficient Certificates of Anti-Concentration Beyond Gaussians](https://mlsanity.com/paper/2405.15084/) (2024)
- [Lower Bounds for the Convergence of Tensor Power Iteration on Random Overcomplete Models](https://mlsanity.com/paper/2211.03827/) (2022)
- [Efficient Sparse Coding using Hierarchical Riemannian Pursuit](https://mlsanity.com/paper/2104.10314/) (2021)
- [Conditional Linear Regression for Heterogeneous Covariances](https://mlsanity.com/paper/2111.07834/) (2021)
- [Tensor Methods in High Dimensional Data Analysis: Opportunities and Challenges](https://mlsanity.com/paper/2405.18412/) (2024)
- [Concentration of polynomial random matrices via Efron-Stein inequalities](https://mlsanity.com/paper/2209.02655/) (2022)
- [Decentralized Complete Dictionary Learning via ℓ4-Norm Maximization](https://mlsanity.com/paper/2211.03628/) (2022)

## Abstract (arXiv)

We develop fast spectral algorithms for tensor decomposition that match the robustness guarantees of the best known polynomial-time algorithms for this problem based on the sum-of-squares (SOS) semidefinite programming hierarchy. Our algorithms can decompose a 4-tensor with n-dimensional orthonormal components in the presence of error with constant spectral norm (when viewed as an n2-by-n2 matrix). The running time is n5 which is close to linear in the input size n4. We also obtain algorithms with similar running time to learn sparsely-used orthogonal dictionaries even when feature representations have constant relative sparsity and non-independent coordinates. The only previous polynomial-time algorithms to solve these problem are based on solving large semidefinite programs. In contrast, our algorithms are easy to implement directly and are based on spectral projections and tensor-mode rearrangements. Or work is inspired by recent of Hopkins, Schramm, Shi, and Steurer (STOC'16) that shows how fast spectral algorithms can achieve the guarantees of SOS for average-case problems. In this work, we introduce general techniques to capture the guarantees of SOS for worst-case problems.