Compressed sensing with coherent and redundant dictionaries

DOI10.1016/j.acha.2010.10.002zbMath1215.94026arXiv1005.2613MaRDI 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 property; basis pursuit; \(\ell _{1}\)-minimization; \(\ell _{1}\)-analysis; redundant dictionaries

Mathematics Subject Classification ID

94A12: Signal theory (characterization, reconstruction, filtering, etc.)

41A29: Approximation with constraints

94A20: Sampling theory in information and communication theory

65T99: Numerical methods in Fourier analysis

Related Items

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

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