Scalable Nuclear-norm Minimization by Subspace Pursuit Proximal Riemannian Gradient
arXiv:1503.02828
Abstract
Nuclear-norm regularization plays a vital role in many learning tasks, such as low-rank matrix recovery (MR), and low-rank representation (LRR). Solving this problem directly can be computationally expensive due to the unknown rank of variables or large-rank singular value decompositions (SVDs). To address this, we propose a proximal Riemannian gradient (PRG) scheme which can efficiently solve trace-norm regularized problems defined on real-algebraic variety $\mMLr$ of real matrices of rank at most . Based on PRG, we further present a simple and novel subspace pursuit (SP) paradigm for general trace-norm regularized problems without the explicit rank constraint $\mMLr$. The proposed paradigm is very scalable by avoiding large-rank SVDs. Empirical studies on several tasks, such as matrix completion and LRR based subspace clustering, demonstrate the superiority of the proposed paradigms over existing methods.
References in corpus (8)
- Robust Recovery of Subspace Structures by Low-Rank Representation
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
- The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices
- Linearized Alternating Direction Method with Adaptive Penalty for Low-Rank Representation
- Tight oracle bounds for low-rank matrix recovery from a minimal number of random measurements
- Large-Scale Convex Minimization with a Low-Rank Constraint
- Efficient and Practical Stochastic Subgradient Descent for Nuclear Norm Regularization
- A Riemannian geometry for low-rank matrix completion