A conditional construction of restricted isometries

Original · EN

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¹/²⁺ε), where M is the number of rows.