A conditional construction of restricted isometries

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

13 Scopus citations


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 ∈ > 0 such that, conditioned on a folklore conjecture in number theory, this matrix satisfies the restricted isometry property with sparsity parameter K = Ω(M1/2+∈), where M is the number of rows.

Original languageEnglish (US)
Pages (from-to)372-381
Number of pages10
JournalInternational Mathematics Research Notices
Issue number2
StatePublished - Jan 2017

ASJC Scopus subject areas

  • General Mathematics


Dive into the research topics of 'A conditional construction of restricted isometries'. Together they form a unique fingerprint.

Cite this