Modified-CS: Modifying Compressive Sensing for Problems with Partially Known Support

Abstract

We study the problem of reconstructing a sparse signal from a limited number of its linear projections when a part of its support is known, although the known part may contain some errors. The ``known" part of the support, denoted T, may be available from prior knowledge. Alternatively, in a problem of recursively reconstructing time sequences of sparse spatial signals, one may use the support estimate from the previous time instant as the ``known" part. The idea of our proposed solution (modified-CS) is to solve a convex relaxation of the following problem: find the signal that satisfies the data constraint and is sparsest outside of T. We obtain sufficient conditions for exact reconstruction using modified-CS. These are much weaker than those needed for compressive sensing (CS) when the sizes of the unknown part of the support and of errors in the known part are small compared to the support size. An important extension called Regularized Modified-CS (RegModCS) is developed which also uses prior signal estimate knowledge. Simulation comparisons for both sparse and compressible signals are shown.

To Appear in IEEE Trans. Signal Processing, September 2010, shorter version presented at ISIT 2009

References in corpus (4)

• Kalman Filtered Compressed Sensing
• LS-CS-residual (LS-CS): Compressive Sensing on Least Squares Residual
• Analyzing Least Squares and Kalman Filtered Compressed Sensing
• Stability (over time) of Modified-CS and LS-CS for Recursive Causal Sparse Reconstruction

Cited by in corpus (98)

• Sparse Signal Recovery with Temporally Correlated Source Vectors Using Sparse Bayesian Learning
• Robust Subspace Learning: Robust PCA, Robust Subspace Tracking, and Robust Subspace Recovery
• Dynamic Compressive Sensing of Time-Varying Signals via Approximate Message Passing
• Efficient High-Dimensional Inference in the Multiple Measurement Vector Problem
• LS-CS-residual (LS-CS): Compressive Sensing on Least Squares Residual
• An Online Algorithm for Separating Sparse and Low-dimensional Signal Sequences from their Sum
• Two-Dimensional Pattern-Coupled Sparse Bayesian Learning via Generalized Approximate Message Passing
• Exploiting Prior Knowledge in Compressed Sensing Wireless ECG Systems
• Recursive Recovery of Sparse Signal Sequences from Compressive Measurements: A Review
• Bi-level Protected Compressive Sampling
• Compressive Sensing with Prior Support Quality Information and Application to Massive MIMO Channel Estimation with Temporal Correlation
• Compressed sensing for longitudinal MRI: An adaptive-weighted approach
• Regularized Modified BPDN for Noisy Sparse Reconstruction with Partial Erroneous Support and Signal Value Knowledge
• Lorentzian Iterative Hard Thresholding: Robust Compressed Sensing with Prior Information
• Sub-Nyquist Radar Systems: Temporal, Spectral and Spatial Compression
• Static and Dynamic Robust PCA and Matrix Completion: A Review
• Dynamic Filtering of Time-Varying Sparse Signals via l1 Minimization
• Adaptive-Rate Compressive Sensing Using Side Information
• Classification and Reconstruction of High-Dimensional Signals from Low-Dimensional Features in the Presence of Side Information
• ReProCS: A Missing Link between Recursive Robust PCA and Recursive Sparse Recovery in Large but Correlated Noise
• Compressed Sensing with Prior Information: Optimal Strategies, Geometry, and Bounds
• Multi-modal dictionary learning for image separation with application in art investigation
• Robust PCA with Partial Subspace Knowledge
• Statistical Recovery of Simultaneously Sparse Time-Varying Signals from Multiple Measurement Vectors
• A Short Note on Compressed Sensing with Partially Known Signal Support
• An Approximate Message Passing Framework for Side Information
• Provable Subspace Tracking from Missing Data and Matrix Completion
• Sparse Bayesian Learning with Dynamic Filtering for Inference of Time-Varying Sparse Signals
• The sample complexity of weighted sparse approximation
• Compressive MUSIC: A Missing Link Between Compressive Sensing and Array Signal Processing
• Deep Coupled-Representation Learning for Sparse Linear Inverse Problems with Side Information
• Recovery of Structured Signals with Prior Information via Maximizing Correlation
• On partial sparse recovery
• Heterogeneous Networked Data Recovery from Compressive Measurements Using a Copula Prior
• Federated Over-Air Subspace Tracking from Incomplete and Corrupted Data
• Real-time Dynamic MRI Reconstruction using Stacked Denoising Autoencoder
• KF-CS: Compressive Sensing on Kalman Filtered Residual
• CSSF MIMO RADAR: Low-Complexity Compressive Sensing Based MIMO Radar That Uses Step Frequency
• Exact Reconstruction Conditions for Regularized Modified Basis Pursuit
• X-ray image separation via coupled dictionary learning
• Real-time Robust Principal Components' Pursuit
• Distribution-aware Block-sparse Recovery via Convex Optimization
• Ranked Sparse Signal Support Detection
• Stability (over time) of Modified-CS and LS-CS for Recursive Causal Sparse Reconstruction
• FPA-CS: Focal Plane Array-based Compressive Imaging in Short-wave Infrared
• Structural Sparsity in Multiple Measurements
• Recovery of signals under the high order RIP condition via prior support information
• Off-The-Grid Spectral Compressed Sensing With Prior Information
• Convolutional Sparse Support Estimator Network (CSEN) From energy efficient support estimation to learning-aided Compressive Sensing
• Incorporating Prior Information in Compressive Online Robust Principal Component Analysis
• Computing the Discrete Fourier Transform of signals with spectral frequency support
• PaFiMoCS: Particle Filtered Modified-CS and Applications in Visual Tracking across Illumination Change
• Super-resolution Line Spectrum Estimation with Block Priors
• Multilinear Compressive Learning with Prior Knowledge
• Recovery of signals under the condition on RIC and ROC via prior support information
• Recoverability Analysis for Modified Compressive Sensing with Partially Known Support
• Weighted-{${\ell }_1$} minimization with multiple weighting sets
• Analyzing Weighted ${\ell }_1$ Minimization for Sparse Recovery with Nonuniform Sparse Models\footnote{The results of this paper were presented in part at the International Symposium on Information Theory, ISIT 2009}
• Compressed Sensing with Prior Information via Maximizing Correlation
• A Unified Algorithmic Framework for Dynamic Compressive Sensing
• ORKA: Object reconstruction using a K-approximation graph
• Stable Recovery of Weighted Sparse Signals from Phaseless Measurements via Weighted l1 Minimization
• Online Decomposition of Compressive Streaming Data Using $n$-${\ell }_1$ Cluster-Weighted Minimization
• Matrix Completion with Prior Subspace Information via Maximizing Correlation
• Recovery of Sparsely Corrupted Signals
• Approximation Algorithms for Model-Based Compressive Sensing
• Recovering Compressively Sampled Signals Using Partial Support Information
• Recursive Sparse Recovery in Large but Structured Noise - Part 2
• Compressive Sampling with Known Spectral Energy Density
• A sharp recovery condition for sparse signals with partial support information via orthogonal matching pursuit
• Recovery of signals by a weighted ${\ell }_2/{\ell }_1$ minimization under arbitrary prior support information
• Operational Support Estimator Networks
• Weighed l1 on the simplex: Compressive sensing meets locality
• A new result of the scaling law of weighted L1 minimization
• Towards a better compressed sensing
• Exact Dynamic Support Tracking with Multiple Measurement Vectors using Compressive MUSIC
• Modified Basis Pursuit Denoising(MODIFIED-BPDN) for Noisy Compressive Sensing with Partially Known Support
• How to exploit prior information in low-complexity models
• Computation of sparse low degree interpolating polynomials and their application to derivative-free optimization
• Beyond ${\ell }_1$-norm minimization for sparse signal recovery
• Exact Recovery Conditions for Sparse Representations with Partial Support Information
• Time Invariant Error Bounds for Modified-CS based Sparse Signal Sequence Recovery
• RLS Recovery with Asymmetric Penalty: Fundamental Limits and Algorithmic Approaches
• Structured Sparsity Modeling for Improved Multivariate Statistical Analysis based Fault Isolation
• Dynamic Sample Complexity for Exact Sparse Recovery using Sequential Iterative Hard Thresholding
• Support driven reweighted ${\ell }_1$ minimization
• RODEO: Robust DE-aliasing autoencOder for Real-time Medical Image Reconstruction
• Stability of Modified-CS and LS-CS for Recursive Reconstruction of Sparse Signal Sequences
• Deterministic Analysis of Weighted BPDN With Partially Known Support Information
• Partial ${\ell }_1$ optimization in random linear systems -- phase transitions and large deviations
• Improved Algorithms For Structured Sparse Recovery
• Prior Support Knowledge-Aided Sparse Bayesian Learning with Partly Erroneous Support Information
• Projected shrinkage algorithm for box-constrained L1-minimization
• Spectral Super-resolution With Prior Knowledge
• Probabilistic Recovery Guarantees for Sparsely Corrupted Signals
• Uniqueness Conditions for A Class of l0-Minimization Problems
• Power Allocation in Compressed Sensing of Non-uniformly Sparse Signals
• Sparse matrices for weighted sparse recovery