Oracle Based Active Set Algorithm for Scalable Elastic Net Subspace Clustering

Chong You, Chun-Guang Li, Daniel P. Robinson, Rene Vidal; Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016, pp. 3928-3937

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 l_1, l_2 or nuclear norms. l_1 regularization is guaranteed to give a subspace-preserving affinity (i.e., there are no connections between points from different subspaces) under broad theoretical conditions, but the clusters may not be connected. l_2 and nuclear norm regularization often improve connectivity, but give a subspace-preserving affinity only for independent subspaces. Mixed l_1, l_2 and nuclear norm regularizations offer a balance between the subspace-preserving and connectedness properties, but this comes at the cost of increased computational complexity. This paper studies the geometry of the elastic net regularizer (a mixture of the l_1 and l_2 norms) and uses it to derive a provably correct and scalable active set method for finding the optimal coefficients. Our geometric analysis also provides a theoretical justification and a geometric interpretation for the balance between the connectedness (due to l_2 regularization) and subspace-preserving (due to l_1 regularization) properties for elastic net subspace clustering. Our experiments show that the proposed active set method not only achieves state-of-the-art clustering performance, but also efficiently handles large-scale datasets.

Related Material


[pdf] [video]
[bibtex]
@InProceedings{You_2016_CVPR,
author = {You, Chong and Li, Chun-Guang and Robinson, Daniel P. and Vidal, Rene},
title = {Oracle Based Active Set Algorithm for Scalable Elastic Net Subspace Clustering},
booktitle = {Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)},
month = {June},
year = {2016}
}