@inbook{c2f1a4a03d704f309d38019bd85c91d2,
title = "The restricted isometry property of subsampled fourier matrices",
abstract = "A matrix A ∈ Cq×N satisfies the restricted isometry property of order k with constant ∈ if it preserves the l2 norm of all k-sparse vectors up to a factor of 1 ± ϵ. We prove that a matrix A obtained by randomly sampling q = O(k log2 k log N) rows from an N × N Fourier matrix satisfies the restricted isometry property of order k with a fixed ∈ with high probability. This improves on Rudelson and Vershynin (Comm Pure Appl Math, 2008), its subsequent improvements, and Bourgain (GAFA Seminar Notes, 2014).",
author = "Ishay Haviv and Oded Regev",
note = "Funding Information: We thank Afonso S. Bandeira, Mahdi Cheraghchi, Michael Kapralov, Jelani Nelson, and Eric Price for useful discussions, and anonymous reviewers for useful comments. Oded Regev was supported by the Simons Collaboration on Algorithms and Geometry and by the National Science Foundation (NSF) under Grant No. CCF-1320188. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the NSF. Publisher Copyright: {\textcopyright} Springer International Publishing AG 2017.",
year = "2017",
doi = "10.1007/978-3-319-45282-1_11",
language = "English (US)",
series = "Lecture Notes in Mathematics",
publisher = "Springer Verlag",
pages = "163--179",
booktitle = "Lecture Notes in Mathematics",
}