Hyperplane Clustering Via Dual Principal Component Pursuit
This addresses hyperplane clustering problems in computer vision and data analysis, offering a theoretical foundation and improved performance, though it is incremental as it builds on an existing algorithm.
The authors extended the Dual Principal Component Pursuit (DPCP) algorithm to cluster data from a union of hyperplanes, proving that under certain conditions, the non-convex problem has a unique global solution equal to the normal vector of the dominant hyperplane. Experiments showed DPCP-based methods dramatically outperform state-of-the-art on synthetic data and are competitive on 3D plane clustering for Kinect data.
We extend the theoretical analysis of a recently proposed single subspace learning algorithm, called Dual Principal Component Pursuit (DPCP), to the case where the data are drawn from of a union of hyperplanes. To gain insight into the properties of the $\ell_1$ non-convex problem associated with DPCP, we develop a geometric analysis of a closely related continuous optimization problem. Then transferring this analysis to the discrete problem, our results state that as long as the hyperplanes are sufficiently separated, the dominant hyperplane is sufficiently dominant and the points are uniformly distributed inside the associated hyperplanes, then the non-convex DPCP problem has a unique global solution, equal to the normal vector of the dominant hyperplane. This suggests the correctness of a sequential hyperplane learning algorithm based on DPCP. A thorough experimental evaluation reveals that hyperplane learning schemes based on DPCP dramatically improve over the state-of-the-art methods for the case of synthetic data, while are competitive to the state-of-the-art in the case of 3D plane clustering for Kinect data.