Estimation of high-dimensional low-rank matrices

By Angelika Rohde, Alexandre B. Tsybakov. 2009

404 citations recorded by the source corpus.

Suppose that we observe entries or, more generally, linear combinations of entries of an unknown m x T-matrix A corrupted by noise. We are particularly interested in the high-dimensional setting where the number mT of unknown entries can be much larger than the sample size N. Motivated by several applications, we consider estimation of matrix A under the assumption that it has small rank. This can be viewed as dimension reduction or sparsity assumption. In order to shrink toward a low-rank representation, we investigate penalized least squares estimators with a Schatten-p quasi-norm penalty term, p ≤ 1. We study these estimators under two possible assumptions—a modified version of the restricted isometry condition and a uniform bound on the ratio "empirical norm induced by the sampling operator/Frobenius norm." The main results are stated as nonasymptotic upper bounds on the prediction risk and on the Schatten-q risk of the estimators, where q ∈ [p, 2]. The rates that we obtain for the prediction risk are of the form rm/N (for m = T), up to logarithmic factors, where r is the rank of A. The particular examples of multi-task learning and matrix completion are worked out in detail. The proofs are based on tools from the theory of empirical processes. As a by-product, we derive bounds for the kth entropy numbers of the quasi-convex Schatten class embeddings S M p → S M 2 , p < 1, which are of independent interest.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/6c7500fd3f25946323420563329a6599e67de429

How researchers see this paper

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

In Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

Matrix estimation by Universal Singular Value Thresholding (2012, neutral): “Some notable examples are [74, 75, 65, 84, 64, 38].”
Neuron Clustering for Mitigating Catastrophic Forgetting in Supervised and Reinforcement Learning (2015, neutral): “Covariance estimation is a well-studied problem [56, 57].”
High-dimensional regression with unknown variance (2011, background): “Several recent papers [9, 20, 49, 58, 63] have investigated another strategy for the low-rank setting.”
Spectral norm of random tensors (2014, result): “This is analogous to the proof of Lemma 4 in Rohde and Tsybakov (2011).”
Sparse PCA: Optimal rates and adaptive estimation (2012, background): “Koltchinskii, Lounici and Tsybakov [32] considered estimation of low-rank matrices based on a trace regression model which includes matrix completion as a special case.”
A unified framework for high-dimensional analysis of $M$-estimators with decomposable regularizers (2009, methodology): “Techniques based on nuclear norm regularization have been studied for different statistical models, including compressed sensing [37, 62], matrix completion [15, 31, 52, 61], multitask regression [4, 10, 51, 63, 77] and system identification [23, 38, 51].”
Speedup Matrix Completion with Side Information: Application to Multi-Label Learning (2013, background): “A more general matrix recovery problem, referred to as matrix regression, was examined in [30, 36].”
Sequential Covariance-Matrix Estimation with Application to Mitigating Catastrophic Forgetting (2015, background): “An extensive body of literature concerning improved estimators in such situations exist [10], [11].”
High-dimensional covariance matrix estimation with missing observations (2012, methodology): “This estimator is the covariance version of the matrix Lasso estimator initially introduced in the matrix regression framework, see [25, 30] and the references cited therein.”
Analysis of elliptical copula correlation factor model with Kendall's tau (2013, neutral): “Our setting is an extension of the low-rank matrix approximation problem [31, 34, 37].”
Estimation of (near) low-rank matrices with noise and high-dimensional scaling (2009, methodology): “Finally, in work posted shortly after our own, Rohde and Tsybakov [47] and Can des and Plan [13] have studied certain aspects of nuclear norm minimization under high-dimensional scaling.”
Fast global convergence rates of gradient methods for high-dimensional statistical recovery (2010, background): “See the papers [10, 17] for more details on reformulating this problem as an instance of matrix regression.”
Optimal selection of reduced rank estimators of high-dimensional matrices (2010, methodology): “…2 ) entries, the RSC estimator corresponding to the penalty pen( B ) = Cσ 2 ( n 1 / 2 + q 1 / 2 ) 2 r ( B ), for any C > 1, is minimax adaptive, for matrices X having a restricted isometry property (RIP), of the type introduced and discussed in Cand`es and Plan (2010) and Rohde and Tsybakov (2010).”
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].”
Efficient Estimation of Approximate Factor Models (2012, background): “ Cai and Zhou (2012), Fan et al. (2008), Jung and Marron (2009), Witten, Tibshirani and Hastie (2009), Deng and Tsui (2010), Yuan (2010), Ledoit and Wolf (2012), El Karoui (2008), Pati et al. (2012), Rohde and Tsybakov (2011), Zhou et al. (2011), Ravikumar et al. (2011) etc. This paper focuses on hi”