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

This paper deals with the trace regression model where $n$ entries or linear\ncombinations of entries of an unknown $m_1\\times m_2$ matrix $A_0$ corrupted by\nnoise are observed. We propose a new nuclear norm penalized estimator of $A_0$\nand establish a general sharp oracle inequality for this estimator for\narbitrary values of $n,m_1,m_2$ under the condition of isometry in expectation.\nThen this method is applied to the matrix completion problem. In this case, the\nestimator admits a simple explicit form and we prove that it satisfies oracle\ninequalities with faster rates of convergence than in the previous works. They\nare valid, in particular, in the high-dimensional setting $m_1m_2\\gg n$. We\nshow…