@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: 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",

}