A framework to characterize performance of LASSO algorithms

In this paper we consider solving noisy under-determined systems of linear equations with sparse solutions. A noiseless equivalent attracted enormous attention in recent years, above all, due to work of citeCRT,CanRomTao06,DonohoPol where it was shown in a statistical and large dimensional context that a sparse unknown vector (of sparsity proportional to the length of the vector) can be recovered from an under-determined system via a simple polynomial ℓ1-optimization algorithm. citeCanRomTao06 further established that even when the equations are noisy, one can, through an SOCP noisy equivalent of ℓ1, obtain an approximate solution that is (in an ℓ2-norm sense) no further than a constant times the noise from the sparse unknown vector. In our recent works citeStojnicCSetam09,StojnicUpper10, we created a powerful mechanism that helped us characterize exactly the performance of ℓ1 optimization in the noiseless case (as shown in citeStojnicEquiv10 and as it must be if the axioms of mathematics are well set, the results of citeStojnicCSetam09,StojnicUpper10 are in an absolute agreement with the corresponding exact ones from citeDonohoPol). In this paper we design a mechanism, as powerful as those from citeStojnicCSetam09,StojnicUpper10, that can handle the analysis of a LASSO type of algorithm (and many others) that can be (or typically are) used for "solving" noisy under-determined systems. Using the mechanism we then, in a statistical context, compute the exact worst-case ℓ2 norm distance between the unknown sparse vector and the approximate one obtained through such a LASSO. The obtained results match the corresponding exact ones obtained in citeBayMon10,DonMalMon10. Moreover, as a by-product of our analysis framework we recognize existence of an SOCP type of algorithm that achieves the same performance.