Code and Data supplement to "Deterministic Matrices Matching the Compressed Sensing Phase Transitions of Gaussian Random Matrices."

The data and code provided here are supplementary information for the paper “Deterministic Matrices Matching the Compressed Sensing Phase Transitions for Gaussian Random Matrices” by H. Monajemi, S. Jafarpour,
Stat330/CME362 Collaboration, and D. L. Donoho. The description of the data is provided in the companion README.TXT file. The data is the outcome of research that started as a course project at Stanford University by participants of Stat330/CME362 class taught by Donoho in Fall 2011 (Course TA: Matan Gavish). Data collection was a joint effort of 40 researchers listed in the original paper.\n\n
In compressed sensing, one takes $n < N$ samples of an $N$-dimensional vector $x_0$ using an $n\times N$ matrix $A$, obtaining undersampled measurements $y = Ax_0$. For random matrices with Gaussian i.i.d entries, it is known that, when $x_0$ is $k$-sparse, there is a precisely determined {\it phase transition}: for a certain region in the ($k/n$,$\ n/N$)-phase diagram, convex optimization $\text{min } ||x||_1 \text{ subject to } y=Ax, \ x \in X^N$ typically finds the sparsest solution, while 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 \textit{random} matrix ensembles.\n\n
We consider specific deterministic matrices including Spikes and Sines, Spikes and Noiselets, Paley Frames, Delsarte-Goethals Frames, Chirp Sensing Matrices, and Grassmannian Frames. Extensive experiments show that for a typical $k$-sparse object, convex optimization is successful over a region of the phase diagram that coincides with the region known for Gaussian matrices. In our experiments, we considered coefficients constrained to $X^N$ for four different sets $X \in \{[0,1], R_+, R, C\}$. We establish this finding for each of the associated four phase transitions.

Monajemi H, Jafarpour S, Gavish M, {Stat 330/CME 362} Collaboration, Donoho DL (2012) Data for the article Deterministic Matrices Matching the Compressed Sensing
Phase Transitions of Gaussian Random Matrices. Available at http://purl.stanford.edu/wp335yr5649.