Improved Lower Bounds for the Restricted Isometry Property of Subsampled Fourier Matrices

2019/03/28 by Rao, Shravas · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Probability (math.PR)

paper · doi:10.48550/arxiv.1903.12146

Abstract

Let A be an N × N Fourier matrix over \mathbbF_p^logN/logp for some prime p. We improve upon known lower bounds for the number of rows of A that must be sampled so that the resulting matrix M satisfies the restricted isometry property for k-sparse vectors. This property states that ‖Mv‖₂² is approximately ‖v‖₂² for all k-sparse vectors v. In particular, if k = Ω( log²N), we show that Ω(klogklogN/logp) rows must be sampled to satisfy the restricted isometry property with constant probability.

Cited by

• Restricted Quasiconvexity Isometry Property for Symmetric α-Stable Random Matrices

Related

• The Restricted Isometry Property of Subsampled Fourier Matrices
• Restricted Isometry Property for General p-Norms
• Satisfying the Restricted Isometry Property with the Optimal Number of Rows and Slightly Less Randomness
• A conditional construction of restricted isometries
• An Improved Lower Bound for Sparse Reconstruction from Subsampled Walsh Matrices