Learning Structured Low-Rank Representation via Matrix Factorization

Jie Shen, Ping LiAISTATS 2016 · OpenReview

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.

Comparison of robustness between LRR and NLRR across varying corruption levels and rank ratios.

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$).

Accuracy and sparsity metrics for LRR and NLRR variants under different dictionary settings (A=Z and A=A0).

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

Abstract

A vast body of recent works in the literature has shown that exploring structures beyond data low-rankness can boost the performance of subspace clustering methods such as Low-Rank Representation (...
BibTeX
@inproceedings{shen2016learning,
  author = {Jie Shen and Ping Li},
  title = {{Learning Structured Low-Rank Representation via Matrix Factorization}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2016},
  url = {https://openreview.net/forum?id=yMDYnDlVwKo},
}
Figure