The restricted isometry property of subsampled fourier matrices

Ishay Haviv, Oded Regev

Research output: Chapter in Book/Report/Conference proceedingChapter

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).

Original languageEnglish (US)
Title of host publicationLecture Notes in Mathematics
PublisherSpringer Verlag
Pages163-179
Number of pages17
DOIs
StatePublished - Jan 1 2017

Publication series

NameLecture Notes in Mathematics
Volume2169
ISSN (Print)0075-8434

    Fingerprint

ASJC Scopus subject areas

  • Algebra and Number Theory

Cite this

Haviv, I., & Regev, O. (2017). The restricted isometry property of subsampled fourier matrices. In Lecture Notes in Mathematics (pp. 163-179). (Lecture Notes in Mathematics; Vol. 2169). Springer Verlag. https://doi.org/10.1007/978-3-319-45282-1_11