Adaptive Low-Rank Kernel Subspace Clustering

Pan Ji, Ian 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

Subspace clustering is a fundamental task in computer vision, aiming to group data points that lie near a union of low-dimensional linear subspaces. Applications range from motion segmentation in video trajectories to face clustering. While linear methods like Sparse Subspace Clustering (SSC) have seen success, real-world data often exhibits non-linear characteristics due to perspective distortion or varying physical conditions.

Existing kernelized approaches attempt to address this by mapping data into a high-dimensional feature space. However, these methods typically rely on fixed, pre-defined kernels (e.g., RBF or Polynomial). Such "black-box" kernels offer no guarantee that the resulting feature space will preserve or enhance the underlying low-rank structure. This paper introduces Adaptive Low-Rank Kernel Subspace Clustering (LRKSC), which learns an optimal feature mapping specifically designed to maintain low-rankness and self-expressiveness.

Methodology

The core innovation of LRKSC is a joint optimization framework that learns the kernel and the clustering structure simultaneously.

Conceptual mapping from non-linear manifolds to linear subspaces via the learned kernel.

Adaptive Kernel Learning

Instead of selecting a static kernel, the method solves for a kernel matrix $K$ decomposed as $K = B^T B$. By minimizing the nuclear norm of $B$, the algorithm explicitly encourages the mapped data in the feature space to be low-rank. This "subspace-aware" mapping ensures that the high-dimensional representation is conducive to clustering.

Self-Expressiveness and Regularization

The framework incorporates the self-expression property—where any point in a subspace is represented as a linear combination of others in the same subspace—directly into the feature space. To prevent trivial solutions (e.g., a zero kernel), the learned kernel is regularized to remain close to a "base" kernel. Additionally, a sparse error term is introduced to handle gross corruptions like specular reflections or tracking outliers. The resulting non-convex problem is solved using the Alternating Direction Method of Multipliers (ADMM).

Experimental Results

The proposed method was evaluated on several standard benchmarks: Hopkins155 (motion), Extended Yale B (faces), ORL (faces), and COIL-100 (objects).

Performance Analysis

LRKSC consistently outperformed state-of-the-art linear and fixed-kernel methods. On the Hopkins155 dataset, it achieved a mean error of 1.64%, compared to 2.18% for SSC. In more challenging scenarios, such as the "two-frame" perspective motion task, LRKSC nearly halved the error rate of linear SSC (3.30% vs 5.20%).

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

As shown in the figure above, LRKSC maintains a significantly lower clustering error as the complexity (number of subjects or objects) increases. Notably, on the ORL dataset—characterized by few samples per subject—LRKSC's adaptive approach captured the underlying subspace structure far more effectively than fixed-kernel competitors.

Conclusion

Adaptive Low-Rank Kernel Subspace Clustering addresses the limitations of fixed-kernel methods by explicitly optimizing for low-rankness in the feature space. By "untangling" non-linear manifolds into linear subspaces, it achieves state-of-the-art performance in motion segmentation and image clustering. Future work may involve integrating Multiple Kernel Learning (MKL) to automate base kernel selection, moving toward a fully autonomous clustering system.

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{ji2017adaptive,
  author = {Pan Ji and Ian Reid and Ravi Garg and Hongdong Li and Mathieu Salzmann},
  title = {{Adaptive Low-Rank Kernel Subspace Clustering}},
  year = {2017},
  eprint = {1707.04974},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1707.04974},
}
Figure