PT - JOURNAL ARTICLE
AU - Monajemi, Hatef
AU - Jafarpour, Sina
AU - Gavish, Matan
AU - ,
AU - Donoho, David L.
TI - Deterministic matrices matching the compressed sensing phase transitions of Gaussian random matrices
AID - 10.1073/pnas.1219540110
DP - 2013 Jan 22
TA - Proceedings of the National Academy of Sciences
PG - 1181--1186
VI - 110
IP - 4
4099 - http://www.pnas.org/content/110/4/1181.short
4100 - http://www.pnas.org/content/110/4/1181.full
SO - Proc Natl Acad Sci USA2013 Jan 22; 110
AB - In compressed sensing, one takes samples of an N-dimensional vector using an matrix A, obtaining undersampled measurements . For random matrices with independent standard Gaussian entries, it is known that, when is k-sparse, there is a precisely determined phase transition: for a certain region in the (,)-phase diagram, convex optimization typically finds the sparsest solution, whereas outside that region, it typically fails. It has been shown empirically that the same propertyâ€”with the same phase transition locationâ€”holds for a wide range of non-Gaussian random matrix ensembles. We report extensive experiments showing that the Gaussian phase transition also describes numerous deterministic matrices, including Spikes and Sines, Spikes and Noiselets, Paley Frames, Delsarte-Goethals Frames, Chirp Sensing Matrices, and Grassmannian Frames. Namely, for each of these deterministic matrices in turn, for a typical k-sparse object, we observe that convex optimization is successful over a region of the phase diagram that coincides with the region known for Gaussian random matrices. Our experiments considered coefficients constrained to for four different sets , and the results establish our finding for each of the four associated phase transitions.