Deterministic matrices matching the compressed sensing phase transitions of Gaussian random matrices.
Proc Natl Acad Sci U S A
; 110(4): 1181-6, 2013 Jan 22.
Article
em En
| MEDLINE
| ID: mdl-23277588
ABSTRACT
In compressed sensing, one takes samples of an N-dimensional vector using an matrix A, obtaining undersampled measurements Y = Ax(0). 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 (k/n,n/N)-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 X(N) for four different sets X [symbol see text]{[0, 1], R(=), R, C}, and the results establish our finding for each of the four associated phase transitions.
Texto completo:
1
Coleções:
01-internacional
Base de dados:
MEDLINE
Tipo de estudo:
Clinical_trials
Idioma:
En
Revista:
Proc Natl Acad Sci U S A
Ano de publicação:
2013
Tipo de documento:
Article
País de afiliação:
Estados Unidos