# The Complexity of Sparse Tensor PCA

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 47 references that are in the map.
- First posted on arXiv 11 Jun 2021.

## Builds on (most cited first, 21 of 21)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio](https://mlsanity.com/paper/1907.11636/) (2019)
- [A statistical model for tensor PCA](https://mlsanity.com/paper/1411.1076/) (2014)
- [The power of sum-of-squares for detecting hidden structures](https://mlsanity.com/paper/1710.05017/) (2017)
- [Reducibility and Statistical-Computational Gaps from Secret Leakage](https://mlsanity.com/paper/2005.08099/) (2020)
- [Subexponential-Time Algorithms for Sparse PCA](https://mlsanity.com/paper/1907.11635/) (2019)
- [Tensor principal component analysis via sum-of-squares proofs](https://mlsanity.com/paper/1507.03269/) (2015)
- [The landscape of the spiked tensor model](https://mlsanity.com/paper/1711.05424/) (2017)
- [An Introductory Guide to Fano's Inequality with Applications in Statistical Estimation](https://mlsanity.com/paper/1901.00555/) (2019)
- [Computational Hardness of Certifying Bounds on Constrained PCA Problems](https://mlsanity.com/paper/1902.07324/) (2019)
- [Tensor Clustering with Planted Structures: Statistical Optimality and Computational Limits](https://mlsanity.com/paper/2005.10743/) (2020)
- [Statistical limits of spiked tensor models](https://mlsanity.com/paper/1612.07728/) (2016)
- [Bayesian estimation from few samples: community detection and related problems](https://mlsanity.com/paper/1710.00264/) (2017)
- [Sparse PCA via Covariance Thresholding](https://mlsanity.com/paper/1311.5179/) (2013)
- [Polynomial-time Tensor Decompositions with Sum-of-Squares](https://mlsanity.com/paper/1610.01980/) (2016)
- [Sparse PCA: Algorithms, Adversarial Perturbations and Certificates](https://mlsanity.com/paper/2011.06585/) (2020)
- [Fast and robust tensor decomposition with applications to dictionary learning](https://mlsanity.com/paper/1706.08672/) (2017)
- [Counterexamples to the Low-Degree Conjecture](https://mlsanity.com/paper/2004.08454/) (2020)
- [Spectral norm of random tensors](https://mlsanity.com/paper/1407.1870/) (2014)
- [A greedy anytime algorithm for sparse PCA](https://mlsanity.com/paper/1910.06846/) (2019)
- [Statistical and computational thresholds for the planted k-densest sub-hypergraph problem](https://mlsanity.com/paper/2011.11500/) (2020)

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

- [Tensor-on-Tensor Regression: Riemannian Optimization, Over-parameterization, Statistical-computational Gap, and Their Interplay](https://mlsanity.com/paper/2206.08756/) (2022)
- [Learning and Testing Latent-Tree Ising Models Efficiently](https://mlsanity.com/paper/2211.13291/) (2022)
- [Higher degree sum-of-squares relaxations robust against oblivious outliers](https://mlsanity.com/paper/2211.07327/) (2022)
- [On the well-spread property and its relation to linear regression](https://mlsanity.com/paper/2206.08092/) (2022)
- [Perturb-and-Project: Differentially Private Similarities and Marginals](https://mlsanity.com/paper/2406.04868/) (2024)
- [sparseGeoHOPCA: A Geometric Solution to Sparse Higher-Order PCA Without Covariance Estimation](https://mlsanity.com/paper/2506.08670/) (2025)
- [Efficient Covariance Estimation for Sparsified Functional Data](https://mlsanity.com/paper/2511.18237/) (2025)

## Abstract (arXiv)

We study the problem of sparse tensor principal component analysis: given a tensor pmb Y = pmb W + λ xotimes p with pmb W ∈ otimespℝn having i.i.d. Gaussian entries, the goal is to recover the k-sparse unit vector x ∈ ℝn. The model captures both sparse PCA (in its Wigner form) and tensor PCA. For the highly sparse regime of k ≤ √n, we present a family of algorithms that smoothly interpolates between a simple polynomial-time algorithm and the exponential-time exhaustive search algorithm. For any 1 ≤ t ≤ k, our algorithms recovers the sparse vector for signal-to-noise ratio λ ≥ tildeO (√t · (k/t)p/2) in time tildeO(np+t), capturing the state-of-the-art guarantees for the matrix settings (in both the polynomial-time and sub-exponential time regimes). Our results naturally extend to the case of r distinct k-sparse signals with disjoint supports, with guarantees that are independent of the number of spikes. Even in the restricted case of sparse PCA, known algorithms only recover the sparse vectors for λ ≥ tildeO(k · r) while our algorithms require λ ≥ tildeO(k). Finally, by analyzing the low-degree likelihood ratio, we complement these algorithmic results with rigorous evidence illustrating the trade-offs between signal-to-noise ratio and running time. This lower bound captures the known lower bounds for both sparse PCA and tensor PCA. In this general model, we observe a more intricate three-way trade-off between the number of samples n, the sparsity k, and the tensor power p.