Estimation of Low-Rank Matrices via Approximate Message Passing

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. The analysis of this estimator 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”). Special cases of these models are closely related to the community detection problem. We show how the proposed estimator can be used to construct asymptotically valid confidence intervals, and find that in many cases of interest, it can achieve Bayes-optimal accuracy above the spectral threshold.

Joint work with Andrea Montanari. The talk will be based on the following paper: https://arxiv.org/abs/1711.01682

• Speaker: Dr Ramji Venkataramanan
• Wednesday 31 October 2018, 14:00–15:00
• Venue: CMS, MR15.
• Series: CCIMI Seminars; organiser: J.W.Stevens.