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

By Vladimir Koltchinskii, Alexandre B. Tsybakov, Karim Lounici. 2010

694 citations recorded by the source corpus.

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

Subfields: Applied Mathematics, Computational Mechanics

View Paper: https://www.semanticscholar.org/paper/3fe293838ee90fc0bd1d11121717616b1fe477ed

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Computational Mechanics

Citations in the corpus

Operator Splitting for a Homogeneous Embedding of the Linear Complementarity Problem (2020, background): “Quadratic objectives over the semideﬁnite cone come up when solving matrix reconstruction and low rank matrix completion problems, where the goal is to ﬁnd a positive semideﬁnite matrix with low rank that minimizes the Frobenius norm to some reference [34, 35].”
How Correlations Influence Lasso Prediction (2012, methodology): “We ﬁnd that the larger the correlations are, the smaller the optimal tuning parameter is.”
Confidence intervals for low dimensional parameters in high dimensional linear models (2011, methodology): “…Bickel et al., 2009; Koltchinskii, 2009; Meinshausen and Yu, 2009; van de Geer and Bühlmann, 2009; Wainwright, 2009a; Zhang, 2009; Ye and Zhang, 2010; Koltchinskii et al., 2011; Sun and Zhang, 2010), non-convex penalized methods (Frank and Friedman, 1993; Fan and Li, 2001; Fan and Peng, 2004; Kim…”
Detection of a sparse submatrix of a high-dimensional noisy matrix (2011, background): “For example, matrix completion for low rank matrices with the nuclear norm penalization has been studied by Koltchinskii, Lounici and Tsybakov [9].”
Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees (2015, background): “, see the papers [18, 54, 51, 50, 22, 42] and references therein).”
An Overview of Low-Rank Matrix Recovery From Incomplete Observations (2016, result): “Similar results can also be established that guarantee approximate recovery in the case of noisy observations and approximately low-rank matrices with the amount of recovery error being naturally determined by the amount of noise and degree of approximation error [27,56,57,79,81,83,84,105,119].”
Slope meets Lasso: Improved oracle bounds and optimality (2016, background): “Consider the following result based on [14, 4, 10], which is representative of the nonasymptotic bounds obtained so far for the prediction performance of the Lasso.”
Geometric median and robust estimation in Banach spaces (2013, background): “For instance, it would be interesting to obtain an estimator in the low-rank matrix completion framework [11,24] that admits strong performance guarantees for the heavy-tailed noise model.”
Sharp oracle inequalities for Least Squares estimators in shape restricted regression (2015, background): “lled adaptive oracleinequalities. Such trade-oﬀ is common in the context of sparse linear regression, where the right hand side of sparsity oracleinequalities balances approximationerror and sparsity [9, 21, 27]. This is opposed to the oracle inequality (7) where there is no trade-oﬀ, the right hand”
On the Prediction Performance of the Lasso (2014, methodology): “ front of the inﬁmum, often referred to as the leading constant of an oracle inequality (OI), is equal to one. The ﬁrst sharp OI with fast rate of convergence of the remainder term has been proved in [KLT11]. It was then reﬁned and extended to the procedure square-root Lasso (also known as the scale”
Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution (2017, background): “which coincides with the theoretical guarantee in [32, Corollary 1] and matches the minimax lower bound established in [67,89].”
On the Linear Convergence of the Proximal Gradient Method for Trace Norm Regularization (2013, background): “Indeed, such a problem arises in a wide variety of applications, including approximation algorithms [17], automatic control [5], matrix classification [20], matrix completion [6], multi–label classification [1], multi–task learning [2], network localization [7], subspace learning [24], and trace reg”
Matrix estimation by Universal Singular Value Thresholding (2012, background): “A conservative choice of λ (albeit with an unspecified constant) and a minimax lower bound that matches the upper bound up to a logarithmic factor are given in [65].”
Loss Minimization and Parameter Estimation with Heavy Tails (2013, methodology): “We demonstrate the versatility of our technique by giving further examples in sparse linear regression (Tibshirani, 1996) under heavy-tailed noise and low-rank covariance co-variance matrix approximation (Koltchinskii et al., 2011) under heavy-tailed covariate distributions.”
High-dimensional covariance matrix estimation with missing observations (2012, methodology): “Proof of Theorem 1 The proof of the first inequality adapts to covariance matrix estimation the arguments used in the trace regression problem to prove Theorems 1 and 11 in [25].”
Online linear optimization with the log-determinant regularizer (2017, background): “In this perspective, the policy class is formulated as a restricted set of matrices, say, the set of matrices of bounded trace norm, which is commonly used in collaborative filtering [7]–[10].”