期刊名称：Proceedings of the National Academy of Sciences
印刷版ISSN：0027-8424
电子版ISSN：1091-6490
出版年度：2013
卷号：110
期号：4
页码：1181-1186
DOI：10.1073/pnas.1219540110
语种：English
出版社：The National Academy of Sciences of the United States of America
摘要：In compressed sensing, one takes [IMG]/medium/pnas.1219540110i1.gif" ALT="Formula "> samples of an N-dimensional vector [IMG]/medium/pnas.1219540110i2.gif" ALT="Formula "> using an [IMG]/medium/pnas.1219540110i3.gif" ALT="Formula "> matrix A, obtaining undersampled measurements [IMG]/medium/pnas.1219540110i4.gif" ALT="Formula ">. For random matrices with independent standard Gaussian entries, it is known that, when [IMG]/medium/pnas.1219540110i5.gif" ALT="Formula "> is k-sparse, there is a precisely determined phase transition: for a certain region in the ([IMG]/medium/pnas.1219540110i6.gif" ALT="Formula ">,[IMG]/medium/pnas.1219540110i7.gif" ALT="Formula ">)-phase diagram, convex optimization [IMG]/medium/pnas.1219540110i8.gif" ALT="Formula "> 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 [IMG]/medium/pnas.1219540110i9.gif" ALT="Formula "> for four different sets [IMG]/medium/pnas.1219540110i10.gif" ALT="Formula ">, and the results establish our finding for each of the four associated phase transitions.
关键词：sparse recovery ; universality in random matrix theory equiangular tight frames ; restricted isometry property ; coherence
