Abstract

Large datasets often have an underlying low-dimensional structure that can be captured by modeling the data matrix as the sum of a low-rank matrix and a noise matrix. The goal is to estimate the low-rank part from the data matrix. A natural approach for estimating the low-rank part is via the spectrum of the data matrix. However, if the empirical distribution of the entries in the low-rank part is known, one can design estimators that substantially outperform simple spectral approaches.

In this talk we discuss an estimator that consists of an Approximate Message Passing (AMP) algorithm initialized with a spectral estimate. We obtain a sharp asymptotic characterization of the performance of this estimator, and use the result to derive detailed predictions for estimating a rank-one matrix and a block-constant low-rank matrix in Gaussian noise. Special cases of these models are closely related to the problem of community detection in stochastic block models. We show how the proposed estimator can be used to construct confidence intervals, and find that in many cases of interest, it can achieve Bayes-optimal accuracy above the spectral threshold.

(The talk will be self-contained, and will not assume familiarity with message passing algorithms.)