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

Abstract

High-dimensional inference refers to problems of statistical estimation in which the ambient dimension of the data may be comparable to or possibly even larger than the sample size. We study an instance of high-dimensional inference in which the goal is to estimate a matrix ${\Theta }^{\ast }\in {\Re }^{k\times p}$ on the basis of $N$ noisy observations, and the unknown matrix ${\Theta }^{\ast }$ 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 then illustrate their consequences for a number of specific matrix models, including low-rank multivariate or multi-task regression, system identification in vector autoregressive processes, and recovery of low-rank matrices from random projections. Simulation results show excellent agreement with the high-dimensional scaling of the error predicted by our theory.

Appeared as Stat. technical report, UC Berkeley

References in corpus (7)

• Estimation of high-dimensional low-rank matrices
• A Unified Framework for High-Dimensional Analysis of M-Estimators with Decomposable Regularizers
• Consistency of trace norm minimization
• Tight oracle bounds for low-rank matrix recovery from a minimal number of random measurements
• Low-rank matrix factorization with attributes
• Guaranteed Minimum Rank Approximation from Linear Observations by Nuclear Norm Minimization with an Ellipsoidal Constraint
• The Benefit of Group Sparsity

Cited by in corpus (5)

• Spectral Experts for Estimating Mixtures of Linear Regressions
• CUR Algorithm for Partially Observed Matrices
• Optimal Schatten-q and Ky-Fan-k Norm Rate of Low Rank Matrix Estimation
• Orthogonal Rank-One Matrix Pursuit for Low Rank Matrix Completion
• Sparse Trace Norm Regularization