Abstract
The problem of clustering points on a union of subspaces finds numerous applications in machine learning and computer vision, and it has been extensively studied in the past two decades. When the subspaces are low-dimensional, the problem can be formulated as a convex sparse optimization problem, for which numerous accurate, efficient and robust methods exist. When the subspaces are of high relative dimension (e.g., hyperplanes), the problem is intrinsically non-convex, and existing methods either lack theory, are computationally costly, lack robustness to outliers, or learn hyperplanes one at a time. In this paper, we propose Hyperplane ARangentment Descent (HARD), a method that robustly learns all the hyperplanes simultaneously by solving a novel non-convex non-smooth $\ell_1$ minimization problem. We provide geometric conditions under which the ground-truth hyperplane arrangement is a coordinate-wise minimizer of our objective. Furthermore, we devise efficient algorithms, and give conditions under which they converge to coordinate-wise minimizes. We provide empirical evidence that HARD surpasses state-of-the-art methods and further show an interesting experiment in clustering deep features on CIFAR-10.
Introduction
Subspace clustering is a foundational problem in machine learning, aiming to group data points that lie on a union of unknown linear subspaces. While low-dimensional subspaces are well-handled by standard sparse or low-rank optimization, high-relative-dimension subspaces—specifically hyperplanes—present a significant challenge. Existing techniques for hyperplane clustering often force a trade-off between theoretical rigor, computational efficiency, and robustness to outliers.
As shown in the comparison above, traditional techniques like RANSAC scale poorly in high dimensions, while GPCA lacks robustness. Methods like DPCP are robust but sequential, potentially propagating errors if the first hyperplane is estimated poorly. HARD (Hyperplane ARrangement Descent) addresses these gaps by providing a robust, efficient, and theoretically grounded "one-shot" approach that learns all hyperplanes simultaneously.
Methodology
The core idea of HARD is to minimize the product of distances from a point to all $K$ hyperplanes. For a point $x$ belonging to any of the hyperplanes, the product of its distances to all hyperplanes will be zero. To ensure robustness against outliers, the authors minimize the sum of these absolute products: $\sum_{i=1}^N \prod_{k=1}^K |x_i^\top b_k|$, where $b_k$ are the normal vectors of the hyperplanes.
This non-convex, non-smooth objective is solved via block coordinate descent. The paper introduces several variants:
- HARD-$\ell_1$: Updates one hyperplane normal at a time while keeping others fixed.
- HARD-$\ell_1+$: Employs a majorization-minimization strategy, bounding the $\ell_1$ norm with a quadratic term to allow for rapid updates via Singular Value Decomposition (SVD).
- HARD-Huber & HARD-Huber+: Replaces the sharp $\ell_1$ absolute value with a smoothed Huber loss, facilitating mathematical proofs of convergence to critical points.
Experimental Results
The proposed methods were evaluated on synthetic datasets with varying dimensions ($D$) and number of hyperplanes ($K$), as well as real-world deep features from CIFAR-10.
Synthetic Data Performance
HARD-$\ell_1+$ and HARD-Huber+ consistently outperformed state-of-the-art baselines like KH-DPCP. As illustrated in the performance plots, the accuracy gap is particularly pronounced in higher dimensions. For instance, at $D=27$ and $K=3$, HARD improved clustering accuracy by 32.8% over KH-DPCP. Furthermore, the "+" variants demonstrated superior speed due to their SVD-based update rules, running in a fraction of the time of iterative DPCP-based methods.
Robustness and Real-World Application
HARD maintained high precision-recall (AUC-PR $\ge$ 0.97) even when the dataset contained 30% pure outliers, whereas competing methods collapsed. On CIFAR-10 deep features, HARD-Huber+ achieved a median clustering accuracy of 73% (max 81%), significantly surpassing baseline methods.
Discussion and Conclusion
HARD leverages the "power of the product" to handle the union of subspaces without needing explicit cluster assignments, using "soft" weights to navigate the non-convex landscape. The authors provide theoretical guarantees that ground-truth hyperplanes are coordinate-wise minimizers under specific geometric conditions. While HARD shows significant promise, challenges remain in scaling to a large number of hyperplanes ($K > 5$) and sensitivity to initialization. Future work may involve integrating HARD with representation learning to encourage feature maps to naturally align with hyperplane arrangements.
Summary updated