Compressed sensing with coherent and redundant dictionaries

DOI10.1016/J.ACHA.2010.10.002zbMATH Open1215.94026arXiv1005.2613OpenAlexW2103955025MaRDI QIDQ544040FDOQ544040

Authors: D. Needell, Paige Randall, Emmanuel J. Candès, Y. C. Eldar 

Publication date: 14 June 2011

Published in: Applied and Computational Harmonic Analysis (Search for Journal in Brave)

Abstract: This article presents novel results concerning the recovery of signals from undersampled data in the common situation where such signals are not sparse in an orthonormal basis or incoherent dictionary, but in a truly redundant dictionary. This work thus bridges a gap in the literature and shows not only that compressed sensing is viable in this context, but also that accurate recovery is possible via an L1-analysis optimization problem. We introduce a condition on the measurement/sensing matrix, which is a natural generalization of the now well-known restricted isometry property, and which guarantees accurate recovery of signals that are nearly sparse in (possibly) highly overcomplete and coherent dictionaries. This condition imposes no incoherence restriction on the dictionary and our results may be the first of this kind. We discuss practical examples and the implications of our results on those applications, and complement our study by demonstrating the potential of L1-analysis for such problems.

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

Recommendations

• Compressed Sensing and Redundant Dictionaries
• scientific article; zbMATH DE number 7128825
• Compressive sensing with redundant dictionaries and structured measurements
• Sparse signal recovery via non-convex optimization and overcomplete dictionaries
• Improved RIP conditions for compressed sensing with coherent tight frames

zbMATH Keywords

restricted isometry propertybasis pursuit\(\ell _{1}\)-minimization\(\ell _{1}\)-analysisredundant dictionaries

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Approximation with constraints (41A29) Sampling theory in information and communication theory (94A20) Numerical methods in Fourier analysis (65T99)

Cites Work

• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Enhancing sparsity by reweighted \(\ell _{1}\) minimization
• Title not available (Why is that?)
• Matching pursuits with time-frequency dictionaries
• Decoding by Linear Programming
• Stable signal recovery from incomplete and inaccurate measurements
• A simple proof of the restricted isometry property for random matrices
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit
• Compressed sensing
• Iterative hard thresholding for compressed sensing
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• Affine systems in \(L_ 2(\mathbb{R}^d)\): The analysis of the analysis operator
• Greed is Good: Algorithmic Results for Sparse Approximation
• Split Bregman methods and frame based image restoration
• Sparsest solutions of underdetermined linear systems via \( \ell _q\)-minimization for \(0<q\leqslant 1\)
• Gabor analysis and algorithms. Theory and applications
• New tight frames of curvelets and optimal representations of objects with piecewise C² singularities
• On sparse reconstruction from Fourier and Gaussian measurements
• The restricted isometry property and its implications for compressed sensing
• Uniform uncertainty principle for Bernoulli and subgaussian ensembles
• Compressed Sensing and Redundant Dictionaries
• Microlocal analysis of the geometric separation problem
• Analysis versus synthesis in signal priors
• Near-ideal model selection by \(\ell _{1}\) minimization
• New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
• Fast Discrete Curvelet Transforms
• Iterative thresholding algorithms
• Title not available (Why is that?)
• A note on guaranteed sparse recovery via \(\ell_1\)-minimization
• The fast Johnson-Lindenstrauss transform and approximate nearest neighbors
• Johnson-Lindenstrauss lemma for circulant matrices
• Improving the Thresholds of Sparse Recovery: An Analysis of a Two-Step Reweighted Basis Pursuit Algorithm
• Title not available (Why is that?)
• An almost optimal unrestricted fast Johnson-Lindenstrauss transform

Cited In (only showing first 100 items - show all)

• Sparse model uncertainties in compressed sensing with application to convolutions and sporadic communication
• Structured random measurements in signal processing
• Sharp recovery bounds for convex demixing, with applications
• The \( \ell _1 \)-analysis in phase retrieval with redundant dictionary
• Signal separation under coherent dictionaries and \(\ell_p\)-bounded noise
• Three stochastic measurement schemes for direction-of-arrival estimation using compressed sensing method
• Sparsity-Inducing Nonconvex Nonseparable Regularization for Convex Image Processing
• On sparse representation of analytic signal in Hardy space
• Local behavior of sparse analysis regularization: applications to risk estimation
• Coherence pattern-guided compressive sensing with unresolved grids
• Guarantees of total variation minimization for signal recovery
• Sparse recovery in probability via \(l_q\)-minimization with Weibull random matrices for \(0 < q\leq 1\)
• One condition for solution uniqueness and robustness of both \(\ell_1\)-synthesis and \(\ell_1\)-analysis minimizations
• A null space analysis of the \(\ell_1\)-synthesis method in dictionary-based compressed sensing
• Deconvolution under Poisson noise using exact data fidelity and synthesis or analysis sparsity priors
• Stable recovery of low-dimensional cones in Hilbert spaces: one RIP to rule them all
• Spark-level sparsity and the \(\ell_1\) tail minimization
• Compressed data separation via dual frames based split-analysis with Weibull matrices
• Low complexity regularization of linear inverse problems
• Spectral compressive sensing
• Solution of linear ill-posed problems using random dictionaries
• Decoupling noise and features via weighted \(\ell_1\)-analysis compressed sensing
• Theory and applications of compressed sensing
• Near oracle performance and block analysis of signal space greedy methods
• Robust analysis ℓ₁-recovery from Gaussian measurements and total variation minimization
• Greedy-like algorithms for the cosparse analysis model
• Perturbations of measurement matrices and dictionaries in compressed sensing
• Sparse recovery with coherent tight frames via analysis Dantzig selector and analysis LASSO
• Frames for compressed sensing using coherence
• An efficient algorithm for \(\ell_{0}\) minimization in wavelet frame based image restoration
• Optimal \(D\)-RIP bounds in compressed sensing
• Two are better than one: fundamental parameters of frame coherence
• Structure dependent sampling in compressed sensing: theoretical guarantees for tight frames
• Sampling and reconstruction of sparse signals on circulant graphs. An introduction to graph-FRI
• Compressive sensing of analog signals using discrete prolate spheroidal sequences
• Iterative re-weighted least squares algorithm for \(l_p\)-minimization with tight frame and \(0 < p \leq 1\)
• A unified framework for linear dimensionality reduction in L1
• Compressed sensing image restoration based on data-driven multi-scale tight frame
• On the decay of the smallest singular value of submatrices of rectangular matrices
• Optimizing excitation coil currents for advanced magnetorelaxometry imaging
• The restricted isometry property for random block diagonal matrices
• Cosparsity in Compressed Sensing
• Analysis \(\ell_1\)-recovery with frames and Gaussian measurements
• Title not available (Why is that?)
• Compressed sensing with coherent tight frames via \(l_q\)-minimization for \(0 < q \leq 1\)
• Computing sparse representation in a highly coherent dictionary based on difference of \(L_1\) and \(L_2\)
• Sampling in the analysis transform domain
• Stability and robustness of \(\ell_1\)-minimizations with Weibull matrices and redundant dictionaries
• Convex optimization in sums of Banach spaces
• The sparsity of LASSO-type minimizers
• Sparse approximation is provably hard under coherent dictionaries
• Structured overcomplete sparsifying transform learning with convergence guarantees and applications
• Sparse sensor placement optimization for classification
• Preserving injectivity under subgaussian mappings and its application to compressed sensing
• Dictionary-sparse recovery via thresholding-based algorithms
• On the null space property of \(l_q\)-minimization for \(0 < q \leq 1\) in compressed sensing
• Compressed sensing and dictionary learning
• Smoothed \(\ell_1\)-regularization-based line search for sparse signal recovery
• Templates for convex cone problems with applications to sparse signal recovery
• Stable recovery of analysis based approaches
• Compressive imaging and characterization of sparse light deflection maps
• Compressive sensing with redundant dictionaries and structured measurements
• Compressed Sensing and Redundant Dictionaries
• Flavors of compressive sensing
• A modified greedy analysis pursuit algorithm for the cosparse analysis model
• Image reconstruction using analysis model prior
• Greedy signal space methods for incoherence and beyond
• Frames and numerical approximation
• $\ell _0$ Minimization for wavelet frame based image restoration
• Multi-layer sparse coding: the holistic way
• Greedy approximate projection for magnetic resonance fingerprinting with partial volumes
• Stability of 1-bit compressed sensing in sparse data reconstruction
• Block-sparse recovery of semidefinite systems and generalized null space conditions
• Sparsity based methods for overparameterized variational problems
• Divide and conquer: an incremental sparsity promoting compressive sampling approach for polynomial chaos expansions
• A preconditioner for a primal-dual Newton conjugate gradient method for compressed sensing problems
• Sparse inverse problems over measures: equivalence of the conditional gradient and exchange methods
• Weighted \(\ell_p\) (\(0<p\le 1\)) minimization with non-uniform weights for sparse recovery under partial support information
• On collaborative compressive sensing systems: the framework, design, and algorithm
• Gradient flows and randomised thresholding: sparse inversion and classification
• Stability of \(l_q\)-analysis based dual frame with Weibull matrices for \(0<q\leq 1\)
• Title not available (Why is that?)
• Tight-frame-like analysis-sparse recovery using nontight sensing matrices
• Sparse recovery with coherent frames via \(\ell_{1-2}\)-analysis
• The core of a Grassmannian frame
• Bilevel Methods for Image Reconstruction
• Recovery error analysis of noisy measurement in compressed sensing
• Compressed data separation via \(\ell_q\)-split analysis with \(\ell_\infty\)-constraint
• A hybrid quasi-Newton projected-gradient method with application to lasso and basis-pursuit denoising
• Nonuniform recovery of fusion frame structured sparse signals
• On and Beyond Total Variation Regularization in Imaging: The Role of Space Variance
• Sparse phase retrieval via ℓp (0 < p ≤ 1) minimization
• Compressed data separation via unconstrained l1-split analysis
• Iterative gradient denoising algorithm for signal recovery using analysis-based implicit prior
• \(k\) block sparse vector recovery via block \(\ell_1-\ell_2\) minimization
• Application of ESN prediction model based on compressed sensing in stock market
• Performance analysis for unconstrained analysis based approaches
• Sparse recovery with general frame via general-dual-based analysis Dantzig selector
• Optimal RIP bounds for sparse signals recovery via \(\ell_p\) minimization
• Compressed sensing with frames and sparsity in levels class

Uses Software

• CoSaMP

This page was built for publication: Compressed sensing with coherent and redundant dictionaries

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