Reduce and Boost: Recovering Arbitrary Sets of Jointly Sparse Vectors

By Moshe Mishali, Yonina C. Eldar. 2008

367 citations recorded by the source corpus.

The rapid developing area of compressed sensing suggests that a sparse vector lying in a high dimensional space can be accurately and efficiently recovered from only a small set of nonadaptive linear measurements, under appropriate conditions on the measurement matrix. The vector model has been extended both theoretically and practically to a finite set of sparse vectors sharing a common sparsity pattern. 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 algorithms 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 be 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 model of a single sparse vector by randomly combining the measurements. Our approach is exact for both countable and uncountable sets, as it does not rely on discretization or heuristic techniques. To efficiently find the single sparse vector produced by the last reduction step, we suggest an empirical boosting strategy that improves the recovery ability of any given suboptimal 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 has fast run time and much higher recovery rate than known popular methods.

Subfields: Biomedical Engineering, Computational Mechanics, Electrical and Electronic Engineering

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Biomedical Engineering

In Computational Mechanics

In Electrical and Electronic Engineering

Citations in the corpus

Data Encoding for Byzantine-Resilient Distributed Optimization (2019, background): “Now we state a lemma from [ME08] that shows that a random linear combination of the error vectors (where coeﬃcients are chosen from an absolutely continuous distribution) preserves the support with probability one.”
Comparing Measures of Sparsity (2008, methodology): “…machine learning algorithms and techniques such as matrix factorization [7], signal recovery/extraction [8], denoising [9], [10], compressed sensing [11], dictionary learning [12], signal representation [13], [14], support vector machines [15], sampling theory [16], [17] and source…”
Blind Multiband Signal Reconstruction: Compressed Sensing for Analog Signals (2007, methodology): “1Since submission of the report [18] and the conference version [19], we have further expanded the analog CS framework in several follow-up papers; see [20]–[23].”
Robust Recovery of Signals From a Structured Union of Subspaces (2008, methodology): “Although at first sight this seems like a difficult problem as o ur algorithms are inherently finite-dimensional, recovery methods for sparse signals in infinite dimensions have been a ddressed in some of our previous work [15]–[19].”
Rank Awareness in Joint Sparse Recovery (2010, background): “One exception to this is the approach in [12] which reduces the MMV problem to a single channel recovery via a random projection that preserves the sparsity pattern.”
Average Case Analysis of Multichannel Sparse Recovery Using Convex Relaxation (2009, methodology): “Several alternative methods have been proposed, that have polynomial complexit y [47], [45], [22], [13], [11], [30], [20], [21], [30].”
Structured Compressed Sensing: From Theory to Applications (2011, methodology): “The sufﬁcient direction of this condition was shown in [113] to hold even in the case where there are inﬁnitely many vectors .”
Convex Optimization in Signal Processing and Communications (2009, methodology): “By using several tools, developed in more detail in [26, 23, 27], it is possible to extend the essential ideas of compressed sensing to the analog domain.”
On the Reconstruction of Block-Sparse Signals With an Optimal Number of Measurements (2008, background): “Generalization of the block-sparse problem to the case when the number of blocks is inﬁnite was considered in the most recent paper [44].”
Block-Sparse Signals: Uncertainty Relations and Efficient Recovery (2009, background): “Another interesting special case of the block-sparse model appears in the multiple measurement vector (MMV) problem, which deals with the measurement of a set of vectors that share a joint sparsity pattern [20], [21], [22], [14], [23].”
Data Encoding for Byzantine-Resilient Distributed Gradient Descent (2018, background): “This idea has appeared before in [22] in the context of compressed sensing for recovering arbitrary sets of jointly sparse signals that have been measured by the same measurement matrix.”