Explicit matrices with the restricted isometry property: breaking the square-root bottleneck

DOI10.1007/978-3-319-16042-9_13MaRDI QIDQ3460841zbMATH OpenOpenAlexFDO

Authors Dustin G. Mixon

Publication date 8 January 2016

Published in Compressed Sensing and its Applications (Search for Journal in Brave)

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

zbMATH Keywords

compressed sensingrestricted isometry property (RIP)

Mathematics Subject Classification ID

Arithmetic combinatorics; higher degree uniformity (11B30) General harmonic expansions, frames (42C15) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: Matrices with the restricted isometry property (RIP) are of particular interest in compressed sensing. To date, the best known RIP matrices are constructed using random processes, while explicit constructions are notorious for performing at the "square-root bottleneck," i.e., they only accept sparsity levels on the order of the square root of the number of measurements. The only known explicit matrix which surpasses this bottleneck was constructed by Bourgain, Dilworth, Ford, Konyagin and Kutzarova. This chapter provides three contributions to further the groundbreaking work of Bourgain et al.: (i) we develop an intuition for their matrix construction and underlying proof techniques; (ii) we prove a generalized version of their main result; and (iii) we apply this more general result to maximize the extent to which their matrix construction surpasses the square-root bottleneck.

Recommendations

• Explicit constructions of RIP matrices and related problems
• Breaking the k ² barrier for explicit RIP matrices
• Explicit Construction of RIP Matrices Is Ramsey‐Hard
• New constructions of RIP matrices with fast multiplication and fewer rows
• The road to deterministic matrices with the restricted isometry property

Cites work

• A mathematical introduction to compressive sensing
• A simple proof of the restricted isometry property for random matrices
• Additive combinatorics
• Certifying the Restricted Isometry Property is Hard
• Chirp sensing codes: Deterministic compressed sensing measurements for fast recovery
• Deterministic constructions of compressed sensing matrices
• Explicit constructions of RIP matrices and related problems
• Lower bounds on the maximum cross correlation of signals (Corresp.)
• On a variant of sum-product estimates and explicit exponential sum bounds in prime fields
• Sharp RIP bound for sparse signal and low-rank matrix recovery
• Steiner equiangular tight frames
• The road to deterministic matrices with the restricted isometry property

Cited in

(11)

• Equiangular tight frames that contain regular simplices
• PROMP: a sparse recovery approach to lattice-valued signals
• Derandomized compressed sensing with nonuniform guarantees for _1 recovery
• On the restricted isometry property of the Paley matrix
• Group-theoretic constructions of erasure-robust frames
• Explicit RIP matrices: an update
• Derandomizing restricted isometries via the Legendre symbol
• Phase retrieval from Gabor measurements
• Breaking the k ² barrier for explicit RIP matrices
• Explicit constructions of RIP matrices and related problems
• Satisfying the restricted isometry property with the optimal number of rows and slightly less randomness

This page was built for publication: Explicit matrices with the restricted isometry property: breaking the square-root bottleneck

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