SIAM MDS20 MS13 Advances in Subspace Learning and Clustering Mini-Symposium

Abstract.: State-of-the-art subspace clustering methods are based on expressing each data point as a linear combination of other data points while regularizing the matrix of coefficients with sparse, ℓ2ℓ2 or low-rank regularizations. Sparse regularization is guaranteed to give a subspace-preserving affinity (i.e., there are no connections between points from different subspaces) under broad conditions, but the clusters may not be connected. Low-rank and ℓ2ℓ2 regularization often improve connectivity, but give a subspace-preserving affinity only for independent subspaces. Moreover, the applicability of such methods to large datasets has been limited due to time complexity and/or memory footprint issues.

In this talk, I present a novel subspace clustering approach based on the elastic net regularizer (a mixture of the sparse and ℓ2ℓ2 regularizers). Our geometric analysis shows that this method maintains subspace-preserving property (due to sparse regularization) while enhances connectedness (due to ℓ2ℓ2 regularization), therefore achieves better clustering performance. We also present two provably correct and scalable active support algorithms for solving the elastic net regularized optimization problem. Experiments on synthetic data verify our theoretical analysis, and show that the proposed methods efficiently handle datasets with 1M data points. In addition, our methods achieve >97>97% clustering accuracy on 70,00070,000 images in the MNIST dataset in about 1 hour.