This is an announcement for the paper "A conditional construction of restricted isometries" by Afonso S. Bandeira, Dustin G. Mixon, and Joel Moreira.

Abstract: 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$ such that, conditioned on a folklore conjecture in number theory, this matrix satisfies the restricted isometry property with sparsity parameter $K=\Omega(M^{1/2+\epsilon})$, where $M$ is the number of rows.

Archive classification: math.FA cs.IT math.IT math.NT

Remarks: 6 pages

Submitted from: moreira@math.ohio-state.edu

The paper may be downloaded from the archive by web browser from URL

http://front.math.ucdavis.edu/1410.6457

or

http://arXiv.org/abs/1410.6457