Reduce and Boost: Recovering Arbitrary Sets of Jointly Sparse Vectors

Abstract

The rapid developing area of compressed sensing suggests that a sparse vector lying in an arbitrary high dimensional space can be accurately recovered from only a small set of non-adaptive linear measurements. Under appropriate conditions on the measurement matrix, the entire information about the original sparse vector is captured in the measurements, and can be recovered using efficient polynomial methods. The vector model has been extended to a finite set of sparse vectors sharing a common non-zero location set. In this paper, we treat a broader framework in which the goal is to recover a possibly infinite set of jointly sparse vectors. Extending existing recovery methods to this model is difficult due to the infinite structure of the sparse vector set. Instead, we prove that the entire infinite set of sparse vectors can recovered by solving a single, reduced-size finite-dimensional problem, corresponding to recovery of a finite set of sparse vectors. We then show that the problem can be further reduced to the basic recovery of a single sparse vector by randomly combining the measurement vectors. Our approach results in exact recovery of both countable and uncountable sets as it does not rely on discretization or heuristic techniques. To efficiently recover the single sparse vector produced by the last reduction step, we suggest an empirical boosting strategy that improves the recovery ability of any given sub-optimal method for recovering a sparse vector. Numerical experiments on random data demonstrate that when applied to infinite sets our strategy outperforms discretization techniques in terms of both run time and empirical recovery rate. In the finite model, our boosting algorithm is characterized by fast run time and superior recovery rate than known popular methods.

21 Pages, 9 figures. Submitted to the IEEE for possible publication

References in corpus (2)

• High-Resolution Radar via Compressed Sensing
• Blind Multi-Band Signal Reconstruction: Compressed Sensing for Analog Signals

Cited by in corpus (66)

• Compressed Sensing of Block-Sparse Signals: Uncertainty Relations and Efficient Recovery
• From Theory to Practice: Sub-Nyquist Sampling of Sparse Wideband Analog Signals
• Structured Compressed Sensing: From Theory to Applications
• Xampling: Signal Acquisition and Processing in Union of Subspaces
• Joint-sparse recovery from multiple measurements
• Time Delay Estimation from Low Rate Samples: A Union of Subspaces Approach
• C-HiLasso: A Collaborative Hierarchical Sparse Modeling Framework
• Compressed Sensing of Analog Signals in Shift-Invariant Spaces
• Multichannel Sampling of Pulse Streams at the Rate of Innovation
• Exploiting Statistical Dependencies in Sparse Representations for Signal Recovery
• A Block Sparsity Based Estimator for mmWave Massive MIMO Channels with Beam Squint
• Sub-Nyquist Cyclostationary Detection for Cognitive Radio
• Various thresholds for ${\ell }_1$-optimization in compressed sensing
• Reconciling Compressive Sampling Systems for Spectrally-sparse Continuous-time Signals
• Self-Dictionary Sparse Regression for Hyperspectral Unmixing: Greedy Pursuit and Pure Pixel Search are Related
• Perturbation Analysis of Orthogonal Matching Pursuit
• Phase Transitions in Frequency Agile Radar Using Compressed Sensing
• Block-length dependent thresholds in block-sparse compressed sensing
• Photoacoustic imaging beyond the acoustic diffraction-limit with dynamic speckle illumination and sparse joint support recovery
• Uncertainty Relations for Shift-Invariant Analog Signals
• Sub-Nyquist Sampling: Bridging Theory and Practice
• Exact Joint Sparse Frequency Recovery via Optimization Methods
• Measurement Bounds for Sparse Signal Ensembles via Graphical Models
• Learning the Conditional Independence Structure of Stationary Time Series: A Multitask Learning Approach
• Improving Noise Robustness in Subspace-based Joint Sparse Recovery
• Performance Limits for Noisy Multi-Measurement Vector Problems
• Compressive MUSIC: A Missing Link Between Compressive Sensing and Array Signal Processing
• Improving M-SBL for Joint Sparse Recovery using a Subspace Penalty
• Beyond Bandlimited Sampling: Nonlinearities, Smoothness and Sparsity
• Airborne Radar STAP using Sparse Recovery of Clutter Spectrum
• Sampling and Reconstruction of Sparse Signals in Shift-Invariant Spaces: Generalized Shannon's Theorem Meets Compressive Sensing
• Conditioning of Random Block Subdictionaries with Applications to Block-Sparse Recovery and Regression
• Rank Awareness in Joint Sparse Recovery
• Non-uniform sampling and reconstruction of multi-band signals and its application in wideband spectrum sensing of cognitive radio
• Performance Limits with Additive Error Metrics in Noisy Multi-Measurement Vector Problem
• Recovering Signals from Lowpass Data
• Estimation of block sparsity in compressive sensing
• A sharp recovery condition for block sparse signals by block orthogonal multi-matching pursuit
• An Adaptive Markov Random Field for Structured Compressive Sensing
• Distribution-aware Block-sparse Recovery via Convex Optimization
• On the Support Recovery of Jointly Sparse Gaussian Sources using Sparse Bayesian Learning
• Stochastic Greedy Algorithms For Multiple Measurement Vectors
• A mixed ${\ell }_1$ regularization approach for sparse simultaneous approximation of parameterized PDEs
• Simultaneously Sparse Solutions to Linear Inverse Problems with Multiple System Matrices and a Single Observation Vector
• Constructing test instances for Basis Pursuit Denoising
• Robust Recovery of Signals From a Structured Union of Subspaces
• Average Case Analysis of Multichannel Sparse Recovery Using Convex Relaxation
• Statistical Physics and Information Theory Perspectives on Linear Inverse Problems
• The high order block RIP condition for signal recovery
• CaSCADE: Compressed Carrier and DOA Estimation
• On the strong convergence of forward-backward splitting in reconstructing jointly sparse signals
• IoT Random Access in Massive MIMO: Exploiting Diversity in Sensing Matrices
• Compressed sensing of block-sparse positive vectors
• Orthogonal subspace based fast iterative thresholding algorithms for joint sparsity recovery
• Identification of Sparse Linear Operators
• Recovery of signals by a weighted ${\ell }_2/{\ell }_1$ minimization under arbitrary prior support information
• Concatenate and Boost for Multiple Measurement Vector Problems
• Minimum Variance Estimation of a Sparse Vector within the Linear Gaussian Model: An RKHS Approach
• GPS Signal Acquisition via Compressive Multichannel Sampling
• Efficient Sampling of Sparse Wideband Analog Signals
• Sub-Nyquist Sampling of Short Pulses
• Joint Sparsity Recovery for Spectral Compressed Sensing
• Expected RIP: Conditioning of The Modulated Wideband Converter
• Random linear under-determined systems with block-sparse solutions -- asymptotics, large deviations, and finite dimensions
• Compressive Imaging and Characterization of Sparse Light Deflection Maps
• Retrieval of Sparse Solutions of Multiple-Measurement Vectors via Zero-point Attracting Projection