Model-Based Compressive Sensing

Abstract

Compressive sensing (CS) is an alternative to Shannon/Nyquist sampling for the acquisition of sparse or compressible signals that can be well approximated by just K << N elements from an N-dimensional basis. Instead of taking periodic samples, CS measures inner products with M < N random vectors and then recovers the signal via a sparsity-seeking optimization or greedy algorithm. Standard CS dictates that robust signal recovery is possible from M = O(K log(N/K)) measurements. It is possible to substantially decrease M without sacrificing robustness by leveraging more realistic signal models that go beyond simple sparsity and compressibility by including structural dependencies between the values and locations of the signal coefficients. This paper introduces a model-based CS theory that parallels the conventional theory and provides concrete guidelines on how to create model-based recovery algorithms with provable performance guarantees. A highlight is the introduction of a new class of structured compressible signals along with a new sufficient condition for robust structured compressible signal recovery that we dub the restricted amplification property, which is the natural counterpart to the restricted isometry property of conventional CS. Two examples integrate two relevant signal models - wavelet trees and block sparsity - into two state-of-the-art CS recovery algorithms and prove that they offer robust recovery from just M=O(K) measurements. Extensive numerical simulations demonstrate the validity and applicability of our new theory and algorithms.

20 pages, 10 figures. Typo corrected in grant number. To appear in IEEE Transactions on Information Theory

Cited by in corpus (110)

• Compressed Sensing of Block-Sparse Signals: Uncertainty Relations and Efficient Recovery
• Structured Compressed Sensing: From Theory to Applications
• Sparse Signal Recovery with Temporally Correlated Source Vectors Using Sparse Bayesian Learning
• Distributed Compressive CSIT Estimation and Feedback for FDD Multi-user Massive MIMO Systems
• Extension of SBL Algorithms for the Recovery of Block Sparse Signals with Intra-Block Correlation
• Data-Driven Sparse Sensor Placement for Reconstruction
• DR2-Net: Deep Residual Reconstruction Network for Image Compressive Sensing
• Compressed Sensing for Energy-Efficient Wireless Telemonitoring of Noninvasive Fetal ECG via Block Sparse Bayesian Learning
• AMP-Net: Denoising based Deep Unfolding for Compressive Image Sensing
• A Unified Framework for High-Dimensional Analysis of M-Estimators with Decomposable Regularizers
• This is SPIRAL-TAP: Sparse Poisson Intensity Reconstruction ALgorithms - Theory and Practice
• Compressed Sensing of EEG for Wireless Telemonitoring with Low Energy Consumption and Inexpensive Hardware
• Structured Compressive Sensing Based Spatio-Temporal Joint Channel Estimation for FDD Massive MIMO
• Compressive Imaging using Approximate Message Passing and a Markov-Tree Prior
• Efficient measurement of quantum dynamics via compressive sensing
• Subspace Methods for Joint Sparse Recovery
• Enhancing ${\ell }_1$-minimization estimates of polynomial chaos expansions using basis selection
• Robustly Stable Signal Recovery in Compressed Sensing with Structured Matrix Perturbation
• Regime Change: Bit-Depth versus Measurement-Rate in Compressive Sensing
• Distributed Compressive Sensing: A Deep Learning Approach
• Exploiting Statistical Dependencies in Sparse Representations for Signal Recovery
• Compressive sensing and low-rank libraries for classification of bifurcation regimes in nonlinear dynamical systems
• Measure What Should be Measured: Progress and Challenges in Compressive Sensing
• Approximate message-passing decoder and capacity-achieving sparse superposition codes
• Sparsity Learning Based Multiuser Detection in Grant-Free Massive-Device Multiple Access
• Two-Dimensional Pattern-Coupled Sparse Bayesian Learning via Generalized Approximate Message Passing
• Learning-based Compressive Subsampling
• Image Compressed Sensing Using Non-local Neural Network
• Exploiting Prior Knowledge in Compressed Sensing Wireless ECG Systems
• Projection Design For Statistical Compressive Sensing: A Tight Frame Based Approach
• Bayesian 3D Reconstruction of Complex Scenes from Single-Photon Lidar Data
• Statistical Compressed Sensing of Gaussian Mixture Models
• Compressive Imaging via Approximate Message Passing with Image Denoising
• Recursive Recovery of Sparse Signal Sequences from Compressive Measurements: A Review
• Block-Sparsity-Induced Adaptive Filter for Multi-Clustering System Identification
• Regularized Modified BPDN for Noisy Sparse Reconstruction with Partial Erroneous Support and Signal Value Knowledge
• Deep Learning Methods for Solving Linear Inverse Problems: Research Directions and Paradigms
• Reconciling Compressive Sampling Systems for Spectrally-sparse Continuous-time Signals
• Lorentzian Iterative Hard Thresholding: Robust Compressed Sensing with Prior Information
• Graph topology inference based on sparsifying transform learning
• Nonlinear Model Reduction for Complex Systems using Sparse Optimal Sensor Locations from Learned Nonlinear Libraries
• From Sparse Signals to Sparse Residuals for Robust Sensing
• Near-Oracle Performance of Greedy Block-Sparse Estimation Techniques from Noisy Measurements
• Communications-Inspired Projection Design with Application to Compressive Sensing
• Joint Channel Estimation and User Grouping for Massive MIMO Systems
• Sparse Recovery from Combined Fusion Frame Measurements
• Sampling and Recovery of Pulse Streams
• Reconstruction of Signals Drawn from a Gaussian Mixture from Noisy Compressive Measurements
• Compressed Sensing with 1D Total Variation: Breaking Sample Complexity Barriers via Non-Uniform Recovery
• Classification and Reconstruction of High-Dimensional Signals from Low-Dimensional Features in the Presence of Side Information
• Group Sparse Recovery via the ${\ell }^0({\ell }^2)$ Penalty: Theory and Algorithm
• The benefits of acting locally: Reconstruction algorithms for sparse in levels signals with stable and robust recovery guarantees
• Combining physics-based and data-driven models: advancing the frontiers of research with Scientific Machine Learning
• Learning Model-Based Sparsity via Projected Gradient Descent
• Theoretical Analysis for Extended Target Recovery in Randomized Stepped Frequency Radars
• Measurement Bounds for Sparse Signal Ensembles via Graphical Models
• Polynomial Fourier Domain as a Domain of Signal Sparsity
• Interplay of Sensor Quantity, Placement and System Dimensionality on Energy Sparse Reconstruction of Fluid Flows
• Compressive Phase Retrieval via Reweighted Amplitude Flow
• Forest Sparsity for Multi-channel Compressive Sensing
• A Constrained Random Demodulator for Sub-Nyquist Sampling
• Reliable recovery of hierarchically sparse signals for Gaussian and Kronecker product measurements
• High-Dimensional Estimation of Structured Signals from Non-Linear Observations with General Convex Loss Functions
• Bounds on the Number of Measurements for Reliable Compressive Classification
• Sparse Poisson Intensity Reconstruction Algorithms
• Channel Estimation and Hybrid Precoding for Distributed Phased Arrays Based MIMO Wireless Communications
• A compressive channel estimation technique robust to synchronization impairments
• Single-Photon Depth Imaging Using a Union-of-Subspaces Model
• Structure-Based Bayesian Sparse Reconstruction
• An exact tree projection algorithm for wavelets
• Improving M-SBL for Joint Sparse Recovery using a Subspace Penalty
• Exploiting Prior Information in Block Sparse Signals
• Binary Compressive Sensing via Analog Fountain Coding
• Conditioning of Random Block Subdictionaries with Applications to Block-Sparse Recovery and Regression
• Sparse Convolution-based Markov Models for Nonlinear Fluid Flows
• Accuracy guaranties for ${\ell }_1$ recovery of block-sparse signals
• Semi-device-dependent blind quantum tomography
• Nest-DGIL: Nesterov-optimized Deep Geometric Incremental Learning for CS Image Reconstruction
• Exact Reconstruction Conditions for Regularized Modified Basis Pursuit
• Sparse p-Adic Data Coding for Computationally Efficient and Effective Big Data Analytics
• An Adaptive Markov Random Field for Structured Compressive Sensing
• One-Bit Compressive Sensing: Can We Go Deep and Blind?
• Generalizing CoSaMP to Signals from a Union of Low Dimensional Linear Subspaces
• Two-stage Sampling, Prediction and Adaptive Regression via Correlation Screening (SPARCS)
• Distribution-aware Block-sparse Recovery via Convex Optimization
• Hierarchical Isometry Properties of Hierarchical Measurements
• Weighted ${\ell }_1$-minimization for generalized non-uniform sparse model
• Ranked Sparse Signal Support Detection
• Structural Sparsity in Multiple Measurements
• Dual Averaging Method for Online Graph-structured Sparsity
• Rate-Distortion Dimension of Stochastic Processes
• Breaking the waves: asymmetric random periodic features for low-bitrate kernel machines
• Convolutional Sparse Support Estimator Network (CSEN) From energy efficient support estimation to learning-aided Compressive Sensing
• A Max-Product EM Algorithm for Reconstructing Markov-tree Sparse Signals from Compressive Samples
• On the strong convergence of forward-backward splitting in reconstructing jointly sparse signals
• High-Dimensional Screening Using Multiple Grouping of Variables
• Sparse Reconstruction-based Detection of Spatial Dimension Holes in Cognitive Radio Networks
• Enhanced block sparse signal recovery based on $q$-ratio block constrained minimal singular values
• A Two Stage Generalized Block Orthogonal Matching Pursuit (TSGBOMP) Algorithm
• A Novel Uplink Data Transmission Scheme For Small Packets In Massive MIMO System
• Model-Based and Graph-Based Priors for Group Testing
• Fast DFT Computation for Signals with Structured Support
• Analysis vs Synthesis with Structure - An Investigation of Union of Subspace Models on Graphs
• Single-Pixel Compressive Imaging in Shift-Invariant Spaces via Exact Wavelet Frames
• The greedy side of the LASSO: New algorithms for weighted sparse recovery via loss function-based orthogonal matching pursuit
• GenMod: A generative modeling approach for spectral representation of PDEs with random inputs
• Learning Multi-Frequency Partial Correlation Graphs
• Distributed Coding of Quantized Random Projections
• Cross-scale predictive dictionaries
• One-Shot Messaging at Any Load Through Random Sub-Channeling in OFDM