The restricted isometry property of subsampled Fourier matrices

Ishay Haviv, Oded Regev

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

A matrix A ∈ Cq×N satisfies the restricted isometry property of order k with constant e if it preserves the l2 norm of all κ-sparse vectors up to a factor of 1 ± ϵ. We prove that a matrix A obtained by randomly sampling q = O(k· log2 k · log TV) rows from an N × N Fourier matrix satisfies the restricted isometry property of order k with a fixed e with high probability. This improves on Rudelson and Vershynin (Comm. Pure Appl. Math., 2008), its subsequent improvements, and Bourgain (GAFA Seminar Notes, 2014).

Original languageEnglish (US)
Title of host publication27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
EditorsRobert Krauthgamer
PublisherAssociation for Computing Machinery
Pages288-297
Number of pages10
ISBN (Electronic)9781510819672
DOIs
StatePublished - 2016
Event27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 - Arlington, United States
Duration: Jan 10 2016Jan 12 2016

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume1

Other

Other27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
CountryUnited States
CityArlington
Period1/10/161/12/16

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'The restricted isometry property of subsampled Fourier matrices'. Together they form a unique fingerprint.

  • Cite this

    Haviv, I., & Regev, O. (2016). The restricted isometry property of subsampled Fourier matrices. In R. Krauthgamer (Ed.), 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 (pp. 288-297). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 1). Association for Computing Machinery. https://doi.org/10.1137/1.9781611974331.ch22