Low-Rank Kernel Subspace Clustering

Pan Ji, Ian D. Reid, Ravi Garg, Hongdong Li, Mathieu Salzmann

Abstract

In this paper, we present a kernel subspace clustering method that can handle non-linear models. In contrast to recent kernel subspace clustering methods which use predefined kernels, we propose to learn a low-rank kernel matrix, with which mapped data in feature space are not only low-rank but also self-expressive. In this manner, the low-dimensional subspace structures of the (implicitly) mapped data are retained and manifested in the high-dimensional feature space. We evaluate the proposed method extensively on both motion segmentation and image clustering benchmarks, and obtain superior results, outperforming the kernel subspace clustering method that uses standard kernels and other state-of-the-art linear subspace clustering methods.

Introduction: Beyond Linear Subspaces

Subspace clustering is a fundamental task in computer vision, essential for applications such as segmenting moving objects in video or grouping faces by identity. The traditional assumption is that data points from the same group lie in a linear subspace. However, real-world data often deviates from this ideal due to camera perspective distortions, varying illumination, and complex geometries, which warp these linear structures into curved manifolds.

Conceptual mapping of non-linear manifolds to linear subspaces via learned feature mapping.

While the "kernel trick" has been employed to map data into higher-dimensional spaces where it might become linear, existing methods typically rely on fixed, pre-defined kernels (e.g., RBF or Polynomial). These "off-the-shelf" kernels do not guarantee that the resulting feature space will preserve the low-rank structure necessary for effective clustering. A poorly chosen kernel can obscure the underlying patterns, leading to degraded performance.

Adaptive Low-Rank Kernel Subspace Clustering (LRKSC)

To address these limitations, we propose a joint optimization framework that adaptively learns a kernel matrix. The core idea is to ensure that data in the implicit feature space is both low-rank and self-expressive.

Key Methodological Components

  1. Low-Rank Feature Mapping: We factorize the unknown kernel matrix $K$ into $B^T B$. By minimizing the nuclear norm of $B$, we encourage the data to form neat, linear subspace structures in the feature space.
  2. Self-Expressiveness: We incorporate the self-expression principle, which posits that any data point in a subspace can be represented as a linear combination of other points in the same subspace.
  3. Adaptive Regularization: To avoid trivial solutions, the learned kernel is regularized to remain close to a "guide" kernel ($K_G$), such as a standard polynomial kernel.
  4. Robustness to Noise: The algorithm includes a sparse error term to handle gross corruptions and outliers, ensuring stability in real-world scenarios.

The resulting non-convex optimization problem is solved efficiently using the Alternating Direction Method of Multipliers (ADMM).

Experimental Evaluation

We evaluated LRKSC against state-of-the-art baselines, including Sparse Subspace Clustering (SSC) and Low-Rank Representation (LRR), across four standard benchmarks: Hopkins 155 (motion), Extended Yale B (faces), ORL (faces), and COIL-100 (objects).

Clustering error comparison across EYaleB, ORL, and COIL-100 datasets.

Key Results

  • Motion Segmentation: On the Hopkins 155 dataset, LRKSC achieved a mean error of 1.64%, significantly better than SSC's 2.18%. In cases of heavy perspective distortion, LRKSC maintained 98.04% accuracy, while SSC dropped to 64.38%.
  • Face Clustering: On the Extended Yale B dataset, LRKSC nearly halved the clustering error of SSC as the number of subjects increased. It also showed remarkable robustness on the ORL dataset, where limited samples per subject typically hinder standard kernel methods.
  • Object Recognition: On COIL-100, LRKSC achieved the lowest clustering errors across all test cases, demonstrating its ability to handle the non-linearities introduced by object rotation.

Conclusion and Future Work

LRKSC demonstrates that learning the feature mapping alongside the clustering coefficients is superior to using fixed kernels. By enforcing low-rankness in the feature space, the method effectively uncovers the intrinsic geometry of complex data. Future research will explore integrating Multiple Kernel Learning (MKL) to automatically determine the optimal base "guide" kernel, further reducing the need for manual parameter tuning.

Summary updated

Abstract

In this paper, we present a kernel subspace clustering method that can handle non-linear models. In contrast to recent kernel subspace clustering methods which use predefined kernels, we propose to learn a low-rank kernel matrix, with which mapped data in feature space are not only low-rank but also self-expressive. In this manner, the low-dimensional subspace structures of the (implicitly) mapped data are retained and manifested in the high-dimensional feature space. We evaluate the proposed method extensively on both motion segmentation and image clustering benchmarks, and obtain superior results, outperforming the kernel subspace clustering method that uses standard kernels[Patel 2014] and other state-of-the-art linear subspace clustering methods.
BibTeX
@misc{ji2017low,
  author = {Pan Ji and Ian D. Reid and Ravi Garg and Hongdong Li and Mathieu Salzmann},
  title = {{Low-Rank Kernel Subspace Clustering}},
  year = {2017},
  eprint = {1707.04974},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1707.04974},
}
Figure