Stochastic gradient methods for matrix completion

Details

Supervisors

Absil, Pierre-Antoine

Faculty

Ecole polytechnique de Louvain

Degree label

Master [120] : ingénieur civil en mathématiques appliquées

Abstract

A common hurdle for handling high-dimensional data is the fact that the observations are often incomplete. The low-rank matrix completion problem attempts to overcome this hurdle by recovering this missing data in a large data set. The most famous application of low-rank matrix completion are recommender systems, but predicting missing values in a database is used in a diverse set of fields including control, system identification and statistics, just to name a few. The method used in this thesis is based on optimization on manifolds, since the rank is fixed beforehand, and the error is minimized. The number of data points being very large, we use a stochastic gradient descent method. This method is scaled, i.e., efficient preconditioners are computed to resolve the issue of scale invariance. Two families of sequences of data points are defined, “Smart shuffling” and “Weighted shuffling”, in order to improve the slow convergence obtained when the data points are visited in a cyclic order. Numerical comparisons show that the smart shuffling performs like a random sequence, and the weighted shuffling improves the convergence.