Derandomized compressed sensing with nonuniform guarantees for _1 recovery

DOI10.1007/S00041-022-09934-6zbMATH Open1486.94025arXiv1912.12045OpenAlexW4220821976MaRDI QIDQ2124653FDOQ2124653

Charles Clum, Dustin G. Mixon

Publication date: 11 April 2022

Published in: The Journal of Fourier Analysis and Applications (Search for Journal in Brave)

Abstract: We extend the techniques of H"{u}gel, Rauhut and Strohmer (Found. Comput. Math., 2014) to show that for every $deltain(0,1]$, there exists an explicit random $mimesN$ partial Fourier matrix $A$ with $m=soperatornamepolylog(N/epsilon)$ and entropy $s^{d}eltaoperatornamepolylog(N/epsilon)$ such that for every $s$-sparse signal $xinmathbb{C}^N$, there exists an event of probability at least $1-epsilon$ over which $x$ is the unique minimizer of $|z{|}_1$ subject to $Az=Ax$. The bulk of our analysis uses tools from decoupling to estimate the extreme singular values of the submatrix of $A$ whose columns correspond to the support of $x$.

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

zbMATH Keywords

compressed sensingderandomization\(\ell_1\) minimization

Mathematics Subject Classification ID

Convex programming (90C25) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Cites Work

• Title not available (Why is that?)
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Extensions of Lipschitz mappings into a Hilbert space
• High-Dimensional Probability
• Probability Inequalities for Sums of Bounded Random Variables
• A simple proof of the restricted isometry property for random matrices
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• An Introduction to Matrix Concentration Inequalities
• Compressed sensing
• User-friendly tail bounds for sums of random matrices
• A mathematical introduction to compressive sensing
• Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing
• The road to deterministic matrices with the restricted isometry property
• Deterministic matrices matching the compressed sensing phase transitions of Gaussian random matrices
• The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing
• On sparse reconstruction from Fourier and Gaussian measurements
• Foundations of Cryptography
• An Improved Estimate in the Restricted Isometry Problem
• The restricted isometry property and its implications for compressed sensing
• Uniform uncertainty principle for Bernoulli and subgaussian ensembles
• Certifying the Restricted Isometry Property is Hard
• Living on the edge: phase transitions in convex programs with random data
• Chirp sensing codes: Deterministic compressed sensing measurements for fast recovery
• Deterministic constructions of compressed sensing matrices
• Suprema of chaos processes and the restricted isometry property
• Derandomizing restricted isometries via the Legendre symbol
• Explicit Matrices with the Restricted Isometry Property: Breaking the Square-Root Bottleneck
• Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes
• Breaking the k ² barrier for explicit RIP matrices
• Explicit constructions of RIP matrices and related problems
• Steiner equiangular tight frames
• Sharp RIP bound for sparse signal and low-rank matrix recovery
• Kirkman Equiangular Tight Frames and Codes
• Equiangular tight frames from Paley tournaments
• On the conditioning of random subdictionaries
• Compressed sensing with sparse binary matrices: instance optimal error guarantees in near-optimal time
• Remote sensing via \(\ell_1\)-minimization
• The Restricted Isometry Property of Subsampled Fourier Matrices
• Equiangular Tight Frames From Hyperovals
• Kesten-McKay law for random subensembles of Paley equiangular tight frames
• A Conditional Construction of Restricted Isometries
• Random Subsets of Structured Deterministic Frames have MANOVA Spectra

Cited In (8)

• Unbiasing in iterative reconstruction algorithms for discrete compressed sensing
• Non-uniform recovery guarantees for binary measurements and infinite-dimensional compressed sensing
• Dequantizing Compressed Sensing: When Oversampling and Non-Gaussian Constraints Combine
• Uniform Recovery Bounds for Structured Random Matrices in Corrupted Compressed Sensing
• Randomization of data acquisition and \(\ell_{1}\)-optimization (recognition with compression)
• Theory of compressive sensing via \(\ell_1\)-minimization: a non-RIP analysis and extensions
• On the Absence of Uniform Recovery in Many Real-World Applications of Compressed Sensing and the Restricted Isometry Property and Nullspace Property in Levels
• Asymptotic Achievability of the CramÉr–Rao Bound for Noisy Compressive Sampling

Uses Software

• JPEG2000

This page was built for publication: Derandomized compressed sensing with nonuniform guarantees for \(\ell_1\) recovery

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