# Algorithms with Polynomially-Improved Approximation Factors for the 2 rightarrow q Norm, and Applications

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 45 references that are in the map.
- First posted on arXiv 24 May 2026.

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

- [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)
- [Learning from Untrusted Data](https://mlsanity.com/paper/1611.02315/) (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 for Outlier-Robust Regression](https://mlsanity.com/paper/1803.03241/) (2018)
- [Outlier Robust Mean Estimation with Subgaussian Rates via Stability](https://mlsanity.com/paper/2007.15618/) (2020)
- [Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers](https://mlsanity.com/paper/1703.04940/) (2017)
- [Robust Linear Regression: Optimal Rates in Polynomial Time](https://mlsanity.com/paper/2007.01394/) (2020)
- [Simple, Efficient, and Neural Algorithms for Sparse Coding](https://mlsanity.com/paper/1503.00778/) (2015)
- [Robust Sparse Mean Estimation via Sum of Squares](https://mlsanity.com/paper/2206.03441/) (2022)
- [Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation](https://mlsanity.com/paper/2106.08537/) (2021)
- [Tester-Learners for Halfspaces: Universal Algorithms](https://mlsanity.com/paper/2305.11765/) (2023)
- [How Hard Is Robust Mean Estimation?](https://mlsanity.com/paper/1903.07870/) (2019)
- [Sum-of-squares proofs and the quest toward optimal algorithms](https://mlsanity.com/paper/1404.5236/) (2014)
- [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)
- [SoS Degree Reduction with Applications to Clustering and Robust Moment Estimation](https://mlsanity.com/paper/2101.01509/) (2021)
- [Towards Learning Sparsely Used Dictionaries with Arbitrary Supports](https://mlsanity.com/paper/1804.08603/) (2018)
- [Estimating operator norms using covering nets](https://mlsanity.com/paper/1509.05065/) (2015)
- [On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs](https://mlsanity.com/paper/2308.09667/) (2023)
- [Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Lattices](https://mlsanity.com/paper/2410.02636/) (2024)

## Abstract (arXiv)

The 2 rightarrow q norm of a matrix X ∈ ℝn × d is defined as lVert X rVert2 rightarrow q = suplVert v rVert2 = 1 lVert Xv rVertq. We give polynomial-time multiplicative approximation algorithms for this norm when q > 2 (i.e. in the hypercontractive setting). This problem either directly captures or is closely related to long-standing open problems in combinatorial optimization and hardness of approximation (e.g. Small Set Expansion), quantum information (e.g. Best Separable State), and algorithmic statistics. Very little is known about what approximation factors we can achieve for this problem in polynomial time, even though such approximations have significant downstream consequences. Barak, Brand~ao, Harrow, Kelner, Steurer, and Zhou showed that no polynomial-time algorithm can achieve an approximation factor better than 2^√log n, assuming the Exponential Time Hypothesis (FOCS'12). On the other hand, a simple spectral algorithm gives a d1/4-approximation as a baseline. For the important special case of q = 4, prior work of Guth, Maldague, and Urschel (SIAM Matrix Analysis and Applications'25) can be combined with known sparsification techniques to give a d1/6-approximation. We improve over these results by polynomial factors, giving a d1/8-approximation. Moreover, we construct sum-of-squares certificates for the 2 rightarrow q norm. This directly implies improved algorithms for robust mean and covariance estimation, robust regression, and clustering, when the data only satisfies a bound on its q-th moment.