Derandomizing restricted isometries via the Legendre symbol

DOI10.1007/s00365-015-9310-6zbMath1367.94143arXiv1406.4089OpenAlexW2962898310MaRDI QIDQ295815

Afonso S. Bandeira, Matthew Fickus, Dustin G. Mixon, Joel Moreira

Publication date: 13 June 2016

Published in: Constructive Approximation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1406.4089

zbMATH Keywords

derandomizationcompressed sensingrestricted isometry propertyLegendre symbolsmall-bias sample space

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Sampling theory in information and communication theory (94A20) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items (5)

Derandomized compressed sensing with nonuniform guarantees for \(\ell_1\) recovery ⋮ Book Review: A mathematical introduction to compressive sensing ⋮ Discrete uncertainty principles and sparse signal processing ⋮ Robust Width: A Characterization of Uniformly Stable and Robust Compressed Sensing ⋮ Group-theoretic constructions of erasure-robust frames

Cites Work

• Unnamed Item
• Unnamed Item
• The road to deterministic matrices with the restricted isometry property
• Explicit constructions of RIP matrices and related problems
• Steiner equiangular tight frames
• The restricted isometry property and its implications for compressed sensing
• Chirp sensing codes: Deterministic compressed sensing measurements for fast recovery
• A simple proof of the restricted isometry property for random matrices
• Uniform uncertainty principle for Bernoulli and subgaussian ensembles
• Equations over finite fields. An elementary approach
• Several generalizations of Weil sums
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• PRIMES is in P
• Deterministic constructions of compressed sensing matrices
• Suprema of Chaos Processes and the Restricted Isometry Property
• Certifying the Restricted Isometry Property is Hard
• New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Explicit Matrices with the Restricted Isometry Property: Breaking the Square-Root Bottleneck
• On sparse reconstruction from Fourier and Gaussian measurements
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Simple Constructions of Almost k-wise Independent Random Variables
• Lower bounds on the maximum cross correlation of signals (Corresp.)
• On finite pseudorandom binary sequences I: Measure of pseudorandomness, the Legendre symbol
• Constructing Small-Bias Sets from Algebraic-Geometric Codes
• Numerical linear algebra in the streaming model
• New constructions of RIP matrices with fast multiplication and fewer rows
• Deterministic methods to find primes
• Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes
• Breaking the k ² barrier for explicit RIP matrices
• A Constructive Solution to a Tournament Problem
• On a Problem in Graph Theory
• Some remarks on the theory of graphs

This page was built for publication: Derandomizing restricted isometries via the Legendre symbol