A conditional construction of restricted isometries

DOI10.1093/IMRN/RNV385MaRDI QIDQ4611870zbMATH OpenOpenAlexFDO

Authors Afonso S. Bandeira, Dustin G. Mixon, Joel Moreira

Publication date 22 January 2019

Published in IMRN. International Mathematics Research Notices (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.6457, http://wrap.warwick.ac.uk/127286/7/WRAP-conditional-construction-restricted-isometries-Moreira-2019.pdf

Mathematics Subject Classification ID

Irregularities of distribution, discrepancy (11K38) Inequalities involving eigenvalues and eigenvectors (15A42) Random matrices (algebraic aspects) (15B52)

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 $epsilon>0$ such that, conditioned on a folklore conjecture in number theory, this matrix satisfies the restricted isometry property with sparsity parameter $K=Omega(M^{1/2+epsilon})$, where $M$ is the number of rows.

Recommendations

• The restricted isometry property of subsampled Fourier matrices
• On the restricted isometry property of the Paley matrix
• The road to deterministic matrices with the restricted isometry property
• Derandomizing restricted isometries via the Legendre symbol

Cited in

(13)

• Derandomized compressed sensing with nonuniform guarantees for _1 recovery
• Fast overcomplete dictionary construction with probabilistic guarantees
• On the restricted isometry property of the Paley matrix
• Group-theoretic constructions of erasure-robust frames
• Fast and RIP-optimal transforms
• Kesten-McKay law for random subensembles of Paley equiangular tight frames
• Derandomizing restricted isometries via the Legendre symbol
• The restricted isometry property for time-frequency structured random matrices
• The restricted isometry property of subsampled Fourier matrices
• Packings in real projective spaces
• The road to deterministic matrices with the restricted isometry property
• Spectral Pseudorandomness and the Road to Improved Clique Number Bounds for Paley Graphs
• Satisfying the restricted isometry property with the optimal number of rows and slightly less randomness

This page was built for publication: A conditional construction of restricted isometries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4611870)