  The task of reconstructing a matrix given a sample of observedentries is
known as the matrix completion problem. It arises ina wide range of problems,
including recommender systems, collaborativefiltering, dimensionality
reduction, image processing, quantum physics or multi-class classificationto
name a few. Most works have focused on recovering an unknown real-valued
low-rankmatrix from randomly sub-sampling its entries.Here, we investigate the
case where the observations take a finite number of values, corresponding for
examples to ratings in recommender systems or labels in multi-class
classification.We also consider a general sampling scheme (not 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 tacklepotentially high dimensional
settings.
