@article{f8026a83bbea45fcbd010481f476f912,
title = "A conditional construction of restricted isometries",
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 ∈ > 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.",
author = "Bandeira, {Afonso S.} and Mixon, {Dustin G.} and Joel Moreira",
note = "Funding Information: This work was partially supported by AFOSR [FA9550-12-1-0317 to A.S.B.] and NSF grant [DMS- 1317308 to A.S.B.] Most of this work was done while the first author was with the Program for Applied and Computational Mathematics at Princeton University. This work was supported by an AFOSR Young Investigator Research Program award [to D.G.M.], [DMS-1321779 to D.G.M.], and AFOSR [F4FGA05076J002 to D.G.M.]. The views expressed in this article are those of the authors and do not reflect the official policy or position of the United States Air Force, Department of Defense, or the U.S. Government. Publisher Copyright: {\textcopyright} The Author(s) 2016. Published by Oxford University Press. All rights reserved.",
year = "2017",
month = jan,
doi = "10.1093/imrn/rnv385",
language = "English (US)",
volume = "2017",
pages = "372--381",
journal = "International Mathematics Research Notices",
issn = "1073-7928",
publisher = "Oxford University Press",
number = "2",
}