Estimation of high-dimensional low-rank matrices

Abstract

Suppose that we observe entries or, more generally, linear combinations of entries of an unknown $m\times 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\le 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\in [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 $k$th entropy numbers of the quasi-convex Schatten class embeddings $S_p^M\hookrightarrow S_2^M$, $p<1$, which are of independent interest.

Published in at http://dx.doi.org/10.1214/10-AOS860 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (9)

• Regularized estimation of large covariance matrices
• A Simpler Approach to Matrix Completion
• Recovering low-rank matrices from few coefficients in any basis
• Optimal rates of convergence for covariance matrix estimation
• A New Approach to Collaborative Filtering: Operator Estimation with Spectral Regularization
• Consistency of trace norm minimization
• Optimal selection of reduced rank estimators of high-dimensional matrices
• Aggregation for Gaussian regression
• High-dimensional analysis of semidefinite relaxations for sparse principal components

Cited by in corpus (102)

• Matrix Completion Methods for Causal Panel Data Models
• Matrix estimation by Universal Singular Value Thresholding
• Nonlinear shrinkage estimation of large-dimensional covariance matrices
• An overview of low-rank matrix recovery from incomplete observations
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Sparse PCA: Optimal rates and adaptive estimation
• A Unified Framework for High-Dimensional Analysis of M-Estimators with Decomposable Regularizers
• Noisy matrix decomposition via convex relaxation: Optimal rates in high dimensions
• Geometric median and robust estimation in Banach spaces
• Optimal selection of reduced rank estimators of high-dimensional matrices
• OptShrink: An algorithm for improved low-rank signal matrix denoising by optimal, data-driven singular value shrinkage
• Minimax risk of matrix denoising by singular value thresholding
• Inference and Uncertainty Quantification for Noisy Matrix Completion
• Noisy low-rank matrix completion with general sampling distribution
• Joint variable and rank selection for parsimonious estimation of high-dimensional matrices
• ROP: Matrix recovery via rank-one projections
• Matrix Completion via Max-Norm Constrained Optimization
• On Iterative Hard Thresholding Methods for High-dimensional M-Estimation
• Poisson Matrix Recovery and Completion
• Optimal Linear Shrinkage Estimator for Large Dimensional Precision Matrix
• The Landmark Selection Method for Multiple Output Prediction
• Provable Meta-Learning of Linear Representations
• On the Strong Convergence of the Optimal Linear Shrinkage Estimator for Large Dimensional Covariance Matrix
• Universal low-rank matrix recovery from Pauli measurements
• Estimation of (near) low-rank matrices with noise and high-dimensional scaling
• Stable Estimation of a Covariance Matrix Guided by Nuclear Norm Penalties
• A Shrinkage Principle for Heavy-Tailed Data: High-Dimensional Robust Low-Rank Matrix Recovery
• Adaptive estimation of the copula correlation matrix for semiparametric elliptical copulas
• Bayesian methods for low-rank matrix estimation: short survey and theoretical study
• Optimal Estimation of Low Rank Density Matrices
• CUR Algorithm for Partially Observed Matrices
• Optimal large-scale quantum state tomography with Pauli measurements
• Geometric Inference for General High-Dimensional Linear Inverse Problems
• Rank penalized estimation of a quantum system
• Asymptotic equivalence of quantum state tomography and noisy matrix completion
• Regularization and the small-ball method II: complexity dependent error rates
• Nearest Neighbors for Matrix Estimation Interpreted as Blind Regression for Latent Variable Model
• Statistically Optimal and Computationally Efficient Low Rank Tensor Completion from Noisy Entries
• Recovering Model Structures from Large Low Rank and Sparse Covariance Matrix Estimation
• A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimation
• Statistical Inferences of Linear Forms for Noisy Matrix Completion
• Towards Faster Rates and Oracle Property for Low-Rank Matrix Estimation
• Online Similarity Prediction of Networked Data from Known and Unknown Graphs
• Fast global convergence of gradient methods for high-dimensional statistical recovery
• Estimation bounds and sharp oracle inequalities of regularized procedures with Lipschitz loss functions
• Selective Factor Extraction in High Dimensions
• Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
• Asymptotic Theory for Estimating the Singular Vectors and Values of a Partially-observed Low Rank Matrix with Noise
• On Low-rank Trace Regression under General Sampling Distribution
• A Universal Variance Reduction-Based Catalyst for Nonconvex Low-Rank Matrix Recovery
• Inter-Subject Analysis: Inferring Sparse Interactions with Dense Intra-Graphs
• Optimal Estimation and Rank Detection for Sparse Spiked Covariance Matrices
• Towards the study of least squares estimators with convex penalty
• Volume Ratio, Sparsity, and Minimaxity under Unitarily Invariant Norms
• Joint Estimation and Inference for Data Integration Problems based on Multiple Multi-layered Gaussian Graphical Models
• Detecting Latent Communities in Network Formation Models
• Approximation, Gelfand, and Kolmogorov numbers of Schatten class embeddings
• Low rank Multivariate regression
• Optimal link prediction with matrix logistic regression
• Provable Accelerated Gradient Method for Nonconvex Low Rank Optimization
• Decomposable Norm Minimization with Proximal-Gradient Homotopy Algorithm
• On Approximation Guarantees for Greedy Low Rank Optimization
• Cross: Efficient Low-rank Tensor Completion
• Confidence Region of Singular Subspaces for Low-rank Matrix Regression
• Optimal Schatten-q and Ky-Fan-k Norm Rate of Low Rank Matrix Estimation
• Optimal spectral norm rates for noisy low-rank matrix completion
• A pseudo-RIP for multivariate regression
• On a low-rank matrix single index model
• Oracle posterior contraction rates under hierarchical priors
• Estimation of low rank density matrices by Pauli measurements
• Stochastic Variance-reduced Gradient Descent for Low-rank Matrix Recovery from Linear Measurements
• A Rank-Corrected Procedure for Matrix Completion with Fixed Basis Coefficients
• Matrix Completion with Nonconvex Regularization: Spectral Operators and Scalable Algorithms
• Regularization-free estimation in trace regression with symmetric positive semidefinite matrices
• Accuracy of empirical projections of high-dimensional Gaussian matrices
• Concentration for matrix martingales in continuous time and microscopic activity of social networks
• Calibrated Multivariate Regression with Application to Neural Semantic Basis Discovery
• Low rank estimation of smooth kernels on graphs
• Adaptive Estimation of Noise Variance and Matrix Estimation via USVT Algorithm
• How well can we learn large factor models without assuming strong factors?
• Learning RUMs: Reducing Mixture to Single Component via PCA
• Poisson Matrix Completion
• Robust Reduced Rank Regression
• Intelligent Initialization and Adaptive Thresholding for Iterative Matrix Completion; Some Statistical and Algorithmic Theory for Adaptive-Impute
• Reduced rank regression via adaptive nuclear norm penalization
• Sharp Oracle Inequalities in Low Rank Estimation
• A Matrix Generalization of the Hardy-Littlewood-Pólya Rearrangement Inequality and Its Applications
• Low solution rank of the matrix LASSO under RIP with consequences for rank-constrained algorithms
• Rank-Constrained Least-Squares: Prediction and Inference
• Interacting Particle Systems on Networks: joint inference of the network and the interaction kernel
• Structured Matrix Completion with Applications to Genomic Data Integration
• High-Dimensional Dynamic Systems Identification with Additional Constraints
• Binary matrix completion with nonconvex regularizers
• Deconvolution with Unknown Error Distribution Interpreted as Blind Isotonic Regression
• Convergence rate of Bayesian tensor estimator: Optimal rate without restricted strong convexity
• Distance Shrinkage and Euclidean Embedding via Regularized Kernel Estimation
• Nonparametric Estimation of Low Rank Matrix Valued Function
• Simultaneous Matrix Diagonalization for Structural Brain Networks Classification
• High-dimensional regression with unknown variance
• Fitting Spectral Decay with the $k$-Support Norm
• Bayesian Singular Value Regularization via a Cumulative Shrinkage Process
• Adversarial Robust Low Rank Matrix Estimation: Compressed Sensing and Matrix Completion