# A performance analysis framework for SOCP algorithms in noisy compressed sensing

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Mar 2013.

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

- [Label-Imbalanced and Group-Sensitive Classification under Overparameterization](https://mlsanity.com/paper/2103.01550/) (2021)
- [Ridge interpolators in correlated factor regression models -- exact risk analysis](https://mlsanity.com/paper/2406.09183/) (2024)
- [Precise analysis of ridge interpolators under heavy correlations -- a Random Duality Theory view](https://mlsanity.com/paper/2406.09199/) (2024)
- [Theoretical limits of descending ℓ0 sparse-regression ML algorithms](https://mlsanity.com/paper/2410.07651/) (2024)

## Abstract (arXiv)

Solving under-determined systems of linear equations with sparse solutions attracted enormous amount of attention in recent years, above all, due to work of citeCRT,CanRomTao06,DonohoPol. In citeCRT,CanRomTao06,DonohoPol it was rigorously shown for the first time that in a statistical and large dimensional context a linear sparsity can be recovered from an under-determined system via a simple polynomial ℓ1-optimization algorithm. citeCanRomTao06 went even further and established that in noisy systems for any linear level of under-determinedness there is again a linear sparsity that can be approximately recovered through an SOCP (second order cone programming) noisy equivalent to ℓ1. Moreover, the approximate solution is (in an ℓ2-norm sense) guaranteed to be no further from the sparse unknown vector than a constant times the noise. In this paper we will also consider solving noisy linear systems and present an alternative statistical framework that can be used for their analysis. To demonstrate how the framework works we will show how one can use it to precisely characterize the approximation error of a wide class of SOCP algorithms. We will also show that our theoretical predictions are in a solid agrement with the results one can get through numerical simulations.