Abstract
Subspace clustering methods like Low-Rank Representation (LRR) have proven effective for grouping high-dimensional data into low-dimensional subspaces. However, LRR's reliance on convex optimization leads to $O(n^3)$ time complexity and $O(n^2)$ memory requirements, limiting its applicability to large-scale datasets. This paper presents NLRR, a non-convex reformulation of LRR based on matrix factorization. By decomposing the representation matrix into smaller factors, NLRR achieves significant speedups and memory savings. Furthermore, the framework allows for the seamless integration of additional structural constraints, such as sparsity, leading to the Elastic NLRR (NLRR21) variant. Experimental results on synthetic and MNIST datasets demonstrate that NLRR outperforms traditional LRR in both efficiency and clustering accuracy.
Introduction
In many real-world applications, data points are drawn from a union of low-dimensional subspaces. Subspace clustering aims to identify these underlying structures. LRR has emerged as a state-of-the-art approach by seeking a low-rank representation of the data. Despite its mathematical elegance, LRR faces two primary challenges: scalability and inflexibility. As the number of samples $n$ grows, the computational burden becomes prohibitive. Additionally, incorporating secondary constraints like sparsity into the convex LRR objective is mathematically complex.
Methodology
The core innovation of NLRR is the factorization of the nuclear norm. Instead of optimizing for the full $n \times n$ matrix $X$, the authors decompose it into $X = UV^\top$, where $U$ and $V$ are smaller matrices of size $n \times d$ and $n \times d$, respectively ($d \ll n$).
The Dummy Variable Trick
To optimize this non-convex objective efficiently, the authors introduce a dummy variable $D = AU$. This decoupling allows for a stochastic block coordinate update scheme, significantly reducing the per-iteration cost. This approach transforms the problem from a computational nightmare into a routine task for large datasets.
Elastic NLRR
By adding an $\ell_1$ penalty to the factor $V$, the authors derive NLRR21. This "Elastic" variant encourages representations that are both low-rank and sparse, which is particularly beneficial when dealing with disjoint subspaces. This formulation also exhibits a "group effect," where similar dictionary atoms receive similar weights, enhancing robustness to noise compared to standard sparse methods like Lasso.
Key Results
The performance of NLRR was evaluated against standard LRR and Sparse Subspace Clustering (SSC) using both synthetic data and the MNIST digit dataset.
Robustness and Recovery
In synthetic tests involving varying levels of data corruption and subspace ranks, NLRR demonstrated superior robustness. While LRR's performance degrades as corruption increases, NLRR maintains high recovery accuracy across a broader range of parameters, as shown in the phase transition heatmaps.
Accuracy and Sparsity
On the MNIST-10K dataset, the Elastic NLRR variant achieved a clustering accuracy of approximately 59.7%, significantly higher than standard LRR (55.2%) and SSC (44.9%). The framework's ability to maintain high accuracy while increasing the number of subspaces is a key advantage, especially when the dictionary is the data itself ($A=Z$).
Computational Efficiency
NLRR provides a dramatic reduction in processing time. For 2,000 samples, NLRR is nearly 4x faster than LRR. This gap widens as the dataset size increases; on the 10,000-sample set, NLRR completed the task in 15 minutes, while LRR required 24 minutes and significantly more memory.
Conclusion
NLRR offers a powerful and scalable alternative to traditional LRR. By leveraging matrix factorization and a non-convex optimization framework, it overcomes the computational bottlenecks of convex programs while providing greater flexibility for structural regularization. The resulting unified framework bridges the gap between low-rank representation, dictionary learning, and sparse clustering, making it a robust tool for modern big data analysis.
Summary updated