Kernelized Low Rank Representation on Grassmann Manifolds

Boyue Wang, Yongli Hu, Junbin Gao, Yanfeng Sun, Baocai YinarXiv 2015 · OpenReview

Abstract

Low rank representation (LRR) has recently attracted great interest due to its pleasing efficacy in exploring low-dimensional subspace structures embedded in data. One of its successful applications is subspace clustering which means data are clustered according to the subspaces they belong to. In this paper, at a higher level, we intend to cluster subspaces into classes of subspaces. This is naturally described as a clustering problem on Grassmann manifold. The novelty of this paper is to generalize LRR on Euclidean space onto an LRR model on Grassmann manifold in a uniform kernelized framework. The new methods have many applications in computer vision tasks. Several clustering experiments are conducted on handwritten digit images, dynamic textures, human face clips and traffic scene sequences. The experimental results show that the proposed methods outperform a number of state-of-the-art subspace clustering methods.

Introduction

Subspace clustering is a fundamental task in computer vision, aimed at grouping data points that reside in the same low-dimensional subspace. Traditional approaches, such as Sparse Subspace Clustering (SSC) and Low Rank Representation (LRR), typically assume that data lies in a flat Euclidean space. However, many real-world datasets—particularly those involving video sequences or image sets—exhibit intrinsic non-linear geometric structures. Treating such data as points in a standard Euclidean space ignores these properties, often leading to suboptimal clustering performance.

To address this, we propose a generalization of the LRR model to the Grassmann manifold. On this manifold, each "point" represents a subspace itself, allowing the algorithm to cluster subspaces into distinct classes rather than raw data points.

Methodology: Grassmann Low Rank Representation (GLRR)

Directly applying linear operations like $Y = YZ + E$ is not feasible on curved manifolds. Our approach, Grassmann LRR (GLRR), overcomes this by mapping points on the Grassmann manifold to a space of symmetric matrices via a projection embedding. This transformation enables the use of standard linear algebra and Euclidean metrics (like the Frobenius norm) within the embedded space.

Conceptual framework of Kernelized Low Rank Representation on Grassmann manifolds.

We introduce two specific models to handle different types of noise:

  1. GLRR-F: Optimized for Gaussian noise using the Frobenius norm, featuring an efficient closed-form solution via Singular Value Decomposition (SVD).
  2. GLRR-21: Designed for robustness against gross corruptions and outliers using the $\ell_{2,1}$ norm, solved through the Alternating Direction Method (ADM).

Furthermore, we extend this into a Kernelized GLRR (KGLRR) framework. By utilizing kernels such as the Projection Kernel and the Canonical Correlation Kernel, we can capture complex similarities between subspaces. Our findings indicate that a weighted combination of these kernels (KGLRR-cc+proj) provides the most stable and accurate results across diverse datasets.

Experimental Evaluation

The proposed methods were evaluated across four distinct datasets representing various computer vision challenges:

  • MNIST Handwritten Digits: A baseline for testing robustness against synthetic Gaussian noise.
  • DynTex++: A large-scale dataset of dynamic textures (e.g., flowing water, swaying grass).
  • YouTube Celebrity (YTC): Real-world face video clips characterized by significant variations in pose, lighting, and expression.
  • Highway Traffic: Video sequences of traffic flow under varying weather and density conditions.
Sample face video clips from the YouTube Celebrity dataset.

Key Results

The experimental results demonstrate a significant performance leap over traditional methods:

  • MNIST: GLRR and KGLRR achieved a perfect 100% accuracy, maintaining this performance even under heavy noise ($\sigma=0.3$), whereas standard LRR dropped significantly.
  • YouTube Celebrity: On a 4-subject subset, KGLRR-cc+proj reached 90.8% accuracy, nearly doubling the performance of the SCGSM baseline (52.8%).
  • Highway Traffic: The proposed method achieved 89.7% accuracy, outperforming standard SSC (65.2%) and LRR (68.3%) by a wide margin.

Conclusion

By respecting the non-linear geometry of data through Grassmann manifolds, the proposed GLRR and KGLRR models offer a powerful framework for subspace clustering. While the $\ell_{2,1}$ norm model presents some computational challenges for very large datasets, the overall accuracy gains in complex vision tasks are substantial. Future research will focus on developing LRR models that operate directly on the manifold's intrinsic geometry without relying on external embeddings.

Summary updated

Abstract

Low rank representation (LRR) has recently attracted great interest due to its pleasing efficacy in exploring low-dimensional subspace structures embedded in data. One of its successful applications is subspace clustering which means data are clustered according to the subspaces they belong to. In this paper, at a higher level, we intend to cluster subspaces into classes of subspaces. This is naturally described as a clustering problem on Grassmann manifold. The novelty of this paper is to generalize LRR on Euclidean space onto an LRR model on Grassmann manifold in a uniform kernelized framework. The new methods have many applications in computer vision tasks. Several clustering experiments are conducted on handwritten digit images, dynamic textures, human face clips and traffic scene sequences. The experimental results show that the proposed methods outperform a number of state-of-the-art subspace clustering methods.
BibTeX
@misc{wang2015kernelized,
  author = {Boyue Wang and Yongli Hu and Junbin Gao and Yanfeng Sun and Baocai Yin},
  title = {{Kernelized Low Rank Representation on Grassmann Manifolds}},
  year = {2015},
  eprint = {1504.01806},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1504.01806},
}
Figure