Hyperplane Clustering via Dual Principal Component Pursuit
[edit]
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:34723481, 2017.
Abstract
Stateoftheart methods for clustering data drawn from a union of subspaces are based on sparse and lowrank representation theory and convex optimization algorithms. Existing results guaranteeing the correctness of such methods require the dimension of the subspaces to be small relative to the dimension of the ambient space. When this assumption is violated, as is, e.g., in the case of hyperplanes, existing methods are either computationally too intensive (e.g., algebraic methods) or lack sufficient theoretical support (e.g., KHyperplanes or RANSAC). In this paper we provide theoretical and algorithmic contributions to the problem of clustering data from a union of hyperplanes, by extending a recent subspace learning method called Dual Principal Component Pursuit (DPCP) to the multihyperplane case. We give theoretical guarantees under which, the nonconvex $\ell_1$ problem associated with DPCP admits a unique global minimizer equal to the normal vector of the most dominant hyperplane. Inspired by this insight, we propose sequential (RANSACstyle) and iterative (KHyperplanesstyle) hyperplane learning DPCP algorithms, which, via experiments on synthetic and real data, are shown to outperform or be competitive to the stateoftheart.
Related Material


