Title: Estimation of Low-Rank Matrices via Approximate Message Passing,
Abstract: Consider the problem of estimating a low-rank symmetric matrix when its
entries are perturbed by Gaussian noise, a setting that is known as `spiked
model' or `deformed Wigner matrix'. If the empirical distribution of the
entries of the spikes is known, optimal estimators that exploit this knowledge
can substantially outperform spectral approaches. Recent work characterizes the
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 has
proven successful in a variety of statistical problem, 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 it often happens in matrix estimation. We develop a new analysis of
AMP that allows for spectral initializations, and builds on a decoupling
between the outlier eigenvectors and the bulk in the spiked random matrix
model. 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 these 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 asymptotically valid confidence intervals. As a further
illustration, we consider the example of a block-constant low-rank matrix with
symmetric blocks, which we refer to as `Gaussian Block Model'.