Unitary Approximate Message Passing for Sparse Bayesian Learning

Man Luo, Qinghua Guo, Ming Jin, Yonina C. Eldar, Defeng Huang, Xiangming MengIEEE TSP 2021 · OpenReview

TL;DR

This paper introduces UAMP-SBL, a novel algorithm for Sparse Bayesian Learning (SBL) that significantly improves robustness and efficiency compared to existing AMP-based methods. By incorporating a unitary transformation into the approximate message passing framework, UAMP-SBL effectively handles challenging measurement matrices that cause traditional AMP to diverge, leading to superior signal recovery performance.

What Problem Does This Paper Address?

Sparse Bayesian Learning (SBL) is a powerful technique for recovering sparse signals from noisy measurements, finding applications in various fields like signal processing and statistics. While Approximate Message Passing (AMP) offers a computationally efficient way to implement SBL, it struggles with "generic" measurement matrices – those that are correlated, ill-conditioned, or have non-zero means. These matrices can cause AMP to diverge, leading to poor performance. Existing solutions like damped AMP improve robustness but often sacrifice convergence speed. This paper aims to bridge this gap by developing an SBL algorithm that is both robust to generic matrices and computationally efficient.

Methods

The core innovation is the Unitary Approximate Message Passing for Sparse Bayesian Learning (UAMP-SBL) algorithm. It builds upon the Approximate Message Passing (AMP) framework by incorporating a unitary transformation of the measurement model. This transformation, derived from the Singular Value Decomposition (SVD) of the measurement matrix, effectively decorrelates the measurement process, making the subsequent AMP iterations more stable and robust.

The authors leverage structured variational inference (SVI) and variational message passing (SVMP) to derive the UAMP-SBL algorithm. This approach allows for efficient approximate inference by representing the problem as a factor graph and passing messages between nodes. The algorithm integrates the UAMP (AMP with unitary transformation) into the SVMP framework to handle the computationally intensive message computations.

Key aspects of the method include:

  • Unitary Transformation: Applying a unitary matrix (derived from SVD) to the measurement model to improve robustness.
  • Structured Variational Inference (SVI): Using SVI to approximate the posterior distribution.
  • Variational Message Passing (SVMP): Formulating SVI as a message-passing algorithm.
  • Automatic Shape Parameter Tuning: Proposing an empirical rule to automatically tune the shape parameter of the Gamma hyperprior, which is crucial for promoting sparsity.
  • Extension to MMV: Adapting the algorithm for Multiple Measurement Vector (MMV) problems, where multiple sparse signals are recovered simultaneously.

Datasets

Not discussed in the paper. The paper focuses on synthetic data generated with specific matrix properties (ill-conditioned, correlated, non-zero mean, low-rank) and signal sparsity characteristics for evaluation.

Key Insights and Ideas

  • Unitary Transformation as a Robustness Enabler: The key insight is that applying a unitary transformation to the measurement matrix, derived from its SVD, can dramatically improve the robustness of AMP-based SBL algorithms to challenging matrix structures. This transformation effectively "whitens" the measurement process.
  • SVI and SVMP for Efficient Integration: The structured variational inference and message passing framework provides a principled way to integrate the UAMP algorithm into the SBL problem, enabling efficient computation and analysis.
  • Automatic Shape Parameter Tuning is Crucial: The paper highlights the significant impact of the Gamma hyperprior's shape parameter ($\epsilon$) on sparsity promotion. Automatically tuning this parameter, rather than fixing it or relying on manual selection, leads to substantial performance gains and better convergence.
  • UAMP-SBL Outperforms Existing Methods: The results consistently show that UAMP-SBL achieves better performance (lower NMSE, higher support recovery rates) and often faster convergence than state-of-the-art methods like GGAMP-SBL, especially in challenging scenarios.

Key Results

  • Remarkable Robustness: UAMP-SBL demonstrates significantly improved robustness against ill-conditioned, correlated, and non-zero mean measurement matrices compared to GGAMP-SBL. In many cases, it closely approaches the theoretical support-oracle bound.
  • Enhanced Efficiency: UAMP-SBL offers a considerable speedup over GGAMP-SBL, particularly in scenarios with larger matrices or when GGAMP-SBL requires small damping factors for robustness.
  • Superior Recovery Accuracy: The algorithm consistently achieves lower Normalized Mean Squared Error (NMSE) and higher support recovery rates across various challenging matrix types and sparsity levels. For instance, in ill-conditioned matrices with a sparsity rate of 0.1, UAMP-SBL's NMSE is notably better than GGAMP-SBL, especially for higher condition numbers.
  • Effective MMV Performance: The extension to MMV problems also shows UAMP-SBL outperforming other methods, particularly when measurement matrices deviate significantly from i.i.d. Gaussian.
  • Automatic $\epsilon$ Tuning Benefits: The proposed empirical rule for tuning $\epsilon$ leads to performance comparable to or better than manual tuning or other heuristic approaches, without requiring prior knowledge of the sparsity rate.

Limitations and Future Work

  • SVD Computation: While the unitary transformation is key, it requires computing the SVD of the measurement matrix. The paper notes that this can be done offline, but its computational cost is still counted for runtime comparisons.
  • Theoretical Analysis of Shape Parameter Update: While an empirical rule for updating $\epsilon$ is proposed and shown to be effective, a more rigorous theoretical analysis of its state evolution and update mechanism is suggested for future work.
  • Generalization of Unitary Transformation: The paper focuses on SVD-based unitary transformations. Exploring other forms of unitary transformations or pre-conditioning techniques could be a future direction.
  • Further Analysis of State Evolution: The authors mention that rigorous analyses of the state evolution of UAMP-SBL are needed.

Summary updated

Abstract

Sparse Bayesian learning (SBL) can be implemented with low complexity based on the approximate message passing (AMP) algorithm. However, it does not work well for a generic measurement matrix, which may cause AMP to diverge. Damped AMP has been used for SBL to alleviate divergence issues at the cost of reducing convergence speed. In this work, we propose a new SBL algorithm based on structured variational inference, leveraging AMP with a unitary transformation. Both single measurement vector and multiple measurement vector problems are investigated. It is shown that, compared to state-of-the-art AMP-based SBL algorithms, the proposed UAMP-SBL is more robust and efficient, leading to remarkably better performance.
BibTeX
@article{luo2021unitary,
  author = {Man Luo and Qinghua Guo and Ming Jin and Yonina C. Eldar and Defeng Huang and Xiangming Meng},
  title = {{Unitary Approximate Message Passing for Sparse Bayesian Learning}},
  journal = {IEEE Trans. Signal Process.},
  year = {2021},
  url = {https://openreview.net/forum?id=09g01OVp62P},
}
Figure