# Optimal Spectral Recovery of a Planted Vector in a Subspace

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 56 references that are in the map.
- First posted on arXiv 31 May 2021.

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

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016)
- [Spectral Methods for Data Science: A Statistical Perspective](https://mlsanity.com/paper/2012.08496/) (2020)
- [Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio](https://mlsanity.com/paper/1907.11636/) (2019)
- [The power of sum-of-squares for detecting hidden structures](https://mlsanity.com/paper/1710.05017/) (2017)
- [Computational Barriers to Estimation from Low-Degree Polynomials](https://mlsanity.com/paper/2008.02269/) (2020)
- [Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors](https://mlsanity.com/paper/1512.02337/) (2015)
- [Computational Hardness of Certifying Bounds on Constrained PCA Problems](https://mlsanity.com/paper/1902.07324/) (2019)
- [A note on the sample complexity of the Er-SpUD algorithm by Spielman, Wang and Wright for exact recovery of sparsely used dictionaries](https://mlsanity.com/paper/1601.02049/) (2016)
- [Complete Dictionary Recovery over the Sphere](https://mlsanity.com/paper/1504.06785/) (2015)
- [Finding a sparse vector in a subspace: Linear sparsity using alternating directions](https://mlsanity.com/paper/1412.4659/) (2014)
- [Sparse PCA: Algorithms, Adversarial Perturbations and Certificates](https://mlsanity.com/paper/2011.06585/) (2020)
- [Finding the Sparsest Vectors in a Subspace: Theory, Algorithms, and Applications](https://mlsanity.com/paper/2001.06970/) (2020)
- [Rounding Sum-of-Squares Relaxations](https://mlsanity.com/paper/1312.6652/) (2013)
- [Polynomial Time and Sample Complexity for Non-Gaussian Component Analysis: Spectral Methods](https://mlsanity.com/paper/1704.01041/) (2017)
- [Lifting Sum-of-Squares Lower Bounds: Degree-2 to Degree-4](https://mlsanity.com/paper/1911.01411/) (2019)
- [The Average-Case Time Complexity of Certifying the Restricted Isometry Property](https://mlsanity.com/paper/2005.11270/) (2020)
- [Scaling Law for Recovering the Sparsest Element in a Subspace](https://mlsanity.com/paper/1310.1654/) (2013)
- [Non-Gaussian Component Analysis using Entropy Methods](https://mlsanity.com/paper/1807.04936/) (2018)

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

- [Lattice-Based Methods Surpass Sum-of-Squares in Clustering](https://mlsanity.com/paper/2112.03898/) (2021)
- [Tensor-on-Tensor Regression: Riemannian Optimization, Over-parameterization, Statistical-computational Gap, and Their Interplay](https://mlsanity.com/paper/2206.08756/) (2022)
- [Clustering a Mixture of Gaussians with Unknown Covariance](https://mlsanity.com/paper/2110.01602/) (2021)
- [Non-Gaussian Component Analysis via Lattice Basis Reduction](https://mlsanity.com/paper/2112.09104/) (2021)
- [Large Dimensional Independent Component Analysis: Statistical Optimality and Computational Tractability](https://mlsanity.com/paper/2303.18156/) (2023)
- [Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials](https://mlsanity.com/paper/2308.15728/) (2023)
- [A computational transition for detecting correlated stochastic block models by low-degree polynomials](https://mlsanity.com/paper/2409.00966/) (2024)
- [Sum-of-squares lower bounds for Non-Gaussian Component Analysis](https://mlsanity.com/paper/2410.21426/) (2024)
- [On the well-spread property and its relation to linear regression](https://mlsanity.com/paper/2206.08092/) (2022)
- [Near-optimal fitting of ellipsoids to random points](https://mlsanity.com/paper/2208.09493/) (2022)
- [Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps](https://mlsanity.com/paper/2402.15409/) (2024)
- [SQ Lower Bounds for Random Sparse Planted Vector Problem](https://mlsanity.com/paper/2301.11124/) (2023)
- [Wasserstein Projection Pursuit of Non-Gaussian Signals](https://mlsanity.com/paper/2302.12693/) (2023)
- [Learning from higher-order statistics, efficiently: hypothesis tests, random features, and neural networks](https://mlsanity.com/paper/2312.14922/) (2023)
- [Tensor learning with orthogonal, Lorentz, and symplectic symmetries](https://mlsanity.com/paper/2406.01552/) (2024)
- [SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More](https://mlsanity.com/paper/2412.21203/) (2024)
- [Sparse PCA Beyond Covariance Thresholding](https://mlsanity.com/paper/2302.10158/) (2023)
- [PTF Testing Lower Bounds for Non-Gaussian Component Analysis](https://mlsanity.com/paper/2511.19398/) (2025)
- [Recovering Imbalanced Clusters via Gradient-Based Projection Pursuit](https://mlsanity.com/paper/2502.02668/) (2025)
- [A Smooth Computational Transition in Tensor PCA](https://mlsanity.com/paper/2509.09904/) (2025)
- [Low-degree Lower bounds for clustering in moderate dimension](https://mlsanity.com/paper/2602.23023/) (2026)

## Abstract (arXiv)

Recovering a planted vector v in an n-dimensional random subspace of ℝN is a generic task related to many problems in machine learning and statistics, such as dictionary learning, subspace recovery, principal component analysis, and non-Gaussian component analysis. In this work, we study computationally efficient estimation and detection of a planted vector v whose ℓ4 norm differs from that of a Gaussian vector with the same ℓ2 norm. For instance, in the special case where v is an N ρ-sparse vector with Bernoulli-Gaussian or Bernoulli-Rademacher entries, our results include the following: (1) We give an improved analysis of a slight variant of the spectral method proposed by Hopkins, Schramm, Shi, and Steurer (2016), showing that it approximately recovers v with high probability in the regime n ρ ll √N. This condition subsumes the conditions ρ ll 1/√n or n √ρ lesssim √N required by previous work up to polylogarithmic factors. We achieve ℓ_∞ error bounds for the spectral estimator via a leave-one-out analysis, from which it follows that a simple thresholding procedure exactly recovers v with Bernoulli-Rademacher entries, even in the dense case ρ = 1. (2) We study the associated detection problem and show that in the regime n ρ gg √N, any spectral method from a large class (and more generally, any low-degree polynomial of the input) fails to detect the planted vector. This matches the condition for recovery and offers evidence that no polynomial-time algorithm can succeed in recovering a Bernoulli-Gaussian vector v when n ρ gg √N.