# SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 56 references that are in the map.
- First posted on arXiv 30 Dec 2024.

## Builds on (most cited first, 30 of 31)

- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016)
- [Being Robust (in High Dimensions) Can Be Practical](https://mlsanity.com/paper/1703.00893/) (2017)
- [Mixture Models, Robustness, and Sum of Squares Proofs](https://mlsanity.com/paper/1711.07454/) (2017)
- [Efficient Algorithms and Lower Bounds for Robust Linear Regression](https://mlsanity.com/paper/1806.00040/) (2018)
- [Outlier Robust Mean Estimation with Subgaussian Rates via Stability](https://mlsanity.com/paper/2007.15618/) (2020)
- [Robust Covariance and Scatter Matrix Estimation under Huber's Contamination Model](https://mlsanity.com/paper/1506.00691/) (2015)
- [Robustness Implies Privacy in Statistical Estimation](https://mlsanity.com/paper/2212.05015/) (2022)
- [Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers](https://mlsanity.com/paper/1703.04940/) (2017)
- [Subexponential-Time Algorithms for Sparse PCA](https://mlsanity.com/paper/1907.11635/) (2019)
- [Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors](https://mlsanity.com/paper/1512.02337/) (2015)
- [Tensor principal component analysis via sum-of-squares proofs](https://mlsanity.com/paper/1507.03269/) (2015)
- [Outlier-robust moment-estimation via sum-of-squares](https://mlsanity.com/paper/1711.11581/) (2017)
- [From Robustness to Privacy and Back](https://mlsanity.com/paper/2302.01855/) (2023)
- [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)
- [Lattice-Based Methods Surpass Sum-of-Squares in Clustering](https://mlsanity.com/paper/2112.03898/) (2021)
- [Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimation](https://mlsanity.com/paper/2211.00724/) (2022)
- [Robust Sparse Mean Estimation via Sum of Squares](https://mlsanity.com/paper/2206.03441/) (2022)
- [Sparse PCA via Covariance Thresholding](https://mlsanity.com/paper/1311.5179/) (2013)
- [Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributions](https://mlsanity.com/paper/2301.12250/) (2023)
- [Optimal Spectral Recovery of a Planted Vector in a Subspace](https://mlsanity.com/paper/2105.15081/) (2021)
- [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)
- [Rounding Sum-of-Squares Relaxations](https://mlsanity.com/paper/1312.6652/) (2013)
- [SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications](https://mlsanity.com/paper/2410.21194/) (2024)
- [Strongly Refuting Random CSPs Below the Spectral Threshold](https://mlsanity.com/paper/1605.00058/) (2016)
- [Scaling Law for Recovering the Sparsest Element in a Subspace](https://mlsanity.com/paper/1310.1654/) (2013)
- [The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination](https://mlsanity.com/paper/2307.10273/) (2023)
- [A greedy anytime algorithm for sparse PCA](https://mlsanity.com/paper/1910.06846/) (2019)

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

- [Sample-Optimal Private Regression in Polynomial Time](https://mlsanity.com/paper/2503.24321/) (2025)
- [PTF Testing Lower Bounds for Non-Gaussian Component Analysis](https://mlsanity.com/paper/2511.19398/) (2025)
- [Computation-Utility-Privacy Tradeoffs in Bayesian Estimation](https://mlsanity.com/paper/2603.18254/) (2026)

## Abstract (arXiv)

We study textitsparse singular value certificates for random rectangular matrices. If M is an n × d matrix with independent Gaussian entries, we give a new family of polynomial-time algorithms which can certify upper bounds on the maximum of |M u|, where u is a unit vector with at most η n nonzero entries for a given η ∈ (0,1). This basic algorithmic primitive lies at the heart of a wide range of problems across algorithmic statistics and theoretical computer science. Our algorithms certify a bound which is asymptotically smaller than the naive one, given by the maximum singular value of M, for nearly the widest-possible range of n,d, and η. Efficiently certifying such a bound for a range of n,d and η which is larger by any polynomial factor than what is achieved by our algorithm would violate lower bounds in the SQ and low-degree polynomials models. Our certification algorithm makes essential use of the Sum-of-Squares hierarchy. To prove the correctness of our algorithm, we develop a new combinatorial connection between the graph matrix approach to analyze random matrices with dependent entries, and the Efron-Stein decomposition of functions of independent random variables. As applications of our certification algorithm, we obtain new efficient algorithms for a wide range of well-studied algorithmic tasks. In algorithmic robust statistics, we obtain new algorithms for robust mean and covariance estimation with tradeoffs between breakdown point and sample complexity, which are nearly matched by SQ and low-degree polynomial lower bounds (that we establish). We also obtain new polynomial-time guarantees for certification of ℓ1/ℓ2 distortion of random subspaces of ℝn (also with nearly matching lower bounds), sparse principal component analysis, and certification of the 2rightarrow p norm of a random matrix.