Efficient Online Minimization for Low-Rank Subspace Clustering
arXiv:1503.08356
Abstract
Low-rank representation~(LRR) has been a significant method for segmenting data that are generated from a union of subspaces. It is, however, known that solving the LRR program is challenging in terms of time complexity and memory footprint, in that the size of the nuclear norm regularized matrix is -by- (where is the number of samples). In this paper, we thereby develop a fast online implementation of LRR that reduces the memory cost from to , with being the ambient dimension and being some estimated rank~(). The crux for this end is a non-convex reformulation of the LRR program, which pursues the basis dictionary that generates the (uncorrupted) observations. We build the theoretical guarantee that the sequence of the solutions produced by our algorithm converges to a stationary point of the empirical and the expected loss function asymptotically. Extensive experiments on synthetic and realistic datasets further substantiate that our algorithm is fast, robust and memory efficient.
arXiv commentShort version accepted to ICML 2016
References in corpus (14)
- 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
- SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
- A geometric analysis of subspace clustering with outliers
- Subspace Learning and Imputation for Streaming Big Data Matrices and Tensors
- Consistency of trace norm minimization
- Matrix Completion has No Spurious Local Minimum
- Stochastic Majorization-Minimization Algorithms for Large-Scale Optimization
- Clustering Partially Observed Graphs via Convex Optimization
- High-Rank Matrix Completion and Subspace Clustering with Missing Data
- Efficient and Practical Stochastic Subgradient Descent for Nuclear Norm Regularization
- Principal Component Analysis with Contaminated Data: The High Dimensional Case
- Advancing Matrix Completion by Modeling Extra Structures beyond Low-Rankness