Compressive sensing predicts that sparse vectors can be recovered via efficient algorithms from what was previously believed to be incomplete information.
Recovery methods include convex optimization approaches (l1-minimization). Provably optimal measurement process are described via Gaussian random matrices.
In practice, however, more structure is required. We describe the state of the art on recovery results for several types of structured random measurement matrices, including random partial Fourier matrices and subsampled random convolutions.