Explicit constructions of RIP matrices and related problems

DOI10.1215/00127094-1384809zbMATH Open1236.94027arXiv1008.4535OpenAlexW3105703423MaRDI QIDQ635478FDOQ635478

Authors: Jean Bourgain, S. J. Dilworth, Kevin Ford, D. Kutzarova, Sergei Konyagin 

Publication date: 19 August 2011

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

Abstract: We give a new explicit construction of $nimesN$ matrices satisfying the Restricted Isometry Property (RIP). Namely, for some c>0, large N and any n satisfying N^{1-c} < n < N, we construct RIP matrices of order k^{1/2+c}. This overcomes the natural barrier k=O(n^{1/2}) for proofs based on small coherence, which are used in all previous explicit constructions of RIP matrices. Key ingredients in our proof are new estimates for sumsets in product sets and for exponential sums with the products of sets possessing special additive structure. We also give a construction of sets of n complex numbers whose k-th moments are uniformly small for 1le kle N (Turan's power sum problem), which improves upon known explicit constructions when (log N)^{1+o(1)} le nle (log N)^{4+o(1)}. This latter construction produces elementary explicit examples of n by N matrices that satisfy RIP and whose columns constitute a new spherical code; for those problems the parameters closely match those of existing constructions in the range (log N)^{1+o(1)} le nle (log N)^{5/2+o(1)}.

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

Recommendations

• Breaking the k ² barrier for explicit RIP matrices
• Explicit matrices with the restricted isometry property: breaking the square-root bottleneck
• Explicit Construction of RIP Matrices Is Ramsey‐Hard
• New constructions of RIP matrices with fast multiplication and fewer rows
• An Improved Estimate in the Restricted Isometry Problem

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) Arithmetic combinatorics; higher degree uniformity (11B30) Exponential sums (11T23) Other types of codes (94B60) Additive bases, including sumsets (11B13) Approximation by arbitrary nonlinear expressions; widths and entropy (41A46)

Cites Work

• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Extensions of Lipschitz mappings into a Hilbert space
• Decoding by Linear Programming
• Stable signal recovery from incomplete and inaccurate measurements
• A simple proof of the restricted isometry property for random matrices
• Title not available (Why is that?)
• Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit
• Additive combinatorics
• List decoding algorithms for certain concatenated codes
• On a variant of sum-product estimates and explicit exponential sum bounds in prime fields
• Simple Constructions of Almost k-wise Independent Random Variables
• Title not available (Why is that?)
• On sparse reconstruction from Fourier and Gaussian measurements
• The restricted isometry property and its implications for compressed sensing
• Approximate formulas for some functions of prime numbers
• Deterministic constructions of compressed sensing matrices
• Constructing small-bias sets from algebraic-geometric codes
• An Estimate for Character Sums
• Title not available (Why is that?)
• Reconstruction and subgaussian operators in asymptotic geometric analysis
• On Lebesgue-type inequalities for greedy approximation
• On the optimality of the orthogonal greedy algorithm for \(\mu\)-coherent dictionaries
• Title not available (Why is that?)
• The Orthogonal Super Greedy Algorithm and Applications in Compressed Sensing
• On the size of incoherent systems
• Multilinear exponential sums in prime fields under optimal entropy condition on the sources
• A theorem on cubes
• 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
• Title not available (Why is that?)
• Construction of a Thin Set with small Fourier Coefficients
• Constructing Small Sets that are Uniform in Arithmetic Progressions
• On the solutions to a power sum problem
• A probabilistic approach to problems of diophantine approximation

Cited In (61)

• Compliant Ternary Matrices based on Restricted Isometry Property: Construction and Application to Image Retrieval
• Explicit Construction of RIP Matrices Is Ramsey‐Hard
• Compressive time-of-flight 3D imaging using block-structured sensing matrices
• Compressive Sensing
• Deterministic matrices matching the compressed sensing phase transitions of Gaussian random matrices
• The road to deterministic matrices with the restricted isometry property
• Additive combinatorics: with a view towards computer science and cryptography -- an exposition
• Packings in real projective spaces
• A deterministic sparse FFT for functions with structured Fourier sparsity
• Construction of sparse binary sensing matrices using set systems
• Deterministic constructions of compressed sensing matrices based on optimal codebooks and codes
• Deterministic construction of compressed sensing matrices from constant dimension codes
• On the restricted isometry property of the Paley matrix
• Derandomizing restricted isometries via the Legendre symbol
• Mathematics of electron tomography
• Theory and applications of compressed sensing
• Fast and RIP-optimal transforms
• Derandomized compressed sensing with nonuniform guarantees for \(\ell_1\) recovery
• New constructions of RIP matrices with fast multiplication and fewer rows
• Breaking the k ² barrier for explicit RIP matrices
• Kesten-McKay law for random subensembles of Paley equiangular tight frames
• An evaluation of the sparsity degree for sparse recovery with deterministic measurement matrices
• Multivariable polynomials for the construction of binary sensing matrices
• Steiner equiangular tight frames
• Using elimination theory to construct rigid matrices
• Constructions of compressed sensing matrices based on the subspaces of symplectic space over finite fields
• Sparse recovery in bounded Riesz systems with applications to numerical methods for PDEs
• An analytic approach to cardinalities of sumsets
• Deterministic convolutional compressed sensing matrices
• Coherence of sensing matrices coming from algebraic-geometric codes
• Deletion correcting codes meet the Littlewood-Offord problem
• Stability of the elastic net estimator
• A novel probabilistic approach for vehicle position prediction in free, partial, and full GPS outages
• Book Review: A mathematical introduction to compressive sensing
• An Unbiased Approach to Low Rank Recovery
• Explicit matrices with the restricted isometry property: breaking the square-root bottleneck
• Mathematics of analog-to-digital conversion
• Stochastic Collocation vial₁-Minimisation on Low Discrepancy Point Sets with Application to Uncertainty Quantification
• An asymptotic existence result on compressed sensing matrices
• Preserving injectivity under subgaussian mappings and its application to compressed sensing
• Deterministic construction of compressed sensing matrices with characters over finite fields
• Explicit RIP matrices: an update
• Group-theoretic constructions of erasure-robust frames
• Toward a unified theory of sparse dimensionality reduction in Euclidean space
• Explicit universal sampling sets in finite vector spaces
• Welch bound-achieving compressed sensing matrices from optimal codebooks
• On the sparsity of Lasso minimizers in sparse data recovery
• Side effects of learning from low-dimensional data embedded in a Euclidean space
• Computational complexity of certifying restricted isometry property
• Analysis of Termatiko sets in measurement matrices
• Newly deterministic construction of compressed sensing matrices via singular linear spaces over finite fields
• Deterministic construction of compressed sensing matrices based on semilattices
• Sergei Vladimirovich Konyagin turns 60
• Deterministic construction of compressed sensing matrices from codes
• Flexible construction of measurement matrices in compressed sensing based on extensions of incidence matrices of combinatorial designs
• On exact recovery of sparse vectors from linear measurements
• Deterministic sampling of sparse trigonometric polynomials
• Frames as codes
• Flavors of compressive sensing
• Equiangular tight frames that contain regular simplices
• Deterministic constructions of compressed sensing matrices based on codes

This page was built for publication: Explicit constructions of RIP matrices and related problems

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