A problem dependent analysis of SOCP algorithms in noisy compressed sensing
share
Under-determined systems of linear equations with sparse solutions have been the subject of an extensive research in last several years above all due to results of CRT,CanRomTao06,DonohoPol. In this paper we will consider noisy under-determined linear systems. In a breakthrough CanRomTao06 it was established that in noisy systems for any linear level of under-determinedness there is a linear sparsity that can be approximately recovered through an SOCP (second order cone programming) optimization algorithm so that the approximate solution vector is (in an ℓ_2-norm sense) guaranteed to be no further from the sparse unknown vector than a constant times the noise. In our recent work StojnicGenSocp10 we established an alternative framework that can be used for statistical performance analysis of the SOCP algorithms. To demonstrate how the framework works we then showed in StojnicGenSocp10 how one can use it to precisely characterize the generic (worst-case) performance of the SOCP. In this paper we present a different set of results that can be obtained through the framework of StojnicGenSocp10. The results will relate to problem dependent performance analysis of SOCP's. We will consider specific types of unknown sparse vectors and characterize the SOCP performance when used for recovery of such vectors. We will also show that our theoretical predictions are in a solid agreement with the results one can get through numerical simulations.
READ FULL TEXT