Matrix completion : statistical and computational aspects.

Summary In this thesis we focus on low rank matrix completion methods and study some related problems. A first set of results aims at extending the existing statistical guarantees for completion models with additive sub-Gaussian noise to more general distributions. In particular, we consider multinational distributions and distributions belonging to the exponential family. For the latter, we prove the optimality (in the minimax sense) to within one logarithmic factor of the trace norm penalty estimators. A second set of results concerns the conditional gradient algorithm which is notably used to compute the previous estimators. In particular, we consider two conditional gradient algorithms in the context of stochastic optimization. We give the conditions under which these algorithms reach the performance of projected gradient algorithms.