The restricted isometry property of subsampled fourier matrices

Ishay Haviv; Oded Regev

doi:10.1007/978-3-319-45282-1_11

The restricted isometry property of subsampled fourier matrices

Ishay Haviv, Oded Regev

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Chapter

Abstract

A matrix A ∈ C^q×N satisfies the restricted isometry property of order k with constant ∈ if it preserves the l₂ 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 log² 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 language	English (US)
Title of host publication	Lecture Notes in Mathematics
Publisher	Springer Verlag
Pages	163-179
Number of pages	17
DOIs	https://doi.org/10.1007/978-3-319-45282-1_11
State	Published - Jan 1 2017

Publication series

Name	Lecture Notes in Mathematics
Volume	2169
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

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

year = "2017",

month = jan

day = "1",

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

}

TY - CHAP

T1 - The restricted isometry property of subsampled fourier matrices

AU - Haviv, Ishay

AU - Regev, Oded

PY - 2017/1/1

Y1 - 2017/1/1

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

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

UR - http://www.scopus.com/inward/record.url?scp=85018503011&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85018503011&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-45282-1_11

DO - 10.1007/978-3-319-45282-1_11

M3 - Chapter

AN - SCOPUS:85018503011

T3 - Lecture Notes in Mathematics

SP - 163

EP - 179

BT - Lecture Notes in Mathematics

PB - Springer Verlag

ER -

Access to Document

10.1007/978-3-319-45282-1_11