Average Case Analysis of Multichannel Sparse Recovery Using Convex Relaxation

By Yonina C. Eldar, Holger Rauhut. IEEE Transactions on Information Theory, 2009

338 citations recorded by the source corpus.

This paper considers recovery of jointly sparse multichannel signals from incomplete measurements. Several approaches have been developed to recover the unknown sparse vectors from the given observations, including thresholding, simultaneous orthogonal matching pursuit (SOMP), and convex relaxation based on a mixed matrix norm. Typically, worst case analysis is carried out in order to analyze conditions under which the algorithms are able to recover any jointly sparse set of vectors. However, such an approach is not able to provide insights into why joint sparse recovery is superior to applying standard sparse reconstruction methods to each channel individually. Previous work considered an average case analysis of thresholding and SOMP by imposing a probability model on the measured signals. Here, the main focus is on analysis of convex relaxation techniques. In particular, the mixed l 2,1 approach to multichannel recovery is investigated. Under a very mild condition on the sparsity and on the dictionary characteristics, measured for example by the coherence, it is shown that the probability of recovery failure decays exponentially in the number of channels. This demonstrates that most of the time, multichannel sparse recovery is indeed superior to single channel methods. The probability bounds are valid and meaningful even for a small number of signals. Using the tools developed to analyze the convex relaxation technique, also previous bounds for thresholding and SOMP recovery are tightened.

Subfields: Biomedical Engineering, Computational Mechanics, Signal Processing

View Paper: https://www.semanticscholar.org/paper/413043212a07f422ee582e51d2fecbc9461d0318

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 Signal Processing

Citations in the corpus

Distributed Compressive CSIT Estimation and Feedback for FDD Multi-User Massive MIMO Systems (2014, methodology): “To fully utilize the spatial multiplexing gains and the array gains of massive MIMO [3], [4], knowledge of channel state information at the transmitter (CSIT) is essential.”
Sparse stabilization and optimal control of the Cucker-Smale model (2013, positive): “We consider the optimal control problem of determining a trajectory solution of (6), starting at (x(0), v(0)) = (x0, v0) ∈ (R) × (R) , and minimizing a cost functional which is a combination of the distance from consensus with the l1 − l2norm of the control (as in [27, 28]), under the control constr”
A Signal Processing Perspective on Hyperspectral Unmixing: Insights from Remote Sensing (2014, background): “However, an average analysis in [55] gives an implication that increasing the number of measurements (or pixels here) can significantly reduce the probability of recovery failure.”
Photoplethysmography-Based Heart Rate Monitoring in Physical Activities via Joint Sparse Spectrum Reconstruction (2015, methodology): “, the number of nonzero rows of X in the MMV model equals to the number of nonzero coefficients of x in the SMV model) and other same conditions, the MMV model can yield solutions with smaller errors than the SMV model [14], [19].”
Sparse Methods for Direction-of-Arrival Estimation (2016, background): “In this respect, the result of [74] can be referred to as average case analysis while those accounting for the aforementioned extreme case can be called worst case analysis.”
From Theory to Practice: Sub-Nyquist Sampling of Sparse Wideband Analog Signals (2009, methodology): “In practice, suboptimal polynomial-time CS algorithms may be used for this computation [11], [29], [32]–[34].”
Sparse Signal Recovery With Temporally Correlated Source Vectors Using Sparse Bayesian Learning (2011, background): “Tang, Eldar and their colleague s [14], [16] showed that under certain mild assumptions the recovery rate increases exponentially with the number of measurement vectors L.”
Collaborative Sparse Regression for Hyperspectral Unmixing (2014, methodology): “This approach was not used before for hyperspectral unmixing and the theoretical background is supported by the results shown in [21], in which the authors exploit exactly the 2,1 norm optimization problem for recovering jointly sparse multichannel signals from incomplete measurements.”
Robust Recovery of Signals From a Structured Union of Subspaces (2008, background): “In [42] we show that if the unknown vectors xi are generated randomly, then the performance improves with increasing number of measurement vectors.”
Rank Awareness in Joint Sparse Recovery (2010, methodology): “One might (rightly) criticise such an alysis as overly pessimistic however we stress that, in the full rank case, the worst case performance of RA-thresholdi ng and RA-ORMP still significantly outperforms the average case performance for the most popular (rank blind) a lgorithms [13].”
Structured Compressed Sensing: From Theory to Applications (2011, methodology): “Theorem 22 [119]: Let be drawn from a probabilistic model in which the indices for its nonzero rows are drawn uniformly at random from the possibilities and its nonzero rows (when concatenated) are given by , where is an arbitrary diagonal matrix and each entry of is an i.i.d. standard Gaussian…”
Distributed Compressive Sensing: A Deep Learning Approach (2015, background): “The selection of one of the above methods depends on the requirements imposed by the speciﬁc application.”
Off-Grid Direction of Arrival Estimation Using Sparse Bayesian Inference (2011, background): “It has been shown in [7] that such joint sparsity can be exploited to improve the averaged recovery success prob-”