Estimation of (near) low-rank matrices with noise and high-dimensional scaling

By Sahand N. Negahban, Martin J. Wainwright. International Conference on Machine Learning, 2009

602 citations recorded by the source corpus.

We study an instance of high-dimensional statistical inference in which the goal is to use N noisy observations to estimate a matrix Θ+ ∈ ℝk×p that is assumed to be either exactly low rank, or "near" low-rank, meaning that it can be well-approximated by a matrix with low rank. We consider an M-estimator based on regularization by the trace or nuclear norm over matrices, and analyze its performance under high-dimensional scaling. We provide non-asymptotic bounds on the Frobenius norm error that hold for a general class of noisy observation models, and apply to both exactly low-rank and approximately low-rank matrices. We then illustrate their consequences for a number of specific learning models, including low-rank multivariate or multi-task regression, system identification in vector autoregressive processes, and recovery of low-rank matrices from random projections. Simulations show excellent agreement with the high-dimensional scaling of the error predicted by our theory.

Subfields: Computational Mechanics, Computer Networks and Communications, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/a205ffddbd10b0a2be6953467a9d749aaa6c27d8

How researchers see this paper

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

In Computational Mechanics

In Computer Networks and Communications

In Statistics and Probability

Citations in the corpus

Estimation of high-dimensional low-rank matrices (2009, methodology): “6 An assumption used in this context in Negahban and Wainwright (2011) is that N > mT (in our notation), which excludes the high-dimensional case mT ≫ N that we are mainly interested in Cand`es and Plan (2010b) consider approximately low-rank matrices, explore the closely related matrix Dantzig…”
Finding and Leveraging Structure in Learning Problems (2012, neutral): “Wainwright [144] and Koltchinskii et al.”
Sparse PCA: Optimal rates and adaptive estimation (2012, background): “Negahban and Wainwright [40] studied (near) low-rank matrix recovery by M-estimators under restricted strong convexity based on the penalized nuclear norm minimization over matrices.”
Joint variable and rank selection for parsimonious estimation of high-dimensional matrices (2011, methodology): “For penalties proportional to the nuclear norm, we refer to Yuan et al. (2007), Candès and Plan (2010), Negahban and Wainwright (2011), Rohde and Tsybakov (2011).”
NBER WORKING PAPER SERIES MATRIX COMPLETION METHODS FOR CAUSAL PANEL DATA MODELS (2018, neutral): “An example of such restriction is given by Negahban and Wainwright (2012) where they assume L∗ is not too spiky.”
Robust multi-task feature learning (2012, background): “On the contrary, algorithms under implicit structure sharing do not explicitly impose all tasks to share certain parameters, but they implicitly capture some common structures; for example, the algorithms in [29, 24] constrain all tasks to share a common low rank subspace and the algorithms in [27, ”
Geometric median and robust estimation in Banach spaces (2013, positive): “In this section, we mainly follow the approach of [23] (Chapter 9) which deals with an important case of sub-Gaussian design (also, see [10,31] for a discussion of related problems), and use results of this work as a basis for our exposition.”
Noisy matrix decomposition via convex relaxation: Optimal rates in high dimensions (2011, background): “nd each row of B∗ as a feature. 4 In many applications, it is natural to assume that the feature weightings—i.e., that is, the vectors β∗ j ∈ R d2—exhibit some degree of shared structure across tasks [2, 32, 21, 27]. This type of shared structured can be modeled by imposing a low-rank structure; for”
Statistical Learning with Sparsity: The Lasso and Generalizations (2015, methodology): “See the papers by Yuan, Ekici, Lu and Monteiro (2007), Negahban and Wainwright (2011a), and Rohde and Tsybakov (2011) for further details and benefits of this unified approach.”
High-dimensional regression with noisy and missing data: Provable guarantees with non-convexity (2011, methodology): “nd let ˙2 = sup jjjjQjjj op . Then for all t> p2 m , we have P 1 n mkYk2 2 E(kYk2 2) >4t˙2 2exp m t p2 2 2 + 2exp( m=2): 37 Proof. This result is a generalization of Lemma I.2 in the paper [15]. By denition, the random vector Y is a mixture of random vectors of the form p Q jX j, where X j˘N”
Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees (2015, background): “It is well known [54, 50] that RIP holds for various random ensembles.”
Sparse multi-task reinforcement learning (2014, positive): “In [22], they consider a general generative model where the samples z i,a,t are generated as z i,a,t = X(W k a )i,t + η k i,a,t, where X is a generic operator and η i,a,t is an observation noise.”
A Dirty Model for Multi-task Learning (2010, positive): “in compressed sensing [3] and LASSO [14]), low-rank structure [13, 9], or spars e graphical model structure [12].”
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].”
Few-Shot Learning via Learning the Representation, Provably (2020, background): “However, the rates will depend inversely on the minimum restricted eigenvalue (Negahban and Wainwright, 2011), which is potentially very small.”
Analysis of elliptical copula correlation factor model with Kendall's tau (2013, positive): “Our setting is an extension of the low-rank matrix approximation problem [31, 34, 37].”
Optimal selection of reduced rank estimators of high-dimensional matrices (2010, result): “…we give a simple proof of this result in Appendix A. Similar results for the NNP estimator of A in the general model y = X ( A ) + ε , where X is a random linear map, have been obtained by Negahban and Wainwright (2009) and Cand`es and Plan (2010), each under diﬀerent sets of assumptions on X .”
An Overview on the Estimation of Large Covariance and Precision Matrices (2015, positive): “See, for example, Candès and Recht (2009); Koltchinskii et al. (2011); Fan et al. (2011); Negahban and Wainwright (2011); Cai et al. (2013); Ma (2013).”