ℓ0-Motivated Low-Rank Sparse Subspace Clustering

Maria Brbic, Ivica Kopriva

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.

Comparison of soft, firm, and hard thresholding functions.

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).

Clustering error rates across varying noise levels and sample sizes for different methods.

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

Abstract

In many applications, high-dimensional data points can be well represented by low-dimensional subspaces. To identify the subspaces, it is important to capture a global and local structure of the data which is achieved by imposing low-rank and sparseness constraints on the data representation matrix. In low-rank sparse subspace clustering (LRSSC), nuclear and $\ell_1$ norms are used to measure rank and sparsity. However, the use of nuclear and $\ell_1$ norms leads to an overpenalized problem and only approximates the original problem. In this paper, we propose two $\ell_0$ quasi-norm based regularizations. First, the paper presents regularization based on multivariate generalization of minimax-concave penalty (GMC-LRSSC), which contains the global minimizers of $\ell_0$ quasi-norm regularized objective. Afterward, we introduce the Schatten-0 ($S_0$) and $\ell_0$ regularized objective and approximate the proximal map of the joint solution using a proximal average method ($S_0/\ell_0$-LRSSC). The resulting nonconvex optimization problems are solved using alternating direction method of multipliers with established convergence conditions of both algorithms. Results obtained on synthetic and four real-world datasets show the effectiveness of GMC-LRSSC and $S_0/\ell_0$-LRSSC when compared to state-of-the-art methods.
BibTeX
@article{brbic2018l,
  author = {Maria Brbic and Ivica Kopriva},
  title = {{ℓ0-Motivated Low-Rank Sparse Subspace Clustering}},
  journal = {IEEE Trans. Cybernetics},
  year = {2018},
  doi = {10.1109/tcyb.2018.2883566},
}
Figure