Improving M-SBL for Joint Sparse Recovery using a Subspace Penalty

Jong Chul Ye, Jong Min Kim, Yoram Bresler

Abstract

The multiple measurement vector problem (MMV) is a generalization of the compressed sensing problem that addresses the recovery of a set of jointly sparse signal vectors. One of the important contributions of this paper is to reveal that the seemingly least related state-of-art MMV joint sparse recovery algorithms - M-SBL (multiple sparse Bayesian learning) and subspace-based hybrid greedy algorithms - have a very important link. More specifically, we show that replacing the $\log\det(\cdot)$ term in M-SBL by a rank proxy that exploits the spark reduction property discovered in subspace-based joint sparse recovery algorithms, provides significant improvements. In particular, if we use the Schatten-$p$ quasi-norm as the corresponding rank proxy, the global minimiser of the proposed algorithm becomes identical to the true solution as $p \rightarrow 0$. Furthermore, under the same regularity conditions, we show that the convergence to a local minimiser is guaranteed using an alternating minimization algorithm that has closed form expressions for each of the minimization steps, which are convex. Numerical simulations under a variety of scenarios in terms of SNR, and condition number of the signal amplitude matrix demonstrate that the proposed algorithm consistently outperforms M-SBL and other state-of-the art algorithms.

Introduction

The Multiple Measurement Vector (MMV) problem is a cornerstone of modern signal processing, extending compressed sensing to scenarios where multiple snapshots share a common sparsity pattern (support). Historically, two distinct paradigms have dominated this field: Sparse Bayesian Learning (SBL), known for its robustness to noise, and subspace-based greedy methods like MUSIC, valued for their speed and theoretical resolution.

This research introduces Subspace-Penalized Sparse Learning (SPL), a framework that reveals a fundamental mathematical link between these two seemingly unrelated approaches. By bridging the gap between Bayesian learning and subspace geometry, the authors overcome the primary limitations of standard Multiple-SBL (M-SBL), such as its susceptibility to local minima and computational overhead.

The Subspace Penalty Framework

The core innovation of SPL lies in the reinterpretation of the M-SBL objective function. The authors demonstrate that the standard $\log\det(\cdot)$ penalty term used in M-SBL is actually a proxy for the rank of a partial sensing matrix.

Instead of the standard M-SBL penalty, SPL introduces a penalty based on the Schatten-p quasi-norm. This penalty specifically targets the "noise subspace"—the portion of the data that does not contain the signal. By using the Schatten-p norm as $p \to 0$, the algorithm performs a direct minimization of the rank of the noise-projected sensing matrix. This provides a more direct and geometrically sound way to impose joint sparsity than previous Bayesian methods.

The SPL Algorithm

The authors develop an Alternating Minimization approach to solve the resulting objective. While the overall problem is non-convex, it is decomposed into three manageable steps:

  1. Signal Update: Updating the signal estimate ($X$).
  2. Subspace Update: Updating a surrogate matrix ($\Psi$) related to the subspace.
  3. Hyper-parameter Update: Updating the sparsity parameters ($\gamma$).

Crucially, each individual step in this alternating algorithm is convex and possesses a closed-form solution, making the implementation reliable and mathematically sound.

Key Insights

Escaping Local Minima

A significant weakness of M-SBL is that if a row is incorrectly estimated as zero during an iteration, it remains zero for the duration of the process, often trapping the algorithm in a suboptimal local minimum. SPL’s subspace geometry allows it to "resuscitate" these rows, providing a mechanism to escape local minima that would otherwise lead to recovery failure.

Computational Efficiency

Because the subspace penalty operates within the noise subspace, the required matrix inversions are often performed on matrices of size $(m-r) \times (m-r)$, where $m$ is the number of sensors and $r$ is the signal rank. This is frequently smaller than the $m \times m$ inversions required by standard M-SBL, leading to improved efficiency in many scenarios.

Experimental Validation

The paper validates the SPL framework through rigorous numerical simulations using both Gaussian and Fourier sensing matrices. The testing varied several critical parameters, including Signal-to-Noise Ratio (SNR), the number of snapshots ($N$), and the condition number of the signal (reflecting snapshot correlation).

Results

  • Superior Recovery: SPL consistently achieved higher success rates for perfect signal recovery compared to M-SBL, MUSIC, and mixed-norm ($l_1/l_2$) approaches.
  • Robustness to Ill-Conditioning: SPL performs significantly better when signal snapshots are highly correlated. While other algorithms see a sharp drop in performance as the condition number increases, SPL remains stable.
  • Noise Performance: The algorithm showed a clear performance gain that increased with the number of snapshots, as more data allowed for a more precise estimation of the noise subspace.

Limitations and Future Work

While SPL represents a significant advancement, the authors note that the theoretical proof of finding the true solution relies on $p$ approaching zero, which can present numerical stability challenges in practice. Additionally, while the algorithm is more efficient than M-SBL, it still requires iterative Singular Value Decompositions (SVDs), which may be a bottleneck for extremely high-dimensional, real-time applications. Future research may focus on automated hyper-parameter tuning for unknown noise environments and further optimization of the iterative steps.

Summary updated

Abstract

The multiple measurement vector problem (MMV) is a generalization of the compressed sensing problem that addresses the recovery of a set of jointly sparse signal vectors. One of the important contributions of this paper is to reveal that the seemingly least related state-of-art MMV joint sparse recovery algorithms - M-SBL (multiple sparse Bayesian learning) and subspace-based hybrid greedy algorithms - have a very important link. More specifically, we show that replacing the $\log\det(\cdot)$ term in M-SBL by a rank proxy that exploits the spark reduction property discovered in subspace-based joint sparse recovery algorithms, provides significant improvements. In particular, if we use the Schatten-$p$ quasi-norm as the corresponding rank proxy, the global minimiser of the proposed algorithm becomes identical to the true solution as $p \rightarrow 0$. Furthermore, under the same regularity conditions, we show that the convergence to a local minimiser is guaranteed using an alternating minimization algorithm that has closed form expressions for each of the minimization steps, which are convex. Numerical simulations under a variety of scenarios in terms of SNR, and condition number of the signal amplitude matrix demonstrate that the proposed algorithm consistently outperforms M-SBL and other state-of-the art algorithms.
BibTeX
@article{ye2015improving,
  author = {Jong Chul Ye and Jong Min Kim and Yoram Bresler},
  title = {{Improving M-SBL for Joint Sparse Recovery using a Subspace Penalty}},
  journal = {IEEE Trans. Signal Process.},
  year = {2015},
  url = {https://openreview.net/forum?id=v9v1Fm9AVA},
}
Figure