Explicit constructions of RIP matrices and related problems

DOI10.1215/00127094-1384809zbMath1236.94027arXiv1008.4535OpenAlexW3105703423MaRDI QIDQ635478

Jean Bourgain, Kevin Ford, Denka Kutzarova, Stephen Dilworth, Sergei V. Konyagin

Publication date: 19 August 2011

Published in: Duke Mathematical Journal (Search for Journal in Brave)

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

zbMATH Keywords

thin setsproduct setsspherical codeRestricted Isometry Property (RIP)RIP matricessmall Fourier coefficientssparse-signals recoverysumset estimatesTurán's power sum problem

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Exponential sums (11T23) Other types of codes (94B60) Additive bases, including sumsets (11B13) Approximation by arbitrary nonlinear expressions; widths and entropy (41A46) Arithmetic combinatorics; higher degree uniformity (11B30)

Related Items

Derandomized compressed sensing with nonuniform guarantees for \(\ell_1\) recovery, Derandomizing restricted isometries via the Legendre symbol, An Unbiased Approach to Low Rank Recovery, Book Review: A mathematical introduction to compressive sensing, Deterministic convolutional compressed sensing matrices, Explicit Matrices with the Restricted Isometry Property: Breaking the Square-Root Bottleneck, Coherence of sensing matrices coming from algebraic-geometric codes, An analytic approach to cardinalities of sumsets, Deterministic construction of compressed sensing matrices with characters over finite fields, Equiangular tight frames that contain regular simplices, Explicit universal sampling sets in finite vector spaces, A novel probabilistic approach for vehicle position prediction in free, partial, and full GPS outages, Kesten-McKay law for random subensembles of Paley equiangular tight frames, Newly deterministic construction of compressed sensing matrices via singular linear spaces over finite fields, On exact recovery of sparse vectors from linear measurements, Explicit RIP matrices: an update, Stability of the elastic net estimator, Sergei Vladimirovich Konyagin turns 60, Deterministic construction of compressed sensing matrices from constant dimension codes, Side effects of learning from low-dimensional data embedded in a Euclidean space, Deterministic construction of compressed sensing matrices based on semilattices, Unnamed Item, Deterministic sampling of sparse trigonometric polynomials, Compressive Sensing, Deletion correcting codes meet the Littlewood-Offord problem, Flavors of Compressive Sensing, Stochastic Collocation vial₁-Minimisation on Low Discrepancy Point Sets with Application to Uncertainty Quantification, On the sparsity of Lasso minimizers in sparse data recovery, Compressive time-of-flight 3D imaging using block-structured sensing matrices, The road to deterministic matrices with the restricted isometry property, Steiner equiangular tight frames, Toward a unified theory of sparse dimensionality reduction in Euclidean space, On the restricted isometry property of the Paley matrix, Mathematics of Analog‐to‐Digital Conversion, Frames as Codes, An evaluation of the sparsity degree for sparse recovery with deterministic measurement matrices, A deterministic sparse FFT for functions with structured Fourier sparsity, Deterministic matrices matching the compressed sensing phase transitions of Gaussian random matrices, Deterministic constructions of compressed sensing matrices based on optimal codebooks and codes, Constructions of compressed sensing matrices based on the subspaces of symplectic space over finite fields, Mathematics of Electron Tomography, Packings in Real Projective Spaces, Sparse recovery in bounded Riesz systems with applications to numerical methods for PDEs, Construction of Sparse Binary Sensing Matrices Using Set Systems, Welch bound-achieving compressed sensing matrices from optimal codebooks, Deterministic Construction of Compressed Sensing Matrices from Codes, Deterministic constructions of compressed sensing matrices based on codes, Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition, Preserving injectivity under subgaussian mappings and its application to compressed sensing, Flexible construction of measurement matrices in compressed sensing based on extensions of incidence matrices of combinatorial designs, Theory and applications of compressed sensing, An asymptotic existence result on compressed sensing matrices, Group-theoretic constructions of erasure-robust frames

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the optimality of the orthogonal greedy algorithm for \(\mu\)-coherent dictionaries
• On the size of incoherent systems
• A probabilistic approach to problems of diophantine approximation
• The restricted isometry property and its implications for compressed sensing
• Multilinear exponential sums in prime fields under optimal entropy condition on the sources
• Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit
• A simple proof of the restricted isometry property for random matrices
• Sums in the grid
• Some extremal properties of trigonometric sums
• Exponential sum estimates over a subgroup in an arbitrary finite field
• Explicit solutions to certain inf max problems from Turán power sum theory
• Deterministic constructions of compressed sensing matrices
• Reconstruction and subgaussian operators in asymptotic geometric analysis
• Approximate formulas for some functions of prime numbers
• On Lebesgue-type inequalities for greedy approximation
• List decoding algorithms for certain concatenated codes
• Extensions of Lipschitz mappings into a Hilbert space
• Construction of a Thin Set with small Fourier Coefficients
• On sparse reconstruction from Fourier and Gaussian measurements
• Decoding by Linear Programming
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• On a variant of sum-product estimates and explicit exponential sum bounds in prime fields
• An Estimate for Character Sums
• Simple Constructions of Almost k-wise Independent Random Variables
• A theorem on cubes
• Constructing Small Sets that are Uniform in Arithmetic Progressions
• Constructing Small-Bias Sets from Algebraic-Geometric Codes
• The Orthogonal Super Greedy Algorithm and Applications in Compressed Sensing
• Stable signal recovery from incomplete and inaccurate measurements