Explicit constructions of RIP matrices and related problems
From MaRDI portal
(Redirected from Publication:635478)
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)- 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
- Compliant Ternary Matrices based on Restricted Isometry Property: Construction and Application to Image Retrieval
- A deterministic sparse FFT for functions with structured Fourier sparsity
- Packings in real projective spaces
- Deterministic constructions of compressed sensing matrices based on optimal codebooks and codes
- Construction of sparse binary sensing matrices using set systems
- 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 _1 recovery
- Explicit Construction of RIP Matrices Is Ramsey‐Hard
- New constructions of RIP matrices with fast multiplication and fewer rows
- Kesten-McKay law for random subensembles of Paley equiangular tight frames
- Breaking the k 2 barrier for explicit RIP matrices
- Steiner 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
- 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
- Deterministic convolutional compressed sensing matrices
- Coherence of sensing matrices coming from algebraic-geometric codes
- An analytic approach to cardinalities of sumsets
- Stability of the elastic net estimator
- Deletion correcting codes meet the Littlewood-Offord problem
- 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
- An asymptotic existence result on compressed sensing matrices
- Preserving injectivity under subgaussian mappings and its application to compressed sensing
- Stochastic Collocation vial1-Minimisation on Low Discrepancy Point Sets with Application to Uncertainty Quantification
- Deterministic construction of compressed sensing matrices with characters over finite fields
- Explicit RIP matrices: an update
- Group-theoretic constructions of erasure-robust frames
- Explicit universal sampling sets in finite vector spaces
- Side effects of learning from low-dimensional data embedded in a Euclidean space
- On the sparsity of Lasso minimizers in sparse data recovery
- Analysis of Termatiko sets in measurement matrices
- Welch bound-achieving compressed sensing matrices from optimal codebooks
- Computational complexity of certifying restricted isometry property
- 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
- Flexible construction of measurement matrices in compressed sensing based on extensions of incidence matrices of combinatorial designs
- Deterministic construction of compressed sensing matrices from codes
- On exact recovery of sparse vectors from linear measurements
- Deterministic sampling of sparse trigonometric polynomials
- Equiangular tight frames that contain regular simplices
- Frames as codes
- Flavors of compressive sensing
- Deterministic constructions of compressed sensing matrices based on codes
- Compressive time-of-flight 3D imaging using block-structured sensing matrices
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)
