Greedy Algorithms for Joint Sparse Recovery

Five known greedy algorithms designed for the single measurement vector setting in compressed sensing and sparse approximation are extended to the multiple measurement vector scenario: Iterative Hard Thresholding (IHT), Normalized IHT (NIHT), Hard Thresholding Pursuit (HTP), Normalized HTP (NHTP), a...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on signal processing 2014-04, Vol.62 (7), p.1694-1704
Main Authors: Blanchard, Jeffrey D., Cermak, Michael, Hanle, David, Yirong Jing
Format: Article
Language:English
Subjects:
Algorithm design and analysis
Algorithms
Applied sciences
Approximation algorithms
Approximation methods
Compressed sensing
Constants
Detection, estimation, filtering, equalization, prediction
Exact sciences and technology
Greedy algorithms
Information, signal and communications theory
joint sparsity
Matching
Matching pursuit algorithms
Mathematical analysis
multiple measurement vectors
performance comparison
Phase transformations
Phase transitions
Recovery
row sparse matrices
Sampling, quantization
Signal and communications theory
Signal processing algorithms
Signal, noise
Telecommunications and information theory
Vectors
Vectors (mathematics)
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Five known greedy algorithms designed for the single measurement vector setting in compressed sensing and sparse approximation are extended to the multiple measurement vector scenario: Iterative Hard Thresholding (IHT), Normalized IHT (NIHT), Hard Thresholding Pursuit (HTP), Normalized HTP (NHTP), and Compressive Sampling Matching Pursuit (CoSaMP). Using the asymmetric restricted isometry property (ARIP), sufficient conditions for all five algorithms establish bounds on the discrepancy between the algorithms' output and the optimal row-sparse representation. When the initial multiple measurement vectors are jointly sparse, ARIP-based guarantees for exact recovery are also established. The algorithms are then compared via the recovery phase transition framework. The strong phase transitions describing the family of Gaussian matrices which satisfy the sufficient conditions are obtained via known bounds on the ARIP constants. The algorithms' empirical weak phase transitions are compared for various numbers of multiple measurement vectors. Finally, the performance of the algorithms is compared against a known rank aware greedy algorithm, Rank Aware Simultaneous Orthogonal Matching Pursuit + MUSIC. Simultaneous recovery variants of NIHT, NHTP, and CoSaMP all outperform the rank-aware algorithm.
ISSN:1053-587X
1941-0476
DOI:10.1109/TSP.2014.2301980