Abstract
Subspace clustering is a fundamental task in high-dimensional data analysis, aiming to group data points based on their underlying low-dimensional subspaces. While traditional methods rely on convex relaxations like the nuclear and $\ell_1$ norms, these approaches often suffer from "overpenalization" bias, where significant signal components are systematically underestimated. This paper introduces two novel non-convex optimization frameworks: GMC-LRSSC, which utilizes the Generalized Minimax-Concave penalty and firm thresholding, and $S_0/\ell_0$-LRSSC, which directly tackles Schatten-0 and $\ell_0$ quasi-norms via a proximal average method. Implemented using the Alternating Direction Method of Multipliers (ADMM), these methods significantly improve clustering accuracy across diverse datasets, including face images, handwritten digits, and speech recognition, while remaining computationally efficient.
Introduction
In many real-world applications, high-dimensional data—such as images, gene expression profiles, or speech signals—actually resides on a union of much simpler, low-dimensional subspaces. Subspace clustering is the process of identifying these subspaces and grouping data points accordingly.
The prevailing methodology for this task is based on the self-expressiveness property, which posits that every data point can be represented as a linear combination of other points within the same subspace ($X = XC$). To obtain a physically meaningful representation matrix $C$, it is desirable for $C$ to be both low-rank (to capture global structure) and sparse (to capture local structure). Historically, the rank function and the $\ell_0$ norm have been the "gold standard" for these constraints. However, because direct optimization of these functions is NP-hard, researchers have long relied on convex relaxation, substituting the nuclear norm for rank and the $\ell_1$ norm for sparsity.
The Overpenalization Bias
A critical drawback of convex relaxations is the "overpenalization" trap. Convex norms like $\ell_1$ apply a uniform penalty to all coefficients. Consequently, to achieve a sparse solution, the most significant signal components are inevitably shrunk, leading to a biased representation. This paper argues that moving beyond convex relaxations to $\ell_0$-motivated non-convex penalties can significantly mitigate this bias.
Proposed Methods
The authors propose two distinct algorithms designed to better approximate the true $\ell_0$ and rank functions:
1. GMC-LRSSC (Generalized Minimax-Concave)
This method employs the GMC penalty, a non-convex regularizer designed to maintain the convexity of individual subproblems. A key feature of GMC-LRSSC is its use of firm thresholding. As illustrated in Figure 1, firm thresholding provides a middle ground between the biased "soft" thresholding of $\ell_1$ and the aggressive "hard" thresholding of $\ell_0$, allowing larger values to pass through with minimal shrinkage.
2. $S_0/\ell_0$-LRSSC
This approach directly addresses the Schatten-0 ($S_0$) quasi-norm for rank and the $\ell_0$ quasi-norm for sparsity. To overcome the inherent difficulty of joint non-convex optimization, the authors utilize a proximal average method. This technique decouples the low-rank and sparsity constraints, solving them separately and then averaging the results to ensure global convergence.
Both algorithms are implemented within the Alternating Direction Method of Multipliers (ADMM) framework, which efficiently splits complex optimization tasks into manageable iterative steps.
Experimental Results
The proposed methods were evaluated against state-of-the-art competitors on several benchmark datasets, including Extended Yale B (faces), MNIST and USPS (digits), and ISOLET1 (speech).
Performance and Robustness
The $\ell_0$-motivated methods demonstrated superior accuracy, particularly as problem complexity increased. For instance, on the Extended Yale B dataset with 30 clusters, GMC-LRSSC and $S_0/\ell_0$-LRSSC achieved clustering errors of 8.65% and 8.35%, respectively, vastly outperforming the 26.73% error rate of standard Sparse Subspace Clustering (SSC).
As shown in Figure 2, the proposed methods maintain lower error rates across various noise levels and sample sizes compared to traditional approaches. Furthermore, the algorithms are highly efficient; GMC-LRSSC often converges in fewer than 15 iterations, making it one of the fastest methods in its class.
Conclusion and Future Work
By utilizing non-convex, $\ell_0$-motivated regularizers, the proposed GMC-LRSSC and $S_0/\ell_0$-LRSSC frameworks effectively eliminate the bias inherent in convex subspace clustering methods. While these methods show remarkable performance, they do introduce additional hyperparameters that require tuning. Future research will focus on automated parameter selection and "p-continuation strategies" to further enhance robustness and avoid local minima.
Summary updated