Improved Turbo Message Passing for Compressive Robust Principal Component Analysis: Algorithm Design and Asymptotic Analysis

Xiaojun Yuan, Zhuohang He, Junjie Ma, Xiaojun Yuan 0002IEEE Trans. Information Theory 2025 · DOI

TL;DR

This paper introduces an improved turbo message passing (ITMP) algorithm for recovering low-rank and sparse components from compressed, noisy data. It provides a rigorous theoretical framework, including asymptotic analysis and convergence guarantees, which is crucial for understanding and optimizing performance in real-world applications.

What Problem Does This Paper Address?

Modern high-dimensional data often exhibits an underlying low-dimensional structure (a "low-rank" component) but is also corrupted by sparse outliers or anomalies. Robust Principal Component Analysis (RPCA) aims to disentangle these components. When measurements are also compressed (meaning we have fewer observations than unknowns), this becomes a Compressive Robust Principal Component Analysis (CRPCA) problem. Existing methods for CRPCA, while effective, often struggle with computational complexity or lack rigorous theoretical understanding, especially when dealing with non-Gaussian noise. This paper addresses the need for an efficient, theoretically sound algorithm for CRPCA that can handle these challenges.

Methods

The authors propose an Improved Turbo Message Passing (ITMP) algorithm. This algorithm is based on a Bayesian probabilistic model and leverages the sum-product rule for message passing. Key innovations include:

  • Novel Interpretation of Turbo Message Passing: They introduce assumptions to simplify message calculations, treating input errors to denoisers as independent and identically distributed (i.i.d.) sequences. This allows for efficient computation and is shown to be self-consistent.
  • State Evolution (SE) Analysis: A core contribution is the development of a state evolution framework to analyze the algorithm's asymptotic behavior in the large-system limit. This provides a deterministic way to track the evolution of mean-square errors (MSEs) of the estimated components.
  • Asymptotic MSE Transfer Functions: They derive analytical expressions for the asymptotic MSE transfer functions of the denoisers (linear, sparse, and low-rank). Crucially, this analysis extends to non-Gaussian input noise for the low-rank denoiser, a significant improvement over prior work.
  • Convergence Analysis: Using the SE framework, they establish sufficient conditions for the algorithm's global convergence and identify phase transition boundaries, predicting when the algorithm will successfully recover the underlying components.

The ITMP algorithm iteratively refines estimates of the low-rank (L) and sparse (S) components using three specialized "denoisers": a linear denoiser for the compressed measurements, a sparse denoiser exploiting the sparsity of S, and a low-rank denoiser exploiting the low-rank nature of L.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and numerical experiments with synthetic data generated according to specific models.

Key Insights and Ideas

  • Non-Gaussian Noise is Common and Important: A key insight is that the noise affecting the low-rank component in CRPCA is often not Gaussian, contrary to assumptions in some prior work. This necessitates more sophisticated analysis and algorithms.
  • State Evolution is Powerful for Understanding: The state evolution framework provides a powerful tool to analyze the complex dynamics of message passing algorithms, offering insights into convergence and performance limits that are hard to obtain otherwise.
  • Theoretical Guarantees Matter: By providing rigorous asymptotic analysis and convergence conditions, the paper offers a strong theoretical foundation for the proposed ITMP algorithm, building confidence in its applicability.
  • Phase Transitions Predict Performance: The identification of phase transition boundaries is critical for understanding the trade-offs between the number of measurements, sparsity level, and rank, guiding practical parameter selection.

Key Results

  • Improved Algorithm: The proposed ITMP algorithm is shown to be effective in recovering low-rank and sparse components from compressed measurements.
  • Theoretical Framework: The paper establishes a rigorous state evolution analysis for the ITMP algorithm, providing asymptotic MSE transfer functions and convergence guarantees.
  • Non-Gaussian Noise Handling: The analysis successfully handles non-Gaussian input noise for the low-rank denoiser, a significant advancement.
  • Accurate Phase Transition Prediction: The theoretical phase transition boundary derived from the SE analysis closely matches empirical observations from numerical experiments.
  • Competitive Performance: Comparisons with existing algorithms (e.g., SPCP, SpaRCS) suggest that the proposed algorithm achieves competitive or superior performance, particularly in terms of the required sampling rate for successful recovery.

Limitations and Future Work

  • Assumptions for State Evolution: The state evolution analysis relies on certain assumptions (e.g., i.i.d. noise, specific properties of denoisers) that, while empirically supported, might not hold in all practical scenarios.
  • Computational Complexity: While ITMP is designed to be efficient, the paper doesn't explicitly detail the computational complexity compared to other methods.
  • Parameter Selection: The paper provides theoretical conditions for convergence, but practical selection of parameters (like regularization parameters) might still require tuning.
  • Future Work: The authors suggest exploring the algorithm's performance with more complex measurement models and real-world datasets. Further investigation into the theoretical underpinnings for non-separable functions and more general noise distributions could also be valuable.

Summary updated

BibTeX
@article{yuan2025improved,
  author = {Xiaojun Yuan and Zhuohang He and Junjie Ma and Xiaojun Yuan},
  title = {{Improved Turbo Message Passing for Compressive Robust Principal Component Analysis: Algorithm Design and Asymptotic Analysis}},
  journal = {IEEE Trans. Information Theory},
  year = {2025},
  doi = {10.1109/tit.2024.3509476},
}
Figure