Fundamental thresholds in compressed sensing: a high-dimensional geometry approach

In this chapter, we introduce a unified high-dimensional geometric framework for analyzing the phase transition phenomenon of ℓ_1 minimization in compressive sensing. This framework connects studying the phase transitions of ℓ_1 minimization with computing the Grassmann angles in high-dimensional convex geometry. We demonstrate the broad applications of this Grassmann angle framework by giving sharp phase transitions for ℓ_1 minimization recovery robustness, weighted ℓ_1 minimization algorithms, and iterative reweighted ℓ_1 minimization algorithms. ; © 2012 Cambridge University Press. This work was supported in part by the National Science Foundation under grant no. CCF-0729203, by the David and Lucille Packard Foundation, and by Caltech's Lee Center for Advanced Networking. ; Published - Xu_p305.pdf