Deterministic matrices matching the compressed sensing phase transitions of Gaussian random matrices.

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.