Optimal Algorithms for the Inhomogeneous Spiked Wigner Model

Aleksandr Pak, Justin Ko, Florent Krzakala

TL;DR

This paper extends the classic "spiked Wigner model" to account for heterogeneous noise, where different parts of a data matrix have different noise levels. The authors develop a new Approximate Message Passing (AMP) algorithm and a corresponding spectral method that achieve the optimal computational limits for signal recovery, identifying a "statistical-to-computational gap" where the problem is theoretically solvable but algorithmically hard.

What Problem Does This Paper Address?

In high-dimensional statistics, the spiked Wigner model is a benchmark for understanding how to extract a signal (the "spike") from a noisy matrix. Traditionally, researchers assume the noise is homogeneous—meaning every entry in the matrix is corrupted by the same amount of variance.

However, real-world data is rarely that uniform. This paper tackles the inhomogeneous version, where the noise follows a block-constant profile (different groups of indices have different noise variances). While the theoretical limits of signal recovery for this model were previously known, the algorithmic path to reaching those limits—and understanding when recovery is computationally efficient—remained an open challenge.

Methods

The authors employ two primary algorithmic frameworks:

  1. Inhomogeneous Approximate Message Passing (AMP): They derive a new AMP recursion specifically tailored for block-constant noise. A key technical contribution is the adaptation of the "Onsager term"—a correction factor in AMP that accounts for correlations introduced by the algorithm's own iterations—to handle the variance profile $\Delta$.
  2. State Evolution: They provide a rigorous "state evolution" analysis, which is a way to track the algorithm's performance (like Mean Squared Error) through a set of deterministic scalar equations.
  3. Optimal Spectral Method: By linearizing their AMP algorithm, the authors deduce a novel spectral method. Instead of performing Principal Component Analysis (PCA) on the raw data matrix $Y$, they construct a transformed matrix $\tilde{Y}$ that accounts for the noise profile. They conjecture (and provide evidence) that the top eigenvalue of this matrix separates from the "bulk" of the noise exactly at the computational threshold.

Datasets

The paper relies on synthetic datasets to validate the theoretical results:

  • Simulated Spiked Matrices: Matrices of size $N=500$ to $N=2500$ generated with a rank-one signal and Gaussian noise.
  • Variance Profiles: Specifically, they test profiles like a $2 \times 2$ block matrix $\tilde{\Delta}$ with equally sized blocks to demonstrate how heterogeneity affects recovery.
  • Priors: They evaluate both standard Gaussian priors and sparse priors to highlight the gaps between different recovery regimes.

Key Insights and Ideas

  • The Onsager Correction is Group-Specific: In the inhomogeneous case, the Onsager term (the "memory" correction in the algorithm) must be calculated based on the specific noise variance of each block. This ensures the algorithm remains "unbiased" as it iterates.
  • Standard PCA is Sub-optimal: One of the most striking findings is that standard PCA applied to a simple renormalization of the matrix fails to reach the optimal recovery threshold. The authors' transformed matrix $\tilde{Y}$ is required to actually "see" the signal at the theoretical limit.
  • The Statistical-to-Computational Gap: For certain "sparse" signals, there is a regime where a signal could be recovered given infinite computing power (the Bayes-optimal limit), but where efficient algorithms like AMP and spectral methods fail. The authors precisely locate this gap at the point where the signal-to-noise ratio $\lambda(\Delta) = 1$.

Key Results

  • Algorithmic Optimality: The authors prove that their AMP algorithm's performance matches the Bayes-optimal fixed-point equations in the asymptotic limit ($N \to \infty$).
  • Phase Transitions: They identify the sharp "BBP-like" transition for their spectral method. As shown in Figure 3 and 5, the outlying eigenvector (the signal) only emerges from the noise bulk when the SNR exceeds 1.
  • Numerical Agreement: Even at relatively small matrix sizes ($N=500$), numerical simulations show a near-perfect match with the theoretical predictions for Mean Squared Error (MSE).

Limitations and Future Work

  • Block-Constant Assumption: While the paper provides a strong foundation for block-constant noise, a fully rigorous analysis for general continuous variance profiles (where every entry might have a unique variance) is suggested as a direction for future study.
  • Conjecture 2.6: The sharp transition for the spectral method is presented as a conjecture. While the authors provide strong evidence using the linear AMP formalism, a full mathematical proof of the eigenvalue separation for $\tilde{Y}$ remains for future work.
  • Higher Rank Spikes: The current work focuses on rank-one spikes (a single signal vector). Extending these optimal algorithms to higher-rank cases (multiple signals) would be a natural next step for more complex data applications.

Summary updated

Abstract

We study a spiked Wigner problem with an inhomogeneous noise profile. Our aim in this problem is to recover the signal passed through an inhomogeneous low-rank matrix channel. While the information-theoretic performances are well-known, we focus on the algorithmic problem. First, we derive an approximate message-passing algorithm (AMP) for the inhomogeneous problem and show that its rigorous state evolution coincides with the information-theoretic optimal Bayes fixed-point equations. Second, we deduce a simple and efficient spectral method that outperforms PCA and is shown to match the information-theoretic transition.
BibTeX
@inproceedings{pak2023optimal,
  author = {Aleksandr Pak and Justin Ko and Florent Krzakala},
  title = {{Optimal Algorithms for the Inhomogeneous Spiked Wigner Model}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=xNUmTRYtV1},
}
Figure