Compressed Sensing and Redundant Dictionaries

Abstract

This article extends the concept of compressed sensing to signals that are not sparse in an orthonormal basis but rather in a redundant dictionary. It is shown that a matrix, which is a composition of a random matrix of certain type and a deterministic dictionary, has small restricted isometry constants. Thus, signals that are sparse with respect to the dictionary can be recovered via Basis Pursuit from a small number of random measurements. Further, thresholding is investigated as recovery algorithm for compressed sensing and conditions are provided that guarantee reconstruction with high probability. The different schemes are compared by numerical experiments.

error in a constant corrected

References in corpus (2)

• Sparse reconstruction by convex relaxation: Fourier and Gaussian measurements
• Counting faces of randomly-projected polytopes when the projection radically lowers dimension

Cited by in corpus (87)

• Compressed sensing imaging techniques for radio interferometry
• Necessary and Sufficient Conditions on Sparsity Pattern Recovery
• Ranking Based Locality Sensitive Hashing Enabled Cancelable Biometrics: Index-of-Max Hashing
• Asymptotic Analysis of MAP Estimation via the Replica Method and Applications to Compressed Sensing
• Sparsity Averaging Reweighted Analysis (SARA): a novel algorithm for radio-interferometric imaging
• PURIFY: a new approach to radio-interferometric imaging
• Greedy-Like Algorithms for the Cosparse Analysis Model
• Covariance Estimation in High Dimensions via Kronecker Product Expansions
• Projection Design For Statistical Compressive Sensing: A Tight Frame Based Approach
• Fundamental performance limits for ideal decoders in high-dimensional linear inverse problems
• Rakeness in the design of Analog-to-Information Conversion of Sparse and Localized Signals
• Sparsity Averaging for Compressive Imaging
• Splines are Universal Solutions of Linear Inverse Problems with Generalized-TV regularization
• Identification of Matrices having a Sparse Representation
• ${\ell }^1$-Analysis Minimization and Generalized (Co-)Sparsity: When Does Recovery Succeed?
• On-Off Random Access Channels: A Compressed Sensing Framework
• Compressed Sensing with General Frames via Optimal-dual-based ${\ell }_1$-analysis
• A Non-Local Structure Tensor Based Approach for Multicomponent Image Recovery Problems
• The restricted isometry property for time-frequency structured random matrices
• Restricted Isometries for Partial Random Circulant Matrices
• Spread spectrum for imaging techniques in radio interferometry
• Compressive Source Separation: Theory and Methods for Hyperspectral Imaging
• Compressive Parameter Estimation for Sparse Translation-Invariant Signals Using Polar Interpolation
• Continuous-Domain Solutions of Linear Inverse Problems with Tikhonov vs. Generalized TV Regularization
• Exploiting Restricted Boltzmann Machines and Deep Belief Networks in Compressed Sensing
• Dense Quantum Measurement Theory
• A Geometrical Study of Matching Pursuit Parametrization
• High Speed Compressed Sensing Reconstruction in Dynamic Parallel MRI Using Augmented Lagrangian and Parallel Processing
• High-Dimensional Estimation of Structured Signals from Non-Linear Observations with General Convex Loss Functions
• The Benefit of Group Sparsity
• Sparse Representation of Astronomical Images
• Quasi-Linear Compressed Sensing
• Multipliers for p-Bessel sequences in Banach spaces
• Fast Algorithms for Demixing Sparse Signals from Nonlinear Observations
• Distributed Representation of Geometrically Correlated Images with Compressed Linear Measurements
• Sample Complexity of Total Variation Minimization
• Sequential adaptive compressed sampling via Huffman codes
• Dictionary Learning Based Sparse Channel Representation and Estimation for FDD Massive MIMO Systems
• Exact Recovery of Sparse Signals via Orthogonal Matching Pursuit: How Many Iterations Do We Need?
• Ranked Sparse Signal Support Detection
• Compressive sensing: a paradigm shift in signal processing
• Guarantees of Total Variation Minimization for Signal Recovery
• Quantum matching pursuit: A quantum algorithm for sparse representations
• Sparsity in time-frequency representations
• A Practical Study of Longitudinal Reference Based Compressed Sensing for MRI
• Utilizing the Structure of the Curvelet Transform with Compressed Sensing
• Performance of Compressive Parameter Estimation via K-Median Clustering
• Sparse Legendre expansions via ${\ell }_1$ minimization
• Average Case Analysis of Multichannel Sparse Recovery Using Convex Relaxation
• Regularity Properties for Sparse Regression
• Spectral Compressive Sensing with Polar Interpolation
• IoT Random Access in Massive MIMO: Exploiting Diversity in Sensing Matrices
• A null space analysis of the L1 synthesis method in dictionary-based compressed sensing
• Compressive Sensing with Redundant Dictionaries and Structured Measurements
• Enhanced Expressive Power and Fast Training of Neural Networks by Random Projections
• A null space property approach to compressed sensing with frames
• Partial Gaussian Graphical Model Estimation
• A Compressed Sampling and Dictionary Learning Framework for WDM-Based Distributed Fiber Sensing
• Generalized Inpainting Method for Hyperspectral Image Acquisition
• Dequantizing Compressed Sensing: When Oversampling and Non-Gaussian Constraints Combine
• Sparse Recovery with Coherent Tight Frames via Analysis Dantzig Selector and Analysis LASSO
• Near Oracle Performance and Block Analysis of Signal Space Greedy Methods
• Separation of undersampled composite signals using the Dantzig selector with overcomplete dictionaries
• On sparsity averaging
• Sparsification of Matrices and Compressed Sensing
• Local sparsity and recovery of fusion frames structured signals
• On the relation of the frame-related operators of fusion frame systems
• Sparse and redundant signal representations for x-ray computed tomography
• Oblique Pursuits for Compressed Sensing
• Compressed Sensing with coherent tight frames via $l_q$-minimization for $0<q\le 1$
• The restricted isometry property meets nonlinear approximation with redundant frames
• Can we allow linear dependencies in the dictionary in the sparse synthesis framework?
• Optimal Non-Linear Models for Sparsity and Sampling
• Sampling and reconstructing signals from a union of linear subspaces
• On Random Construction of a Bipolar Sensing Matrix with Compact Representation
• Linear Transformations and Restricted Isometry Property
• Stable Embedding of Grassmann Manifold via Gaussian Random matrices
• Thresholding-based reconstruction of compressed correlated signals
• Basic Thresholding Classification
• Performance Analysis of ${\ell }_1$-synthesis with Coherent Frames
• Spark Level Sparsity and the ${\ell }_1$ Tail Minimization
• Dictionary Learning Strategies for Compressed Fiber Sensing Using a Probabilistic Sparse Model
• Fast Fourier-Based Generation of the Compression Matrix for Deterministic Compressed Sensing
• The ${\ell }_1$-analysis with redundant dictionary in phase retrieval
• Dictionary for Sparse Representation of Chirp Echo in Broadband Radar
• A Novel Compressive Sensing based Enhanced Multiplexing Scheme for MIMO System
• Structure dependent sampling in compressed sensing: theoretical guarantees for tight frames