Ramji Venkataramanan
Estimation of Low-Rank Matrices via Approximate Message Passing

Abstract: We consider the problem of estimating a low-rank symmetric
matrix when its entries are perturbed by Gaussian noise, a setting
often called the spiked model.  If the empirical distribution of the
entries of the spikes is known, optimal estimators that exploit this
knowledge can substantially outperform simple spectral approaches. We
discuss an estimator that uses Approximate Message Passing (AMP) in
conjunction with a spectral initialization.  We develop a 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.  As illustrations, we use our main result
to derive detailed predictions for estimating a rank-one matrix and a
block-constant low-rank matrix ("Gaussian block model"). We find that
in many cases of interest, the proposed algorithm can achieve
Bayes-optimal accuracy above the spectral threshold.

Joint work with Andrea Montanari.