Timezone: »

 
Poster
Probabilistic low-rank matrix completion on finite alphabets
Jean Lafond · Olga Klopp · Eric Moulines · Joseph Salmon

Tue Dec 09 04:00 PM -- 08:59 PM (PST) @ Level 2, room 210D
in Poster Session »

The task of reconstructing a matrix given a sample of observed entries is known as the \emph{matrix completion problem}. Such a consideration arises in a wide variety of problems, including recommender systems, collaborative filtering, dimensionality reduction, image processing, quantum physics or multi-class classification to name a few. Most works have focused on recovering an unknown real-valued low-rank matrix from randomly sub-sampling its entries. Here, we investigate the case where the observations take a finite numbers of values, corresponding for examples to ratings in recommender systems or labels in multi-class classification. We also consider a general sampling scheme (non-necessarily uniform) over the matrix entries. The performance of a nuclear-norm penalized estimator is analyzed theoretically. More precisely, we derive bounds for the Kullback-Leibler divergence between the true and estimated distributions. In practice, we have also proposed an efficient algorithm based on lifted coordinate gradient descent in order to tackle potentially high dimensional settings.

[ PDF] 

Author Information

Jean Lafond (Télécom ParisTech)
Olga Klopp (Université Paris Ouest)
Eric Moulines (Telecom ParisTech)
Joseph Salmon (Télécom ParisTech)

More from the Same Authors