A conditional construction of restricted isometries

2014/10/23 by Bandeira, Afonso S., Mixon, Dustin G., Moreira, Joel
#FOS: Computer and information sciences #FOS: Mathematics #Functional Analysis (math.FA) #Information Theory (cs.IT) #Number Theory (math.NT)

paper · doi:10.48550/arxiv.1410.6457

Abstract

We study the restricted isometry property of a matrix that is built from the discrete Fourier transform matrix by collecting rows indexed by quadratic residues. We find an ε>0 such that, conditioned on a folklore conjecture in number theory, this matrix satisfies the restricted isometry property with sparsity parameter K=Ω(M^1/2+ε), where M is the number of rows.

Related

• The Restricted Isometry Property of Subsampled Fourier Matrices
• Improved Lower Bounds for the Restricted Isometry Property of Subsampled Fourier Matrices
• Restricted Isometry Property for General p-Norms
• Computational Complexity of Certifying Restricted Isometry Property
• Explicit Matrices with the Restricted Isometry Property: Breaking the Square-Root Bottleneck