A rigorous geometry-probability equivalence in characterization of ${\ell }_1$-optimization

Abstract

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 \cite{CRT,DonohoPol}. In a statistical context it was rigorously established for the first time in \cite{CRT,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 ${\ell }_1$-optimization algorithm (of course, this assuming that such a sparse solution vector exists). Moreover, the geometric approach of \cite{DonohoPol} produced the exact values for the proportionalities in question. In our recent work \cite{StojnicCSetam09} 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 \cite{DonohoPol}. In this paper we give a rigorous analytical confirmation that the results of \cite{StojnicCSetam09} indeed match those from \cite{DonohoPol}.

References in corpus (2)

• Various thresholds for ${\ell }_1$-optimization in compressed sensing
• Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling

Cited by in corpus (2)

• A framework to characterize performance of LASSO algorithms
• Meshes that trap random subspaces