Oracle Based Active Set Algorithm for Scalable Elastic Net Subspace Clustering

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 ${\ell }_1$, ${\ell }_2$ or nuclear norms. ${\ell }_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. ${\ell }_2$ and nuclear norm regularization often improve connectivity, but give a subspace-preserving affinity only for independent subspaces. Mixed ${\ell }_1$, ${\ell }_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 ${\ell }_1$ and ${\ell }_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 ${\ell }_2$ regularization) and subspace-preserving (due to ${\ell }_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.

15 pages, 6 figures, accepted to CVPR 2016 for oral presentation

References in corpus (14)

• Least Angle Regression
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Rejoinder to "Least angle regression" by Efron et al
• Linearized Alternating Direction Method with Adaptive Penalty for Low-Rank Representation
• A geometric analysis of subspace clustering with outliers
• Filtrated Spectral Algebraic Subspace Clustering
• Sparse Prediction with the $k$-Support Norm

Cited by in corpus (13)

• Structured Sparse Subspace Clustering: A Joint Affinity Learning and Subspace Clustering Framework
• Learning Diverse and Discriminative Representations via the Principle of Maximal Coding Rate Reduction
• Scalable and Robust Sparse Subspace Clustering Using Randomized Clustering and Multilayer Graphs
• Scalable Sparse Subspace Clustering by Orthogonal Matching Pursuit
• Deep Subspace Clustering Networks
• Efficient Sparse Subspace Clustering by Nearest Neighbour Filtering
• Theoretical Analysis of Sparse Subspace Clustering with Missing Entries
• Spatial-Temporal Union of Subspaces for Multi-body Non-rigid Structure-from-Motion
• Pattern Dependence Detection using n-TARP Clustering
• Learning Self-Expression Metrics for Scalable and Inductive Subspace Clustering
• Sparse-Dense Subspace Clustering
• Leveraging Union of Subspace Structure to Improve Constrained Clustering
• Subspace Clustering through Sub-Clusters