Estimation of low-rank matrices via approximate message passing

Andrea Montanari, Ramji VenkataramananThe Annals of Statistics 2021 · DOI · arXiv

Abstract

In high-dimensional statistics, recovering a low-rank signal from a noisy observation—often referred to as the "spiked model"—is a fundamental challenge. While spectral methods are computationally efficient, they frequently fail to achieve the Bayes-optimal error because they do not incorporate prior knowledge of the signal's structure. This paper introduces a practical algorithm that combines Approximate Message Passing (AMP) with spectral initialization to achieve Bayes-optimal accuracy. We provide a new mathematical framework to analyze AMP when it is initialized using data-dependent spectral methods, overcoming a long-standing theoretical barrier in the analysis of state evolution.

Introduction

The problem of estimating a low-rank matrix $X$ from a noisy observation $Y = X + Z$ (where $Z$ is Gaussian noise) arises across diverse fields, including genomics, social network analysis, and signal processing. When the empirical distribution of the signal's entries is known, Bayes-optimal estimators can significantly outperform simple spectral approaches. However, these optimal estimators are often computationally intractable.

Approximate Message Passing (AMP) algorithms have emerged as a powerful class of iterative methods designed to reach these theoretical limits efficiently. However, a major hurdle has persisted: AMP's performance is typically tracked via "state evolution," a framework that requires the algorithm's starting point to be independent of the noise. In low-rank estimation, random initializations often lead AMP to get stuck at uninformative, unstable fixed points. To succeed, the algorithm must be initialized using the data itself (e.g., via the top eigenvectors), which traditionally breaks the state evolution analysis. This paper bridges this gap by providing a rigorous analysis of AMP with spectral initialization.

Methodology

The Two-Step Algorithm

The proposed approach consists of two distinct phases:

  1. Spectral Initialization: We compute the principal eigenvectors of the noisy data matrix $Y$. This provides a starting point that is already correlated with the true signal, effectively "breaking the symmetry" of the problem.
  2. AMP Iteration: We run a customized AMP algorithm, using the spectral estimate as the initial state. This iterative process refines the estimate toward the Bayes-optimal limit.

The Conditioning Lemma

The core theoretical contribution is a new analysis of state evolution. The authors prove a "Conditioning Lemma," which demonstrates that for large matrices, the data matrix conditioned on its top eigenvectors behaves like a simpler, decoupled model. This allows the researchers to mathematically account for the bias introduced by the spectral start and rigorously track the algorithm's progress as it moves from the spectral estimate toward the minimum mean square error (MMSE).

Applications and Models

As a theoretical study, the methodology is validated against several fundamental probabilistic models rather than static datasets:

  • Spiked Wigner and Rectangular Matrices: These serve as the standard benchmarks for symmetric and asymmetric low-rank recovery.
  • The Gaussian Block Model: A variant of the Stochastic Block Model used to detect community structures in networks. The paper shows that AMP can effectively identify asymmetric communities.
  • Sparse Low-Rank Matrices: The algorithm is shown to exploit sparsity priors to improve recovery beyond what is possible with standard PCA.

Key Insights

Achieving Bayes-Optimality

The paper demonstrates that the proposed AMP algorithm achieves Bayes-optimal accuracy as soon as the signal strength exceeds the "spectral threshold"—the point at which the signal becomes detectable in the eigenvalues of the noisy matrix. In many cases, this allows the algorithm to reach the absolute information-theoretic limit of what is computationally feasible.

Statistical Inference

Beyond point estimation, the authors show that AMP can be used for rigorous statistical inference. Because the algorithm's errors are approximately Gaussian in the high-dimensional limit, it is possible to construct accurate confidence intervals and control the False Discovery Rate (FDR). This transforms AMP from a recovery heuristic into a robust tool for hypothesis testing.

Handling Fluctuations

In complex cases where the signal has multiple identical eigenvalues (degenerate cases), the algorithm's path may fluctuate. The new analysis provides a way to characterize the distribution of these fluctuations, ensuring that the algorithm's performance remains predictable even when the specific path varies between runs.

Conclusion and Future Work

This work provides a rigorous foundation for using AMP in low-rank matrix estimation, proving that spectral initialization does not preclude exact asymptotic analysis. While the current framework relies on the assumption of Gaussian noise, it sets the stage for future research into "universality"—the principle that these results should hold for a broader class of noise distributions. Additionally, while the "Bayes-AMP" variant requires knowledge of the signal's prior distribution, the general framework provides a path toward more flexible, agnostic estimators that still outperform traditional spectral methods.

Summary updated

Abstract

Consider the problem of estimating a low-rank matrix when its entries are perturbed by Gaussian noise. If the empirical distribution of the entries of the spikes is known, optimal estimators that exploit this knowledge can substantially outperform simple spectral approaches. Recent work characterizes the asymptotic accuracy of Bayes-optimal estimators in the high-dimensional limit. In this paper we present a practical algorithm that can achieve Bayes-optimal accuracy above the spectral threshold. A bold conjecture from statistical physics posits that no polynomial-time algorithm achieves optimal error below the same threshold (unless the best estimator is trivial). Our approach uses Approximate Message Passing (AMP) in conjunction with a spectral initialization. AMP algorithms have proved successful in a variety of statistical estimation tasks, and are amenable to exact asymptotic analysis via state evolution. Unfortunately, state evolution is uninformative when the algorithm is initialized near an unstable fixed point, as often happens in low-rank matrix estimation. We develop a new analysis of AMP that allows for spectral initializations. Our main theorem is general and applies beyond matrix estimation. However, we use it to derive detailed predictions for the problem of estimating a rank-one matrix in noise. Special cases of this problem are closely related---via universality arguments---to the network community detection problem for two asymmetric communities. For general rank-one models, we show that AMP can be used to construct confidence intervals and control false discovery rate. We provide illustrations of the general methodology by considering the cases of sparse low-rank matrices and of block-constant low-rank matrices with symmetric blocks (we refer to the latter as to the `Gaussian Block Model').
BibTeX
@article{montanari2021estimation,
  author = {Andrea Montanari and Ramji Venkataramanan},
  title = {{Estimation of low-rank matrices via approximate message passing}},
  journal = {The Annals of Statistics},
  year = {2021},
  doi = {10.1214/20-aos1958},
}
Figure