Derandomized Compressed Sensing with Nonuniform Guarantees for l1 Recovery

In compressed sensing, the sensing matrices of minimal sample complexity are constructed with the help of randomness. Over 13 years ago, Tao (Open question: deterministic WP matrices. https://terrytao.wordpress.com/2007/07/02/open-question-deterministic-uup-matrices/) posed the notoriously difficult problem of derandomizing these sensing matrices. While most work in this vein has been in the setting of explicit deterministic matrices with uniform guarantees, the present paper focuses on explicit random matrices of low entropy with non-uniform guarantees. Specifically, we extend the techniques of Hilgel et al. (Found Comput Math 14:115-150, 2014) to show that for every delta is an element of (0, 1], there exists an explicit random m x N partial Fourier matrix A with m <= C-1 (delta)s log(4/delta) (N/epsilon) and entropy at most C-2(delta)s(8) log(5) (N/epsilon) such that for every s-sparse signal x is an element of C-N, there exists an event of probability at least 1 - epsilon over which x is the unique minimizer of parallel to z parallel to(1) subject to Az = Ax. The bulk of our analysis uses tools from decoupling to estimate the extreme singular values of the submatrix of A whose columns correspond to the support of x.