Constrained low-rank matrix (and tensor) estimation
Lenka Zdeborova, CNRS and CEA Saclay, France, Currently at Duke for Spring Semester 2018
Friday, February 23, 2018 - 3:30pm
Low-rank matrix factorization is one of the basic methods used in data analysis for unsupervised learning of relevant features and other types of dimensionality reduction. We consider a probabilistic model of constrained low-rank matrix (or tensor) estimation where the factors are drawn uniformly at random and the low-rank matrix (or tensor) is observed through a general component0wise output channel. This is a generalization of the popular spiked covariance model with iid spikes. We present a generic methodology coming from statistical physics that leads to a closed formula for the minimum-mean-squared error achievable in this model by the Bayes-optimal estimator. We also present the corresponding approximate message passing algorithms and locate a region of parameters for which this algorithms achieves the optimal performance. We discuss intuition on computational hardness of the complementary region. Our analysis also provides results and insight on performance of commonly used spectral algorithms.
Seminars generally take place in 116 Old Chemistry Building on Fridays from 3:30 - 4:30 pm. For additional information contact: firstname.lastname@example.org or phone 919-684-8029. Sorry, but we do not have reprints available. Please feel free to contact the authors by email for follow-up information, articles, etc. Reception following seminar in 211 Old Chemistry