A Unitary Transform Based Generalized Approximate Message Passing

Jiang Zhu, Xiangming Meng, Xupeng Lei, Qinghua Guo

This paper, titled "A Unitary Transform Based Generalized Approximate Message Passing," introduces a robust new algorithm (GUAMP) designed to recover signals from nonlinear measurements, even when the underlying data structures are highly messy or correlated.

TL;DR

The authors propose GUAMP, an algorithm that extends the robustness of Unitary Approximate Message Passing (UAMP) to nonlinear systems. By using a modular framework based on Expectation Propagation, GUAMP successfully recovers signals in scenarios where traditional methods like GAMP and GVAMP fail due to highly correlated measurement matrices.

What Problem Does This Paper Address?

In many fields—like wireless communications, medical imaging, and machine learning—we try to recover an unknown signal $\mathbf{x}$ from observations $\mathbf{y}$. This is often modeled as a Generalized Linear Model (GLM): $$\mathbf{y} = f(\mathbf{Ax} + \mathbf{w})$$ Where $\mathbf{A}$ is a measurement matrix, $\mathbf{w}$ is noise, and $f(\cdot)$ is a nonlinear function (like a quantizer or a phase-retrieval step).

The "gold standard" algorithms for this, like GAMP (Generalized Approximate Message Passing), work beautifully when the matrix $\mathbf{A}$ is composed of independent, identically distributed (i.i.d.) Gaussian elements. However, in the real world, matrices are rarely that "nice"—they are often highly correlated. When correlations are present, standard GAMP often diverges (the math "blows up"), and even newer variants like GVAMP struggle in challenging, highly correlated scenarios.

Methods

The authors bridge the gap between two existing ideas: UAMP (which is great at handling correlated matrices in linear models) and GAMP (which is great at handling nonlinearities).

The key technical steps include:

  1. Singular Value Decomposition (SVD): They decompose the measurement matrix $\mathbf{A}$ into $\mathbf{U\Sigma V}^T$. This allows them to transform the original problem into an equivalent model where the "effective" measurement matrix is unitary. Unitary matrices are mathematically "stable" and don't amplify errors the way correlated matrices do.
  2. Modular Inference: They break the problem into two distinct modules:
  3. Module A (The AMP Module): Handles the linear transform and the signal prior.
  4. Module B (The GAMP Module): Handles the nonlinear measurement function.
  5. Expectation Propagation (EP): These two modules "talk" to each other iteratively. They exchange "extrinsic information"—essentially their best guesses for the means and variances of the hidden variables—until the algorithm converges on a solution.

Datasets

The researchers evaluated GUAMP using synthetic simulations of quantized compressed sensing.

  • Signal: A sparse Bernoulli-Gaussian signal.
  • Matrix: They used a "highly correlated" matrix model ($\mathbf{A} = \mathbf{R}_L \mathbf{H} \mathbf{R}_R$), where the correlation is controlled by a coefficient $\rho$. As $\rho$ increases, the problem becomes significantly harder.
  • Nonlinearity: They tested both 1-bit (sign only) and 2-bit quantization models.

Key Insights and Ideas

  • The Power of Unitary Transforms: The "aha moment" is that by performing an SVD and left-multiplying by the unitary matrix $\mathbf{U}^T$, you can turn a "tough" correlated matrix into a "friendly" diagonal one. This makes the message-passing math stable again.
  • Decomposition is Key: By separating the nonlinearity from the matrix correlation into two modules, the authors can apply the best tool for each specific part of the problem.
  • Robustness to Correlation: Unlike previous iterations of GAMP, GUAMP doesn't require the matrix to be i.i.d. Gaussian to work well. It maintains performance even when the correlation coefficient $\rho$ is high (e.g., 0.35 or 0.5), where other algorithms fail completely.

Key Results

The authors compared GUAMP against GAMP and GVAMP across varying levels of correlation ($\rho$):

  • Low Correlation ($\rho \approx 0$): All algorithms performed similarly well.
  • Moderate to High Correlation ($\rho > 0.15$): GAMP and GVAMP began to diverge, with their error (NMSE) spiking toward 0 dB (meaning they failed to recover the signal).
  • High Correlation ($\rho = 0.35$): GUAMP continued to converge remarkably well, while the competitors failed entirely.
  • Speed: GUAMP typically converges in about 10–20 iterations, making it computationally efficient for practical use.

Limitations and Future Work

  • Damping: The current version of GUAMP does not use "damping" (a technique to slow down updates to prevent oscillation). The authors suggest adding this could further improve stability.
  • Adaptive Steps: They propose that an adaptive step-size scheme could speed up convergence even more.
  • Theoretical Links: A promising future direction is exploring the relationship between GUAMP and ADMM (a popular optimization framework), which might lead to a deeper theoretical understanding of why GUAMP is so robust.

Summary updated

Abstract

We consider the problem of recovering an unknown signal ${\mathbf x}\in {\mathbb R}^n$ from general nonlinear measurements obtained through a generalized linear model (GLM), i.e., ${\mathbf y}= f\left({\mathbf A}{\mathbf x}+{\mathbf w}\right)$, where $f(\cdot)$ is a componentwise nonlinear function. Based on the unitary transform approximate message passing (UAMP) and expectation propagation, a unitary transform based generalized approximate message passing (GUAMP) algorithm is proposed for general measurement matrices $\bf{A}$, in particular highly correlated matrices. Experimental results on quantized compressed sensing demonstrate that the proposed GUAMP significantly outperforms state-of-the-art GAMP and GVAMP under correlated matrices $\bf{A}$.
BibTeX
@inproceedings{zhu2023unitary,
  author = {Jiang Zhu and Xiangming Meng and Xupeng Lei and Qinghua Guo},
  title = {{A Unitary Transform Based Generalized Approximate Message Passing}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2023},
  doi = {10.1109/icassp49357.2023.10095346},
}

Loading related content...

Figure