# Tensor principal component analysis via sum-of-squares proofs

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

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jul 2015.

## Built on by (most cited first, 30 of 35)

- [High-dimensional limit theorems for SGD: Effective dynamics and critical scaling](https://mlsanity.com/paper/2206.04030/) (2022)
- [Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Models](https://mlsanity.com/paper/2305.10633/) (2023)
- [Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence](https://mlsanity.com/paper/2104.12031/) (2021)
- [A Random Matrix Perspective on Random Tensors](https://mlsanity.com/paper/2108.00774/) (2021)
- [On Estimating Rank-One Spiked Tensors in the Presence of Heavy Tailed Errors](https://mlsanity.com/paper/2107.09660/) (2021)
- [Long Random Matrices and Tensor Unfolding](https://mlsanity.com/paper/2110.10210/) (2021)
- [The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Models](https://mlsanity.com/paper/2506.05500/) (2025)
- [Tensor cumulants for statistical inference on invariant distributions](https://mlsanity.com/paper/2404.18735/) (2024)
- [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)
- [Deflated HeteroPCA: Overcoming the curse of ill-conditioning in heteroskedastic PCA](https://mlsanity.com/paper/2303.06198/) (2023)
- [On free energy barriers in Gaussian priors and failure of cold start MCMC for high-dimensional unimodal distributions](https://mlsanity.com/paper/2209.02001/) (2022)
- [Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials](https://mlsanity.com/paper/2211.05274/) (2022)
- [Higher degree sum-of-squares relaxations robust against oblivious outliers](https://mlsanity.com/paper/2211.07327/) (2022)
- [Semidefinite programs simulate approximate message passing robustly](https://mlsanity.com/paper/2311.09017/) (2023)
- [Computational Thresholds in Multi-Modal Learning via the Spiked Matrix-Tensor Model](https://mlsanity.com/paper/2506.02664/) (2025)
- [Efficient Certificates of Anti-Concentration Beyond Gaussians](https://mlsanity.com/paper/2405.15084/) (2024)
- [Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models](https://mlsanity.com/paper/2411.05708/) (2024)
- [Lower Bounds for the Convergence of Tensor Power Iteration on Random Overcomplete Models](https://mlsanity.com/paper/2211.03827/) (2022)
- [Learning from higher-order statistics, efficiently: hypothesis tests, random features, and neural networks](https://mlsanity.com/paper/2312.14922/) (2023)
- [SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More](https://mlsanity.com/paper/2412.21203/) (2024)
- [Transfer learning for tensor Gaussian graphical models](https://mlsanity.com/paper/2211.09391/) (2022)
- [Sharp Analysis of Power Iteration for Tensor PCA](https://mlsanity.com/paper/2401.01047/) (2024)
- [Fundamental limits of Non-Linear Low-Rank Matrix Estimation](https://mlsanity.com/paper/2403.04234/) (2024)
- [Tensor Methods in High Dimensional Data Analysis: Opportunities and Challenges](https://mlsanity.com/paper/2405.18412/) (2024)
- [Perturb-and-Project: Differentially Private Similarities and Marginals](https://mlsanity.com/paper/2406.04868/) (2024)
- [Improved high-dimensional estimation with Langevin dynamics and stochastic weight averaging](https://mlsanity.com/paper/2603.06028/) (2026)
- [On maximum-likelihood estimation in the all-or-nothing regime](https://mlsanity.com/paper/2101.09994/) (2021)
- [Concentration of polynomial random matrices via Efron-Stein inequalities](https://mlsanity.com/paper/2209.02655/) (2022)

## Abstract (arXiv)

We study a statistical model for the tensor principal component analysis problem introduced by Montanari and Richard: Given a order-3 tensor T of the form T = τ · v0otimes 3 + A, where τ ≥ 0 is a signal-to-noise ratio, v0 is a unit vector, and A is a random noise tensor, the goal is to recover the planted vector v0. For the case that A has iid standard Gaussian entries, we give an efficient algorithm to recover v0 whenever τ ≥ ω(n3/4 log(n)1/4), and certify that the recovered vector is close to a maximum likelihood estimator, all with high probability over the random choice of A. The previous best algorithms with provable guarantees required τ ≥ Omega(n). In the regime τ ≤ o(n), natural tensor-unfolding-based spectral relaxations for the underlying optimization problem break down (in the sense that their integrality gap is large). To go beyond this barrier, we use convex relaxations based on the sum-of-squares method. Our recovery algorithm proceeds by rounding a degree-4 sum-of-squares relaxations of the maximum-likelihood-estimation problem for the statistical model. To complement our algorithmic results, we show that degree-4 sum-of-squares relaxations break down for τ ≤ O(n3/4/log(n)1/4), which demonstrates that improving our current guarantees (by more than logarithmic factors) would require new techniques or might even be intractable. Finally, we show how to exploit additional problem structure in order to solve our sum-of-squares relaxations, up to some approximation, very efficiently. Our fastest algorithm runs in nearly-linear time using shifted (matrix) power iteration and has similar guarantees as above. The analysis of this algorithm also confirms a variant of a conjecture of Montanari and Richard about singular vectors of tensor unfoldings.