2013/03/29 by Mihailo Stojnic, Stojnic, Mihailo
Computer Science · Engineering · Mathematics · #Digital Image Processing Techniques #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Mathematical Analysis and Transform Methods #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1303.7287
openalex publication_date 2013/03/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we consider under-determined systems of linear equations that have sparse solutions. This subject attracted enormous amount of interest in recent years primarily due to influential works \citeCRT,DonohoPol. In a statistical context it was rigorously established for the first time in \citeCRT,DonohoPol that if the number of equations is smaller than but still linearly proportional to the number of unknowns then a sparse vector of sparsity also linearly proportional to the number of unknowns can be recovered through a polynomial ℓ1-optimization algorithm (of course, this assuming that such a sparse solution vector exists). Moreover, the geometric approach of \citeDonohoPol produced the exact values for the proportionalities in question. In our recent work \citeStojnicCSetam09 we introduced an alternative statistical approach that produced attainable values of the proportionalities. Those happened to be in an excellent numerical agreement with the ones of \citeDonohoPol. In this paper we give a rigorous analytical confirmation that the results of \citeStojnicCSetam09 indeed match those from \citeDonohoPol.