Compressed sensing with coherent and redundant dictionaries

DOI10.1016/J.ACHA.2010.10.002zbMath1215.94026arXiv1005.2613OpenAlexW2103955025MaRDI QIDQ544040

Paige Randall, Deanna Needell, Emmanuel J. Candès, Yonina C. Eldar

Publication date: 14 June 2011

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

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

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)

Related Items (only showing first 100 items - show all)

WARPd: A Linearly Convergent First-Order Primal-Dual Algorithm for Inverse Problems with Approximate Sharpness Conditions ⋮ Structure dependent sampling in compressed sensing: theoretical guarantees for tight frames ⋮ One condition for solution uniqueness and robustness of both \(\ell_1\)-synthesis and \(\ell_1\)-analysis minimizations ⋮ A unified framework for linear dimensionality reduction in L1 ⋮ A Preconditioner for A Primal-Dual Newton Conjugate Gradient Method for Compressed Sensing Problems ⋮ Sparsity Based Methods for Overparameterized Variational Problems ⋮ Compressive Sensing with Redundant Dictionaries and Structured Measurements ⋮ Compressed sensing image restoration based on data-driven multi-scale tight frame ⋮ Gradient flows and randomised thresholding: sparse inversion and classification* ⋮ On the decay of the smallest singular value of submatrices of rectangular matrices ⋮ THE RESTRICTED ISOMETRY PROPERTY FOR SIGNAL RECOVERY WITH COHERENT TIGHT FRAMES ⋮ Sparse phase retrieval via ℓp (0 < p ≤ 1) minimization ⋮ Sparse Model Uncertainties in Compressed Sensing with Application to Convolutions and Sporadic Communication ⋮ Cosparsity in Compressed Sensing ⋮ Sparse signal recovery via non-convex optimization and overcomplete dictionaries ⋮ Sparse approximation is provably hard under coherent dictionaries ⋮ Compressive Imaging and Characterization of Sparse Light Deflection Maps ⋮ Learning probabilistic neural representations with randomly connected circuits ⋮ Recovery error analysis of noisy measurement in compressed sensing ⋮ \(\ell^1\)-analysis minimization and generalized (co-)sparsity: when does recovery succeed? ⋮ Improved RIP conditions for compressed sensing with coherent tight frames ⋮ A hybrid quasi-Newton projected-gradient method with application to lasso and basis-pursuit denoising ⋮ Convex optimization in sums of Banach spaces ⋮ Performance analysis for unconstrained analysis based approaches* ⋮ Robust recovery of a kind of weighted l1-minimization without noise level ⋮ Sharp recovery bounds for convex demixing, with applications ⋮ Iterative hard thresholding for compressed data separation ⋮ Alternating forward-backward splitting for linearly constrained optimization problems ⋮ Robust analysis ℓ₁-recovery from Gaussian measurements and total variation minimization ⋮ Analysis non-sparse recovery for relaxed ALASSO ⋮ Stability of lq-analysis based dual frame with Weibull matrices for 0 < q ≤ 1 ⋮ Global Optimality in Separable Dictionary Learning with Applications to the Analysis of Diffusion MRI ⋮ Sampling in the analysis transform domain ⋮ Block-sparse recovery of semidefinite systems and generalized null space conditions ⋮ Analysis \(\ell_1\)-recovery with frames and Gaussian measurements ⋮ An efficient algorithm for \(\ell_{0}\) minimization in wavelet frame based image restoration ⋮ Two are better than one: fundamental parameters of frame coherence ⋮ Guarantees of total variation minimization for signal recovery ⋮ Time for dithering: fast and quantized random embeddings via the restricted isometry property ⋮ Smoothed \(\ell_1\)-regularization-based line search for sparse signal recovery ⋮ Adaptive iterative hard thresholding for low-rank matrix recovery and rank-one measurements ⋮ Flavors of Compressive Sensing ⋮ Stability and robustness of \(\ell_1\)-minimizations with Weibull matrices and redundant dictionaries ⋮ Greedy-like algorithms for the cosparse analysis model ⋮ Perturbations of measurement matrices and dictionaries in compressed sensing ⋮ Compressive sensing of analog signals using discrete prolate spheroidal sequences ⋮ Stability of 1-bit compressed sensing in sparse data reconstruction ⋮ The restricted isometry property for random block diagonal matrices ⋮ Signal separation under coherent dictionaries and \(\ell_p\)-bounded noise ⋮ Compressed sensing with coherent tight frames via \(l_q\)-minimization for \(0 < q \leq 1\) ⋮ On the null space property of \(l_q\)-minimization for \(0 < q \leq 1\) in compressed sensing ⋮ Computing sparse representation in a highly coherent dictionary based on difference of \(L_1\) and \(L_2\) ⋮ Sparse recovery in probability via \(l_q\)-minimization with Weibull random matrices for \(0 < q\leq 1\) ⋮ Stable recovery of low-dimensional cones in Hilbert spaces: one RIP to rule them all ⋮ Spark-level sparsity and the \(\ell_1\) tail minimization ⋮ A modified greedy analysis pursuit algorithm for the cosparse analysis model ⋮ Fast and provable algorithms for spectrally sparse signal reconstruction via low-rank Hankel matrix completion ⋮ The \( \ell _1 \)-analysis in phase retrieval with redundant dictionary ⋮ $\ell _0$ Minimization for wavelet frame based image restoration ⋮ Image reconstruction using analysis model prior ⋮ Spectral compressive sensing ⋮ Local behavior of sparse analysis regularization: applications to risk estimation ⋮ Sparse recovery with coherent tight frames via analysis Dantzig selector and analysis LASSO ⋮ Templates for convex cone problems with applications to sparse signal recovery ⋮ Compressed data separation via dual frames based split-analysis with Weibull matrices ⋮ Deconvolution under Poisson noise using exact data fidelity and synthesis or analysis sparsity priors ⋮ Iterative re-weighted least squares algorithm for \(l_p\)-minimization with tight frame and \(0 < p \leq 1\) ⋮ Solution of linear ill-posed problems using random dictionaries ⋮ On Collaborative Compressive Sensing Systems: The Framework, Design, and Algorithm ⋮ Low Complexity Regularization of Linear Inverse Problems ⋮ Application of ESN prediction model based on compressed sensing in stock market ⋮ Structured overcomplete sparsifying transform learning with convergence guarantees and applications ⋮ A null space analysis of the \(\ell_1\)-synthesis method in dictionary-based compressed sensing ⋮ An extended DEIM algorithm for subset selection and class identification ⋮ Optimizing excitation coil currents for advanced magnetorelaxometry imaging ⋮ Greedy approximate projection for magnetic resonance fingerprinting with partial volumes ⋮ Adaptive dimension-discriminative low-rank tensor recovery for computational hyperspectral imaging ⋮ Divide and conquer: an incremental sparsity promoting compressive sampling approach for polynomial chaos expansions ⋮ Inpainting via sparse recovery with directional constraints ⋮ A note on block-sparse signal recovery with coherent tight frames ⋮ Decoupling noise and features via weighted ℓ ₁ -analysis compressed sensing ⋮ Structured random measurements in signal processing ⋮ Sparse Sensor Placement Optimization for Classification ⋮ Sparse Inverse Problems over Measures: Equivalence of the Conditional Gradient and Exchange Methods ⋮ Overcomplete representation in a hierarchical Bayesian framework ⋮ Two-stage geometric information guided image reconstruction ⋮ Preserving injectivity under subgaussian mappings and its application to compressed sensing ⋮ ℓ ₁ − αℓ ₂ minimization methods for signal and image reconstruction with impulsive noise removal ⋮ Sampling and reconstruction of sparse signals on circulant graphs. An introduction to graph-FRI ⋮ Optimal RIP bounds for sparse signals recovery via \(\ell_p\) minimization ⋮ Theory and applications of compressed sensing ⋮ Near oracle performance and block analysis of signal space greedy methods ⋮ The sparsity of LASSO-type minimizers ⋮ On sparse representation of analytic signal in Hardy space ⋮ Greedy signal space methods for incoherence and beyond ⋮ Stable recovery of analysis based approaches ⋮ Multi-Layer Sparse Coding: The Holistic Way ⋮ Optimal \(D\)-RIP bounds in compressed sensing ⋮ Weighted \(\ell_p\) (\(0<p\le 1\)) minimization with non-uniform weights for sparse recovery under partial support information ⋮ Three stochastic measurement schemes for direction-of-arrival estimation using compressed sensing method

Uses Software

• CoSaMP

Cites Work

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

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