Nuclear norm penalization and optimal rates for noisy low rank matrix completion

This paper deals with the trace regression model where n entries or linear of entries of an unknown m₁\× m₂ matrix A₀ corrupted by are observed. We propose a new nuclear norm penalized estimator of A₀ establish a general sharp oracle inequality for this estimator for values of n,m₁,m₂ under the condition of isometry in expectation. this method is applied to the matrix completion problem. In this case, the admits a simple explicit form and we prove that it satisfies oracle with faster rates of convergence than in the previous works. They valid, in particular, in the high-dimensional setting m₁m₂\ n. We that the obtained rates are optimal up to logarithmic factors in a minimax and also derive, for any fixed matrix A₀, a non-minimax lower bound on rate of convergence of our estimator, which coincides with the upper bound to a constant factor. Finally, we show that our procedure provides an exact of the rank of A₀ with probability close to 1. We also discuss the learning setting where there is no underlying model determined by₀ and the aim is to find the best trace regression model approximating the.