Compressive sensing with redundant dictionaries and structured measurements

DOI10.1137/151005245zbMATH Open1345.94014arXiv1501.03208OpenAlexW2568623927MaRDI QIDQ3455237FDOQ3455237

Authors: Felix Krahmer, D. Needell, Rachel Ward 

Publication date: 4 December 2015

Published in: SIAM Journal on Mathematical Analysis (Search for Journal in Brave)

Abstract: Consider the problem of recovering an unknown signal from undersampled measurements, given the knowledge that the signal has a sparse representation in a specified dictionary $D$. This problem is now understood to be well-posed and efficiently solvable under suitable assumptions on the measurements and dictionary, if the number of measurements scales roughly with the sparsity level. One sufficient condition for such is the $D$-restricted isometry property ($D$-RIP), which asks that the sampling matrix approximately preserve the norm of all signals which are sufficiently sparse in $D$. While many classes of random matrices are known to satisfy such conditions, such matrices are not representative of the structural constraints imposed by practical sensing systems. We close this gap in the theory by demonstrating that one can subsample a fixed orthogonal matrix in such a way that the $D$-RIP will hold, provided this basis is sufficiently incoherent with the sparsifying dictionary $D$. We also extend this analysis to allow for weighted sparse expansions. Consequently, we arrive at compressive sensing recovery guarantees for structured measurements and redundant dictionaries, opening the door to a wide array of practical applications.

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

Recommendations

• Compressed Sensing and Redundant Dictionaries
• Compressed sensing with coherent and redundant dictionaries
• Perturbations of measurement matrices and dictionaries in compressed sensing
• The restricted isometry property for random block diagonal matrices
• Sparse signal recovery via non-convex optimization and overcomplete dictionaries

zbMATH Keywords

compressive sensingrestricted isometry propertyredundant dictionaries

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Trigonometric approximation (42A10) Approximation by arbitrary linear expressions (41A45)

Cites Work

• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Title not available (Why is that?)
• An elementary proof of a theorem of Johnson and Lindenstrauss
• Decoding by Linear Programming
• A simple proof of the restricted isometry property for random matrices
• Compressed sensing
• Stable image reconstruction using total variation minimization
• A mathematical introduction to compressive sensing
• Sparse Legendre expansions via \(\ell_1\)-minimization
• A Probabilistic and RIPless Theory of Compressed Sensing
• Sparsity and incoherence in compressive sampling
• Tight frames and their symmetries
• New tight frames of curvelets and optimal representations of objects with piecewise C² singularities
• A framelet-based image inpainting algorithm
• On sparse reconstruction from Fourier and Gaussian measurements
• Stable and Robust Sampling Strategies for Compressive Imaging
• The cosparse analysis model and algorithms
• Performance Guarantees of the Thresholding Algorithm for the Cosparse Analysis Model
• Compressed Sensing and Redundant Dictionaries
• Super-resolution from noisy data
• Analysis versus synthesis in signal priors
• Signal Space CoSaMP for Sparse Recovery With Redundant Dictionaries
• Towards a Mathematical Theory of Super‐resolution
• Sparse directional image representations using the discrete shearlet transform
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• Deterministic constructions of compressed sensing matrices
• Suprema of chaos processes and the restricted isometry property
• New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
• Restricted isometry of Fourier matrices and list decodability of random linear codes
• The sizes of compact subsets of Hilbert space and continuity of Gaussian processes
• Title not available (Why is that?)
• Compressive sensing and structured random matrices
• Compressed sensing with coherent and redundant dictionaries
• Analysis \(\ell_1\)-recovery with frames and Gaussian measurements
• Restricted isometries for partial random circulant matrices
• Interpolation via weighted \(\ell_{1}\) minimization
• Compressive sampling of polynomial chaos expansions: convergence analysis and sampling strategies
• High-Resolution Radar via Compressed Sensing
• Inequalities of Bernstein-Jackson-type and the degree of compactness of operators in Banach spaces
• On the Effective Measure of Dimension in the Analysis Cosparse Model
• Constructing tight fusion frames
• Optimally Sparse Frames
• The fast Johnson-Lindenstrauss transform and approximate nearest neighbors
• Breaking the coherence barrier: a new theory for compressed sensing
• Johnson-Lindenstrauss lemma for circulant matrices
• Sparse Estimation of Spectral Lines: Grid Selection Problems and Their Solutions
• Compressed Sensing With General Frames via Optimal-Dual-Based $\ell _{1}$-Analysis
• Near oracle performance and block analysis of signal space greedy methods
• Greedy-like algorithms for the cosparse analysis model
• Structure dependent sampling in compressed sensing: theoretical guarantees for tight frames
• Title not available (Why is that?)
• Near-Optimal Compressed Sensing Guarantees for Total Variation Minimization
• Greedy signal space methods for incoherence and beyond
• Weighted eigenfunction estimates with applications to compressed sensing
• Sampling in the analysis transform domain
• On the role of total variation in compressed sensing

Cited In (17)

• New analysis of manifold embeddings and signal recovery from compressive measurements
• Title not available (Why is that?)
• Tight-frame-like analysis-sparse recovery using nontight sensing matrices
• Perturbations of measurement matrices and dictionaries in compressed sensing
• Structure dependent sampling in compressed sensing: theoretical guarantees for tight frames
• Compressive sensing of analog signals using discrete prolate spheroidal sequences
• Compressed sensing with coherent and redundant dictionaries
• Compressed sensing with frames and sparsity in levels class
• Compressed sensing of data with a known distribution
• \(\ell^1\)-analysis minimization and generalized (co-)sparsity: when does recovery succeed?
• Preserving injectivity under subgaussian mappings and its application to compressed sensing
• Theoretical guarantees for graph sparse coding
• Sampling rates for \(\ell^1\)-synthesis
• Compressed sensing with structured sparsity and structured acquisition
• Infinite dimensional compressed sensing from anisotropic measurements and applications to inverse problems in PDE
• Compressed Sensing and Redundant Dictionaries
• Compressive time-of-flight 3D imaging using block-structured sensing matrices

Uses Software

• CoSaMP

This page was built for publication: Compressive sensing with redundant dictionaries and structured measurements

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