TY - GEN

T1 - The restricted isometry property of subsampled Fourier matrices

AU - Haviv, Ishay

AU - Regev, Oded

PY - 2016

Y1 - 2016

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

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

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

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

U2 - 10.1137/1.9781611974331.ch22

DO - 10.1137/1.9781611974331.ch22

M3 - Conference contribution

AN - SCOPUS:84962826200

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 288

EP - 297

BT - 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016

A2 - Krauthgamer, Robert

PB - Association for Computing Machinery

T2 - 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016

Y2 - 10 January 2016 through 12 January 2016

ER -