  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').
