# Semi-Random Sparse Recovery in Nearly-Linear Time arXiv: https://arxiv.org/abs/2203.04002 · HTML: https://mlsanity.com/paper/2203.04002/ ## Key facts - Cited by 18 papers in the map (data through 14 Oct 2026). - Builds on 20 of its 89 references that are in the map. - First posted on arXiv 8 Mar 2022. ## Builds on (most cited first, 20 of 20) - [Distribution-Independent PAC Learning of Halfspaces with Massart Noise](https://mlsanity.com/paper/1906.10075/) (2019) - [On Iterative Hard Thresholding Methods for High-dimensional M-Estimation](https://mlsanity.com/paper/1410.5137/) (2014) - [Learning Halfspaces with Massart Noise Under Structured Distributions](https://mlsanity.com/paper/2002.05632/) (2020) - [Geometric Median in Nearly Linear Time](https://mlsanity.com/paper/1606.05225/) (2016) - [Solving Tall Dense Linear Programs in Nearly Linear Time](https://mlsanity.com/paper/2002.02304/) (2020) - [How Robust are Reconstruction Thresholds for Community Detection?](https://mlsanity.com/paper/1511.01473/) (2015) - [Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noise](https://mlsanity.com/paper/2102.05312/) (2021) - [Forster Decomposition and Learning Halfspaces with Noise](https://mlsanity.com/paper/2107.05582/) (2021) - [On the Power of Preconditioning in Sparse Linear Regression](https://mlsanity.com/paper/2106.09207/) (2021) - [Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability](https://mlsanity.com/paper/2006.04787/) (2020) - [On the Prediction Performance of the Lasso](https://mlsanity.com/paper/1402.1700/) (2014) - [Boosting in the Presence of Massart Noise](https://mlsanity.com/paper/2106.07779/) (2021) - [ReLU Regression with Massart Noise](https://mlsanity.com/paper/2109.04623/) (2021) - [Optimal prediction for sparse linear models? Lower bounds for coordinate-separable M-estimators](https://mlsanity.com/paper/1503.03188/) (2015) - [Non-Convex Matrix Completion Against a Semi-Random Adversary](https://mlsanity.com/paper/1803.10846/) (2018) - [Learning Communities in the Presence of Errors](https://mlsanity.com/paper/1511.03229/) (2015) - [Constant Factor Approximation for Balanced Cut in the PIE model](https://mlsanity.com/paper/1406.5665/) (2014) - [Tight Error Bounds for Structured Prediction](https://mlsanity.com/paper/1409.5834/) (2014) - [Towards Learning Sparsely Used Dictionaries with Arbitrary Supports](https://mlsanity.com/paper/1804.08603/) (2018) - [Exploiting Prior Knowledge in Compressed Sensing Wireless ECG Systems](https://mlsanity.com/paper/1405.4201/) (2014) ## Built on by (most cited first, 18 of 18) - [Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time](https://mlsanity.com/paper/2302.11068/) (2023) - [Testing distributional assumptions of learning algorithms](https://mlsanity.com/paper/2204.07196/) (2022) - [ReSQueing Parallel and Private Stochastic Convex Optimization](https://mlsanity.com/paper/2301.00457/) (2023) - [Oja's Algorithm for Streaming Sparse PCA](https://mlsanity.com/paper/2402.07240/) (2024) - [Dueling Optimization with a Monotone Adversary](https://mlsanity.com/paper/2311.11185/) (2023) - [The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination](https://mlsanity.com/paper/2505.20177/) (2025) - [Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions](https://mlsanity.com/paper/2406.02789/) (2024) - [Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random](https://mlsanity.com/paper/2501.09851/) (2025) - [Matrix Completion in Almost-Verification Time](https://mlsanity.com/paper/2308.03661/) (2023) - [Testing Noise Assumptions of Learning Algorithms](https://mlsanity.com/paper/2501.09189/) (2025) - [Top-K ranking with a monotone adversary](https://mlsanity.com/paper/2402.07445/) (2024) - [Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization](https://mlsanity.com/paper/2406.07373/) (2024) - [Low-Precision Streaming PCA](https://mlsanity.com/paper/2510.22440/) (2025) - [On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models](https://mlsanity.com/paper/2412.14315/) (2024) - [Computation-Utility-Privacy Tradeoffs in Bayesian Estimation](https://mlsanity.com/paper/2603.18254/) (2026) - [Entrywise Error Bounds for Spectral Ranking with Semi-Random Adversaries](https://mlsanity.com/paper/2605.23854/) (2026) - [Lasso and Partially-Rotated Designs](https://mlsanity.com/paper/2505.11093/) (2025) - [Combinatorial Sparse PCA Beyond the Spiked Identity Model](https://mlsanity.com/paper/2603.02607/) (2026) ## Abstract (arXiv) Sparse recovery is one of the most fundamental and well-studied inverse problems. Standard statistical formulations of the problem are provably solved by general convex programming techniques and more practical, fast (nearly-linear time) iterative methods. However, these latter "fast algorithms" have previously been observed to be brittle in various real-world settings. We investigate the brittleness of fast sparse recovery algorithms to generative model changes through the lens of studying their robustness to a "helpful" semi-random adversary, a framework which tests whether an algorithm overfits to input assumptions. We consider the following basic model: let A ∈ ℝn × d be a measurement matrix which contains an unknown subset of rows G ∈ ℝm × d which are bounded and satisfy the restricted isometry property (RIP), but is otherwise arbitrary. Letting x^star ∈ ℝd be s-sparse, and given either exact measurements b = A x^star or noisy measurements b = A x^star + xi, we design algorithms recovering x^star information-theoretically optimally in nearly-linear time. We extend our algorithm to hold for weaker generative models relaxing our planted RIP assumption to a natural weighted variant, and show that our method's guarantees naturally interpolate the quality of the measurement matrix to, in some parameter regimes, run in sublinear time. Our approach differs from prior fast iterative methods with provable guarantees under semi-random generative models: natural conditions on a submatrix which make sparse recovery tractable are NP-hard to verify. We design a new iterative method tailored to the geometry of sparse recovery which is provably robust to our semi-random model. We hope our approach opens the door to new robust, efficient algorithms for natural statistical inverse problems.