A conditional construction of restricted isometries

Afonso S. Bandeira, Dustin G. Mixon, Joel Moreira

We study the restricted isometry property of a matrix that is built from the discrete Fourier transform matrix by collecting rows indexed by quadratic residues. We find an $\epsilon >0$ su…