TL;DR
This paper introduces a novel "Scaled Simplex Representation" (SSR) for subspace clustering, which improves upon existing methods by ensuring physically meaningful, non-negative coefficients and a more flexible affine constraint. The proposed SSRSC algorithm demonstrates superior accuracy and efficiency on various benchmark datasets for tasks like motion segmentation and face clustering.
What Problem Does This Paper Address?
High-dimensional data often exhibits a structure that can be represented as a union of low-dimensional subspaces. Subspace clustering (SC) aims to discover these underlying subspaces and group data points accordingly. Many existing SC methods rely on the "self-expressive property," where a data point can be reconstructed from other data points within the same subspace. However, these methods often struggle with:
- Physically Meaningless Coefficients: Standard methods can produce negative coefficients, which are problematic for reconstruction and can damage inherent data correlations.
- Inflexible Affine Constraints: The common affine constraint (coefficients summing to 1) is not always suitable for real-world scenarios.
- Information Loss in Affinity Matrix Construction: Operations like exponentiation or symmetrization to create an affinity matrix from coefficients can discard valuable information, especially negative correlations.
This paper tackles these limitations by proposing a more robust and flexible representation for subspace clustering.
Methods
The core contribution is the Scaled Simplex Representation (SSR). This representation introduces two key modifications to the self-expressive framework:
- Non-negative Coefficients: By enforcing $c_i \ge 0$, the coefficients become physically meaningful, representing a positive contribution from other data points.
- Scaled Affine Constraint: Instead of requiring coefficients to sum to 1 ($1^T c_i = 1$), SSR requires them to sum to a scalar $s$ ($1^T c_i = s$), where $0 < s < 1$. This allows for more flexible representation and can enhance discriminative properties.
The proposed SSR-based Subspace Clustering (SSRSC) model is formulated as an optimization problem. To solve it efficiently, the authors employ the Alternating Direction Method of Multipliers (ADMM) framework. This involves:
- Introducing an auxiliary variable $Z$ to reformulate the problem into a linear equality-constrained problem.
- Alternating updates for the coefficient matrix $C$ and the auxiliary variable $Z$, along with a Lagrange multiplier.
- The update for $C$ uses a closed-form solution derived from a least squares regression problem.
- The update for $Z$ involves a projection onto a scaled simplex, which is efficiently handled by a projection-based method.
The affinity matrix is then constructed simply as $A = (C + C^T)/2$, leveraging the non-negativity of $C$ to avoid information-damaging operations. Finally, spectral clustering (specifically Normalized Cuts) is applied to the affinity matrix for segmentation.
Datasets
The proposed SSRSC method was evaluated on the following benchmark datasets:
- Hopkins-155: For motion segmentation (155 video sequences).
- Extended Yale B: For human face clustering (images of 38 subjects under varying illumination).
- ORL: For human face clustering (400 images of 40 subjects).
- MNIST: For handwritten digit clustering (60,000 grayscale images of 10 digits).
- EMNIST: For handwritten digit/letter clustering (190,998 images of 26 lowercase letters).
Key Insights and Ideas
- Non-negativity is Crucial for Physical Meaning: Forcing coefficients to be non-negative makes the reconstruction process more intuitive and physically grounded, avoiding "cancellation" of data points.
- Scaled Affine Constraint Offers Flexibility: Allowing the sum of coefficients to be a tunable scalar $s$ (instead of fixed to 1) provides a knob to control the representation's properties, potentially leading to better discriminative power.
- Direct Affinity Construction from Non-negative Coefficients: By ensuring $C \ge 0$, the affinity matrix can be formed directly as $A = (C+C^T)/2$, preserving more information than methods that use exponentiation or symmetrization on potentially negative coefficients.
- ADMM for Efficient Optimization: The use of ADMM allows for efficient, iterative updates of the model's variables, leading to a practical algorithm.
- Removing Diagonal Constraint Improves Robustness: The paper argues that removing the $c_{ii}=0$ constraint (which prevents a point from being represented by itself) makes the model more robust to noise, as seen in ablation studies.
Key Results
- Superior Accuracy: SSRSC consistently outperformed state-of-the-art subspace clustering algorithms across all tested datasets, achieving significantly lower clustering errors. For example, on Hopkins-155, SSRSC achieved an error of 1.04% (with $s=0.9$), compared to 1.75% for NLSR. On MNIST, it achieved 4.53% with 600 images per digit.
- Efficiency: The proposed SSRSC algorithm is efficient, with a complexity of $O(\max(D, \log N)N^2K)$, where $D$ is the data dimension, $N$ is the number of data points, and $K$ is the number of iterations. Its speed is comparable to other efficient methods like SSCOMP.
- Parameter Sensitivity: The performance of SSRSC is influenced by the scalar $s$. The paper shows plots demonstrating how varying $s$ affects clustering error, with optimal values often found between 0.15 and 0.9 depending on the dataset.
- Ablation Studies: Experiments confirmed the effectiveness of both the non-negative constraint and the scaled affine constraint, showing significant performance gains compared to baseline methods that lack one or both.
Limitations and Future Work
- Parameter Tuning: While SSRSC is robust, the parameters $\lambda$ (regularization) and $s$ (scaled affine constraint) still require tuning for optimal performance on different datasets.
- Scalability: While efficient, extending the algorithm for even larger-scale datasets is suggested as a future direction.
- Non-linear Extensions: The authors propose extending the SSRSC model to non-linear versions using kernel approaches.
- Imbalanced Datasets: Adapting the proposed model for imbalanced datasets is also identified as a valuable future research avenue.
Summary updated