University of Cambridge > Talks.cam > Signal Processing and Communications Lab Seminars > Estimating low-rank matrices via approximate message passing

Estimating low-rank matrices via approximate message passing

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Dr Ramji Venkataramanan.

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

This talk is part of the Signal Processing and Communications Lab Seminars series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2018 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity