Explicit constructions of RIP matrices and related problems
From MaRDI portal
thin setsproduct setsspherical codeRestricted Isometry Property (RIP)RIP matricessmall Fourier coefficientssparse-signals recoverysumset estimatesTurán's power sum problem
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)
Abstract: We give a new explicit construction of 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)}.
Recommendations
- Breaking the k 2 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
Cites work
- scientific article; zbMATH DE number 3865403 (Why is no real title available?)
- scientific article; zbMATH DE number 3756556 (Why is no real title available?)
- scientific article; zbMATH DE number 699709 (Why is no real title available?)
- scientific article; zbMATH DE number 2079345 (Why is no real title available?)
- scientific article; zbMATH DE number 3373547 (Why is no real title available?)
- A probabilistic approach to problems of diophantine approximation
- A simple proof of the restricted isometry property for random matrices
- A theorem on cubes
- Additive combinatorics
- An Estimate for Character Sums
- Approximate formulas for some functions of prime numbers
- Constructing Small Sets that are Uniform in Arithmetic Progressions
- Constructing small-bias sets from algebraic-geometric codes
- Construction of a Thin Set with small Fourier Coefficients
- Decoding by Linear Programming
- Deterministic constructions of compressed sensing matrices
- Explicit solutions to certain inf max problems from Turán power sum theory
- Exponential sum estimates over a subgroup in an arbitrary finite field
- Extensions of Lipschitz mappings into a Hilbert space
- List decoding algorithms for certain concatenated codes
- Multilinear exponential sums in prime fields under optimal entropy condition on the sources
- Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
- On Lebesgue-type inequalities for greedy approximation
- On a variant of sum-product estimates and explicit exponential sum bounds in prime fields
- On sparse reconstruction from Fourier and Gaussian measurements
- On the optimality of the orthogonal greedy algorithm for \(\mu\)-coherent dictionaries
- On the size of incoherent systems
- On the solutions to a power sum problem
- Reconstruction and subgaussian operators in asymptotic geometric analysis
- Simple Constructions of Almost k-wise Independent Random Variables
- Some extremal properties of trigonometric sums
- Stable signal recovery from incomplete and inaccurate measurements
- Sums in the grid
- The Orthogonal Super Greedy Algorithm and Applications in Compressed Sensing
- The restricted isometry property and its implications for compressed sensing
- Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit
Cited in
(60)- 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
- Theory and applications of compressed sensing
- Compressive Sensing
- Group-theoretic constructions of erasure-robust frames
- A deterministic sparse FFT for functions with structured Fourier sparsity
- Fast and RIP-optimal transforms
- Sergei Vladimirovich Konyagin turns 60
- Deterministic construction of compressed sensing matrices based on semilattices
- Preserving injectivity under subgaussian mappings and its application to compressed sensing
- Deterministic construction of compressed sensing matrices from codes
- Sparse recovery in bounded Riesz systems with applications to numerical methods for PDEs
- Frames as codes
- Book Review: A mathematical introduction to compressive sensing
- Welch bound-achieving compressed sensing matrices from optimal codebooks
- Kesten-McKay law for random subensembles of Paley equiangular tight frames
- On the sparsity of Lasso minimizers in sparse data recovery
- Side effects of learning from low-dimensional data embedded in a Euclidean space
- Explicit matrices with the restricted isometry property: breaking the square-root bottleneck
- The road to deterministic matrices with the restricted isometry property
- Additive combinatorics: with a view towards computer science and cryptography -- an exposition
- Mathematics of analog-to-digital conversion
- Flexible construction of measurement matrices in compressed sensing based on extensions of incidence matrices of combinatorial designs
- Deterministic matrices matching the compressed sensing phase transitions of Gaussian random matrices
- An analytic approach to cardinalities of sumsets
- An evaluation of the sparsity degree for sparse recovery with deterministic measurement matrices
- Derandomized compressed sensing with nonuniform guarantees for \(\ell_1\) recovery
- Flavors of compressive sensing
- On exact recovery of sparse vectors from linear measurements
- Deterministic construction of compressed sensing matrices from constant dimension codes
- Deterministic sampling of sparse trigonometric polynomials
- Deletion correcting codes meet the Littlewood-Offord problem
- Stability of the elastic net estimator
- Steiner equiangular tight frames
- Multivariable polynomials for the construction of binary sensing matrices
- Explicit RIP matrices: an update
- Deterministic constructions of compressed sensing matrices based on codes
- Computational complexity of certifying restricted isometry property
- Analysis of Termatiko sets in measurement matrices
- On the restricted isometry property of the Paley matrix
- Stochastic Collocation vial1-Minimisation on Low Discrepancy Point Sets with Application to Uncertainty Quantification
- Equiangular tight frames that contain regular simplices
- New constructions of RIP matrices with fast multiplication and fewer rows
- An asymptotic existence result on compressed sensing matrices
- Explicit universal sampling sets in finite vector spaces
- Deterministic convolutional compressed sensing matrices
- Construction of sparse binary sensing matrices using set systems
- Coherence of sensing matrices coming from algebraic-geometric codes
- Using elimination theory to construct rigid matrices
- A novel probabilistic approach for vehicle position prediction in free, partial, and full GPS outages
- 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
- Deterministic construction of compressed sensing matrices with characters over finite fields
- Derandomizing restricted isometries via the Legendre symbol
- Mathematics of electron tomography
- Newly deterministic construction of compressed sensing matrices via singular linear spaces over finite fields
- Breaking the k 2 barrier for explicit RIP matrices
- An Unbiased Approach to Low Rank Recovery
- Packings in real projective spaces
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)
