Estimation of high-dimensional low-rank matrices

DOI10.1214/10-AOS860zbMATH Open1215.62056arXiv0912.5338OpenAlexW2281296685MaRDI QIDQ548539FDOQ548539

Authors: Angelika Rohde, Alexandre B. Tsybakov 

Publication date: 29 June 2011

Published in: The Annals of Statistics (Search for Journal in Brave)

Abstract: Suppose that we observe entries or, more generally, linear combinations of entries of an unknown $mimesT$-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, $pleq1$. 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 $qin[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.

Full work available at URL: https://arxiv.org/abs/0912.5338

Recommendations

• Estimation of (near) low-rank matrices with noise and high-dimensional scaling
• Robust low-rank matrix estimation
• Rank penalized estimators for high-dimensional matrices
• High‐dimensional covariance matrix estimation using a low‐rank and diagonal decomposition
• Estimation of matrices with row sparsity
• Optimal selection of reduced rank estimators of high-dimensional matrices
• Degrees of freedom in low rank matrix estimation
• Nonparametric estimation of low rank matrix valued function
• Estimation of low-rank matrices via approximate message passing
• Sparse and low-rank covariance matrix estimation

zbMATH Keywords

empirical processsparse recoverySchatten normpenalized least-squares estimatorquasi-convex Schatten class embeddings

Mathematics Subject Classification ID

Point estimation (62F10) Nonparametric estimation (62G05) Estimation in multivariate analysis (62H12)

Cites Work

• Matrix completion from noisy entries
• Simultaneous analysis of Lasso and Dantzig selector
• High-dimensional graphs and variable selection with the Lasso
• Title not available (Why is that?)
• A unified framework for high-dimensional analysis of \(M\)-estimators with decomposable regularizers
• Regularized estimation of large covariance matrices
• Remarks on Inequalities for Large Deviation Probabilities
• Introduction to nonparametric estimation
• Exact matrix completion via convex optimization
• Title not available (Why is that?)
• Estimation of (near) low-rank matrices with noise and high-dimensional scaling
• Optimal selection of reduced rank estimators of high-dimensional matrices
• The risk inflation criterion for multiple regression
• High-dimensional covariance estimation by minimizing \(\ell _{1}\)-penalized log-determinant divergence
• Decoding by Linear Programming
• Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
• Title not available (Why is that?)
• Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
• Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• Aggregation for Gaussian regression
• Oracle inequalities and optimal inference under group sparsity
• User-friendly tail bounds for sums of random matrices
• Optimal rates of convergence for covariance matrix estimation
• Title not available (Why is that?)
• Title not available (Why is that?)
• \(c_ p\)
• Entropy Numbers and Approximation Numbers in Function Spacess
• Title not available (Why is that?)
• Exponential screening and optimal rates of sparse estimation
• Consistency of trace norm minimization
• Title not available (Why is that?)
• Recovering Low-Rank Matrices From Few Coefficients in Any Basis
• A simpler approach to matrix completion
• Title not available (Why is that?)
• Learning Theory
• Reconstruction and subgaussian operators in asymptotic geometric analysis
• A new approach to collaborative filtering: operator estimation with spectral regularization
• Title not available (Why is that?)
• Square root penalty: Adaption to the margin in classification and in edge estimation
• High-dimensional analysis of semidefinite relaxations for sparse principal components
• On spectral learning
• Some problems in asymptotic convex geometry and random matrices motivated by numerical algorithms
• Title not available (Why is that?)

Cited In (only showing first 100 items - show all)

• A shrinkage principle for heavy-tailed data: high-dimensional robust low-rank matrix recovery
• High‐dimensional covariance matrix estimation using a low‐rank and diagonal decomposition
• Exact minimum rank approximation via Schatten \(p\)-norm minimization
• Low rank multivariate regression
• Low rank estimation of similarities on graphs
• Noisy matrix decomposition via convex relaxation: optimal rates in high dimensions
• Entropy numbers of embeddings of Schatten classes
• Direct shrinkage estimation of large dimensional precision matrix
• Reconstruction of a high-dimensional low-rank matrix
• Bayesian methods for low-rank matrix estimation: short survey and theoretical study
• Reconstruction of a low-rank matrix in the presence of Gaussian noise
• Optimal large-scale quantum state tomography with Pauli measurements
• Regularization and the small-ball method. I: Sparse recovery
• Matrix estimation by universal singular value thresholding
• Efficient estimation of approximate factor models via penalized maximum likelihood
• Matrix completion with covariate information
• \(S_{1/2}\) regularization methods and fixed point algorithms for affine rank minimization problems
• Inference on low-rank data matrices with applications to microarray data
• Von Neumann entropy penalization and low-rank matrix estimation
• Noisy matrix completion: understanding statistical guarantees for convex relaxation via nonconvex optimization
• Noisy low-rank matrix completion with general sampling distribution
• Robust low-rank matrix estimation
• Sparse PCA: optimal rates and adaptive estimation
• Minimax risk of matrix denoising by singular value thresholding
• Matrix completion via max-norm constrained optimization
• Geometric inference for general high-dimensional linear inverse problems
• Oracle posterior contraction rates under hierarchical priors
• Estimating high-dimensional covariance and precision matrices under general missing dependence
• A rank-corrected procedure for matrix completion with fixed basis coefficients
• Estimating structured high-dimensional covariance and precision matrices: optimal rates and adaptive estimation
• Max-norm optimization for robust matrix recovery
• Inference for low-rank models
• Estimation of matrices with row sparsity
• Nonparametric estimation of low rank matrix valued function
• Rank penalized estimators for high-dimensional matrices
• Low rank estimation of smooth kernels on graphs
• Low-Rank Matrix Estimation from Rank-One Projections by Unlifted Convex Optimization
• ROP: matrix recovery via rank-one projections
• High dimensional matrix estimation with unknown variance of the noise
• Asymptotic equivalence of quantum state tomography and noisy matrix completion
• Nonlinear shrinkage estimation of large-dimensional covariance matrices
• Fast global convergence of gradient methods for high-dimensional statistical recovery
• On the strong convergence of the optimal linear shrinkage estimator for large dimensional covariance matrix
• Matrix completion with nonconvex regularization: spectral operators and scalable algorithms
• Geometric median and robust estimation in Banach spaces
• A unified framework for high-dimensional analysis of \(M\)-estimators with decomposable regularizers
• Adaptive estimation of the copula correlation matrix for semiparametric elliptical copulas
• High-dimensional covariance matrix estimation with missing observations
• Estimation of (near) low-rank matrices with noise and high-dimensional scaling
• Optimal selection of reduced rank estimators of high-dimensional matrices
• Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion
• Joint variable and rank selection for parsimonious estimation of high-dimensional matrices
• Cross: efficient low-rank tensor completion
• Stable estimation of a covariance matrix guided by nuclear norm penalties
• Decomposable norm minimization with proximal-gradient homotopy algorithm
• Near-optimal estimation of simultaneously sparse and low-rank matrices from nested linear measurements
• Robust matrix completion
• High-dimensional regression with unknown variance
• Concentration inequalities for matrix martingales in continuous time
• Degrees of freedom in low rank matrix estimation
• Entrywise Estimation of Singular Vectors of Low-Rank Matrices With Heteroskedasticity and Dependence
• Fast Estimation of Approximate Matrix Ranks Using Spectral Densities
• Matrix Completion Methods for Causal Panel Data Models
• Low-rank matrix recovery under heavy-tailed errors
• Simultaneous Decorrelation of Matrix Time Series
• Matrix Completion under Low-Rank Missing Mechanism
• An efficient semi-proximal ADMM algorithm for low-rank and sparse regularized matrix minimization problems with real-world applications
• On matrix estimation under monotonicity constraints
• Low-rank diffusion matrix estimation for high-dimensional time-changed Lévy processes
• An Exact and Robust Conformal Inference Method for Counterfactual and Synthetic Controls
• Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
• Approximation, Gelfand, and Kolmogorov numbers of Schatten class embeddings
• Double fused Lasso regularized regression with both matrix and vector valued predictors
• Robust matrix estimations meet Frank-Wolfe algorithm
• Sparse and Low-Rank Matrix Quantile Estimation With Application to Quadratic Regression
• Exponential weights in multivariate regression and a low-rankness favoring prior
• Title not available (Why is that?)
• Estimation bounds and sharp oracle inequalities of regularized procedures with Lipschitz loss functions
• Bootstrap-based regularization for low-rank matrix estimation
• Regularization and the small-ball method. II: Complexity dependent error rates
• High-dimensional latent panel quantile regression with an application to asset pricing
• Adaptive estimation of the rank of the coefficient matrix in high-dimensional multivariate response regression models
• Statistically optimal and computationally efficient low rank tensor completion from noisy entries
• Tight risk bound for high dimensional time series completion
• Distributed estimation in heterogeneous reduced rank regression: with application to order determination in sufficient dimension reduction
• Regularization parameter selection for the low rank matrix recovery
• Bayesian singular value regularization via a cumulative shrinkage process
• Provable accelerated gradient method for nonconvex low rank optimization
• Understanding Implicit Regularization in Over-Parameterized Single Index Model
• Global optimality condition and fixed point continuation algorithm for non-Lipschitz \(\ell_p\) regularized matrix minimization
• High-dimensional varying index coefficient models via Stein's identity
• The analysis of multivariate data using semi-definite programming
• Linear models based on noisy data and the Frisch scheme
• A generalized likelihood ratio test for normal mean when \(p\) is greater than \(n\)
• Robust recovery of Robinson property in \(L^p\)-graphons: a cut-norm approach
• High dimensional deformed rectangular matrices with applications in matrix denoising
• A framework of regularized low-rank matrix models for regression and classification
• HIGH DIMENSIONAL ESTIMATION VIA SUM-OF-SQUARES PROOFS
• Gelfand numbers of embeddings of Schatten classes
• Low-Rank Regression Models for Multiple Binary Responses and their Applications to Cancer Cell-Line Encyclopedia Data

This page was built for publication: Estimation of high-dimensional low-rank matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q548539)