Global guarantees from local knowledge: Stable and robust recovery of sparse in levels vectors

The model of sparse vectors has proven invaluable for compressive imaging, allowing for signal recovery from very few linear measurements. Recently however, the structured sparsity model of sparsity in levels has inspired a new generation of effective acquisition and reconstruction modalities. Moreover this local structure arises in various areas of signal processing such as parallel acquisition, radar, and the sparse corruptions problem. Reconstruction strategies for sparse in levels signals have previously relied on a suitable convex optimization program. While iterative and greedy algorithms can outperform convex optimization and have been studied extensively in the case of standard sparsity, little is known about their generalizations to the sparse in levels setting. We bridge this gap by showing new stable and robust recovery guarantees for sparse in level variants of the iterative hard thresholding and the compressive sampling matching pursuit algorithms. Our theoretical analysis generalizes recovery guarantees currently available in the case of standard sparsity and favorably compare to sparse in levels guarantees for weighted l1 minimization, both in accuracy and computational time. In addition, we propose and numerically test an extension of the orthogonal matching pursuit algorithm for sparse in levels signals.