A performance analysis framework for SOCP algorithms in noisy compressed sensing

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.