Towards Faster Rates and Oracle Property for Low-Rank Matrix Estimation
arXiv:1505.04780
Abstract
We present a unified framework for low-rank matrix estimation with nonconvex penalties. We first prove that the proposed estimator attains a faster statistical rate than the traditional low-rank matrix estimator with nuclear norm penalty. Moreover, we rigorously show that under a certain condition on the magnitude of the nonzero singular values, the proposed estimator enjoys oracle property (i.e., exactly recovers the true rank of the matrix), besides attaining a faster rate. As far as we know, this is the first work that establishes the theory of low-rank matrix estimation with nonconvex penalties, confirming the advantages of nonconvex penalties for matrix completion. Numerical experiments on both synthetic and real world datasets corroborate our theory.
arXiv comment29 pages, 1 figure, 2 tables
References in corpus (12)
- Nearly unbiased variable selection under minimax concave penalty
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
- Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
- Estimation of high-dimensional low-rank matrices
- A Unified Framework for High-Dimensional Analysis of M-Estimators with Decomposable Regularizers
- Generalized Nonconvex Nonsmooth Low-Rank Minimization
- A General Iterative Shrinkage and Thresholding Algorithm for Non-convex Regularized Optimization Problems
- Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima
- Large-Scale Convex Minimization with a Low-Rank Constraint
- Matrix Completion via Max-Norm Constrained Optimization
- Exponential Family Matrix Completion under Structural Constraints
- Fast Low-Rank Matrix Learning with Nonconvex Regularization