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

2026/05/31 by Samuel B. Hopkins, Stefan Tiegel
Computer Science · Mathematics · #cs.DS #cs.LG #math.ST #stat.ML #stat.TH

paper · pdf · doi:10.48550/arxiv.2605.25303

v3 added that sparsification can be used to reduce to n roughly d^q/2

arxiv created 2026/08/03 · arxiv updated 2026/08/05

Abstract

The 2 → q norm of a matrix X ∈ ℝ^{n × d} is defined as ‖ X ‖_{2 → q} = sup_{‖ v ‖2 = 1} ‖ Xv ‖_q. 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ão, 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 d^1/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 d^1/6-approximation. We improve over these results by polynomial factors, giving a d^1/8-approximation. Moreover, we construct sum-of-squares certificates for the 2 → 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.

Citations

• SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications
• Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Lattices
• On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs
• Tester-Learners for Halfspaces: Universal Algorithms
• Robust Sparse Mean Estimation via Sum of Squares
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation
• SoS Degree Reduction with Applications to Clustering and Robust Moment Estimation
• Outlier Robust Mean Estimation with Subgaussian Rates via Stability
• Robust Linear Regression: Optimal Rates in Polynomial Time
• Playing Unique Games on Certified Small-Set Expanders
• How Hard Is Robust Mean Estimation?
• Towards Learning Sparsely Used Dictionaries with Arbitrary Supports
• Efficient Algorithms for Outlier-Robust Regression
• Mixture Models, Robustness, and Sum of Squares Proofs
• Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers
• Being Robust (in High Dimensions) Can Be Practical
• Limitations of semidefinite programs for separable states and entangled games
• Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures
• Learning from Untrusted Data
• Agnostic Estimation of Mean and Covariance
• Robust Estimators in High Dimensions without the Computational\n Intractability
• Estimating operator norms using covering nets
• Simple, Efficient, and Neural Algorithms for Sparse Coding
• A useful variant of the Davis--Kahan theorem for statisticians
• Sum-of-squares proofs and the quest toward optimal algorithms
• Rounding Sum-of-Squares Relaxations
• Hypercontractivity, Sum-of-Squares Proofs, and their Applications
• Hypercontractivity and its applications
• Reductions Between Expansion Problems
• Subexponential Algorithms for Unique Games and Related Problems
• Graph expansion and the unique games conjecture
• Approximating Matrix p-norms
• Testing product states, quantum Merlin-Arthur games and tensor optimisation
• Approximating the moments of marginals of high-dimensional distributions
• Quantitative estimates of the convergence of the empirical covariance matrix in Log-concave Ensembles
• Twice-Ramanujan Sparsifiers
• Optimal algorithms and inapproximability results for every CSP?