Constrained low-rank matrix estimation

With Lenka Zdeborova (IPhT)

Constrained low-rank matrix estimation

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 present a framework to study the constrained low-rank matrix estimation for a general prior on the factors, and a general output channel through which the matrix is observed. We draw a parallel with the study of vector-spin glass models – presenting a unifying way to study a number of inference and learning problems considered previously in separate works. We consider a probabilistic model of constrained low-rank matrix estimation where the factors are drawn uniformly at random. This is closely related to the popular spiked covariance model that is used to model for instance sparse PCA . 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. 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.

Add to your calendar or Include in your list