Scalable Nuclear-norm Minimization by Subspace Pursuit Proximal Riemannian Gradient
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 $r$. 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.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringMatrix CompletionSimilar Papers 제목 키워드 기반
Scalable Sparse Subspace Clustering by Orthogonal Matching Pursuit
Subspace clustering methods based on $\ell_1$, $\ell_2$ or nuclear norm regularization have become very popular due to their simplicity, theoretical guarantees and empirical success. However, the choice of the regularize…
ClusteringFace ClusteringImage ClusteringParallel Active Subspace Decomposition for Scalable and Efficient Tensor Robust Principal Component Analysis
Tensor robust principal component analysis (TRPCA) has received a substantial amount of attention in various fields. Most existing methods, normally relying on tensor nuclear norm minimization, need to pay an expensive c…
Subspace clustering based on low rank representation and weighted nuclear norm minimization
Subspace clustering refers to the problem of segmenting a set of data points approximately drawn from a union of multiple linear subspaces. Aiming at the subspace clustering problem, various subspace clustering algorithm…
ClusteringRobust Orthonormal Subspace Learning: Efficient Recovery of Corrupted Low-rank Matrices
Low-rank matrix recovery from a corrupted observation has many applications in computer vision. Conventional methods address this problem by iterating between nuclear norm minimization and sparsity minimization. However,…
Dual Principal Component Pursuit: Improved Analysis and Efficient Algorithms
Recent methods for learning a linear subspace from data corrupted by outliers are based on convex L1 and nuclear norm optimization and require the dimension of the subspace and the number of outliers to be sufficiently s…