PaperlayerView exact revision on arXiv

Source-linked AI summary

Kernel Methods on Riemannian Manifolds with Gaussian RBF Kernels

Sadeep Jayasumana, Richard Hartley, Mathieu Salzmann, Hongdong Li, Mehrtash Harandi

arXiv:1412.0265v2cs.CV

TL;DR

Manifold-valued data do not fit Euclidean learning methods well, motivating kernels that respect nonlinear geometry. The paper develops conditions for positive definite Gaussian RBF kernels, applies them to SPD and Grassmann manifolds, and uses them to extend standard algorithms.

  • Problem

    Manifold-valued data lack Euclidean structure, limiting the direct use of standard computer vision and machine learning algorithms.

  • Method

    The paper analyzes Gaussian RBF positive definiteness on generic metric spaces and constructs manifold kernels that enable RKHS embeddings and kernel algorithms.

  • Results

    The resulting kernels are identified for SPD and Grassmann manifolds, and experiments across several computer vision tasks outperform corresponding Euclidean and other manifold-specific methods.

  • Takeaways & Limitations

    Positive definite manifold kernels extend algorithms such as SVM, FDA, and PCA to nonlinear manifold-valued data while preserving their favorable properties.

  • Takeaways & Limitations

    For compact manifolds, a positive definite Gaussian based on geodesic distance cannot generally be obtained, so suitable non-geodesic distances may be needed.

Abstract

from arXiv · show

In this paper, we develop an approach to exploiting kernel methods with manifold-valued data. In many computer vision problems, the data can be naturally represented as points on a Riemannian manifold. Due to the non-Euclidean geometry of Riemannian manifolds, usual Euclidean computer vision and machine learning algorithms yield inferior results on such data. In this paper, we define Gaussian radial basis function (RBF)-based positive definite kernels on manifolds that permit us to embed a given manifold with a corresponding metric in a high dimensional reproducing kernel Hilbert space. These kernels make it possible to utilize algorithms developed for linear spaces on nonlinear manifold-valued data. Since the Gaussian RBF defined with any given metric is not always positive definite, we present a unified framework for analyzing the positive definiteness of the Gaussian RBF on a generic metric space. We then use the proposed framework to identify positive definite kernels on two specific manifolds commonly encountered in computer vision: the Riemannian manifold of symmetric positive definite matrices and the Grassmann manifold, i.e., the Riemannian manifold of linear subspaces of a Euclidean space. We show that many popular algorithms designed for Euclidean spaces, such as support vector machines, discriminant analysis and principal component analysis can be generalized to Riemannian manifolds with the help of such positive definite Gaussian kernels.

1 INTRODUCTION

The paper addresses the difficulty of applying Euclidean learning methods to manifold-valued data by developing positive definite Gaussian kernels that preserve manifold geometry. It analyzes when such kernels are valid and applies them to SPD and Grassmann manifolds, where experiments show improved performance over Euclidean and other manifold-specific methods.

  • Manifold-valued data lack Euclidean structures, so directly applying methods such as SVM, PCA, and mean-shift often produces poor accuracy and undesirable effects.
  • Tangent-space approximations can distort data far from the origin, increase computational cost through repeated mappings, and depend heavily on the chosen tangent-space origin.
  • Kernel methods offer an alternative by embedding manifolds in a high-dimensional RKHS, but the required kernel must be positive definite.
  • Replacing Euclidean distance in the Gaussian RBF with a nonlinear manifold distance is attractive, yet the resulting kernel is not positive definite in general.
  • The paper derives necessary and sufficient conditions for Gaussian RBF positive definiteness on generic metric spaces and uses them to construct kernels for SPD and Grassmann manifolds.
  • Experiments across pedestrian detection, segmentation, face recognition, and action recognition show manifold kernels outperform corresponding Euclidean and other state-of-the-art manifold methods.

2 RELATED WORK

Prior manifold methods often rely on tangent spaces, approximations, restricted kernels, or non-positive definite constructions. The paper distinguishes its framework by providing provably positive definite Gaussian kernels and broader kernel-based learning capabilities.

  • SPD and Grassmann manifolds are widely used for descriptors and subspace representations in object, texture, action, face, and activity recognition.
  • Existing Riemannian optimization methods can incur high computational costs from tangent-space mappings and Karcher mean calculations.
  • The proposed positive definite kernels support efficient classification without tangent-space approximations and readily extend kernel-based classifiers to multiclass settings.
  • Earlier manifold dimensionality-reduction methods cluster after mapping to a lower-dimensional space that may not preserve all original information, whereas this work clusters in a higher-dimensional RKHS.
  • Earlier SPD kernels may fail positive definiteness generally or only satisfy it for restricted Gaussian bandwidth values, making unconstrained bandwidth selection desirable.
  • The paper’s Gaussian-like Grassmann kernels differ from projection kernels that are analogous to Euclidean linear kernels.
  • Unlike prior approaches lacking explicit proofs, the paper presents a unified framework and identifies provably positive definite kernels on SPD and Grassmann manifolds.
  • Positive definiteness is required for valid RKHS construction and guarantees convexity in SVM and multiple kernel learning.

3 MANIFOLDS IN COMPUTER VISION

The paper introduces the geometric structures relevant to computer vision, focusing on SPD matrices and Grassmann manifolds as nonlinear spaces with useful application-specific distances.

  • A Riemannian manifold is a differentiable manifold with smoothly varying inner products on tangent spaces, inducing geometric notions and geodesic distance.
  • Geodesic distance is the natural Riemannian dissimilarity, while other nonlinear metrics may also be useful and need not arise from Riemannian metrics.
  • SPD Matrices: An SPD matrix satisfies x^T Sx > 0 for every nonzero x in R^d.
  • SPD Matrices: The space of d × d SPD matrices is not a vector space but forms a convex cone in d^2-dimensional Euclidean space.
  • SPD Matrices: Riemannian geometry gives SPD matrices a more accurate geodesic distance than the ambient Euclidean distance, with affine-invariant and log-Euclidean metrics widely used.
  • Grassmann Manifolds: A point on the Grassmann manifold is an r-dimensional linear subspace of R^n, represented by an n × r orthonormal-basis matrix up to orthogonal change of basis.
  • Grassmann Manifolds: The Grassmann arc length distance equals the l2 norm of the vector of principal angles between two subspaces.

4 HILBERT SPACE EMBEDDING OF MANIFOLDS

The paper embeds manifold points into an RKHS so algorithms requiring inner products can operate on nonlinear data. Positive definiteness is the central condition enabling these embeddings and the resulting learning methods.

  • An RKHS is a Hilbert space of functions whose inner product is represented through a bivariate kernel function.
  • The kernel trick lets algorithms such as SVM, PCA, FDA, and k-means use RKHS inner products without explicitly computing high-dimensional feature vectors.
  • Manifold points can likewise be mapped into a possibly infinite-dimensional Hilbert space, with a kernel defining its inner product.
  • The main technical difficulty is that Mercer’s theorem requires the manifold kernel to be positive definite for a valid RKHS.
  • An RKHS embedding both linearizes manifold geometry for existing algorithms and provides a richer high-dimensional representation that can make classification easier.
  • The paper builds a framework for defining positive definite kernels on manifolds.

5 THEORY OF POSITIVE AND NEGATIVE DEFINITE KERNELS

This section develops criteria for positive and negative definite kernels, emphasizing Schoenberg’s characterization of Gaussian exponential kernels and a practical matrix test for conditional negative definiteness.

  • Definitions: A kernel is positive definite when it is symmetric and satisfies the required nonnegative quadratic-form condition; negative definiteness adds the constraint that coefficients sum to zero.The paper also notes that some authors call negative definite kernels conditionally negative definite.
  • Core theorem: Schoenberg’s theorem states that exp(−γ f(x, y)) is positive definite for every γ > 0 exactly when f is negative definite.This theorem provides the central link between negative definite kernels and Gaussian RBF–like exponential kernels.
  • Core theorem: If exp(−γ f(x, y)) is positive definite for all γ in some interval (0, δ), then it is positive definite for every γ > 0.The proof proceeds by showing that 1 − exp(−γ f(x, y)) is negative definite and taking a pointwise limit.
  • Hilbert-space representation: Negative definite kernels can represent squared Hilbert-space distances, with a nonnegative function h that vanishes when f(x, x) = 0 for every x.The representation uses a mapping ψ from X into a Hilbert space.
  • Matrix test: For a kernel matrix M, conditional negative semidefiniteness is equivalent to negative semidefiniteness of PMP, where P = I_m − (1/m)1_m1_m^T.Checking the eigenvalues of PMP supplies a convenient test for conditional negative definiteness.

6 KERNELS ON MANIFOLDS

The paper develops conditions for Gaussian RBF kernels on metric spaces to be positive definite, then applies them to SPD and Grassmann manifolds.

  • 6 KERNELS ON MANIFOLDS: Positive definite kernels are the key challenge in extending Euclidean kernel methods to nonlinear manifolds.Linear and polynomial kernels depend on Euclidean geometry, while manifold embeddings into RKHSs require positive definite kernels.
  • 6.1 The Gaussian RBF Kernel on Metric Spaces: A Gaussian RBF based on a manifold distance is not necessarily positive definite, including the geodesic distance on the unit sphere.The paper therefore analyzes Gaussian RBF positive definiteness for generic metric spaces.
  • 6.1 The Gaussian RBF Kernel on Metric Spaces: The Gaussian RBF exp(−γd(x,y)^2) is positive definite for every γ > 0 exactly when the distance admits an isometric embedding into an inner product space.The embedding has the form d(x,y) = ∥ψ(x) − ψ(y)∥V.
  • 6.2 Geodesic Distances and the Gaussian RBF: For complete Riemannian manifolds, the geodesic Gaussian is positive definite only when the manifold is isometric to some Euclidean space R^n.Compact manifolds cannot satisfy this condition because they cannot be isometric to noncompact R^n.
  • 6.3–6.4 Kernels on SPD and Grassmann Manifolds: The Log-Euclidean Gaussian on SPD matrices and the Projection Gaussian on Grassmann manifolds are positive definite for all γ > 0.For SPD matrices, Cholesky and power-Euclidean metrics also yield positive definite Gaussian kernels; other Grassmann metrics lack this property.

7 KERNEL-BASED ALGORITHMS ON MANIFOLDS

The paper generalizes Euclidean kernel algorithms to manifold-valued data by mapping points into an RKHS through positive definite manifold kernels. It applies this framework to SVM, MKL, kernel PCA, clustering, and FDA, while preserving manifold geometry.

  • Positive definite manifold kernels enable Euclidean kernel algorithms to operate on nonlinear manifold-valued data through an RKHS embedding.The feature map need not be explicitly computed because algorithms can use the kernel trick.
  • Kernel SVM: Manifold kernel SVM separates mapped feature vectors with maximum margin, and standard SVM software and optimization remain applicable.Positive definiteness guarantees convergence of standard SVM optimization algorithms.
  • Kernel SVM: Manifold kernel SVM is simpler and less computationally demanding than manifold LogitBoost, while experiments report better classification results.LogitBoost repeatedly combines weak learners on tangent spaces and requires expensive weighted-mean gradient descent.
  • Multiple Kernel Learning: Multiple Kernel Learning combines manifold-valued descriptors and can also combine them with Euclidean descriptors using nonnegative kernel weights.An l1 regularizer produces sparse combinations, but convergence requires all component kernels to be positive definite.
  • Dimensionality reduction: Kernel PCA and kernel FDA produce Euclidean representations in RKHS while accounting for manifold geometry and, for FDA, maximizing class separation.Kernel FDA can extract up to l − 1 dimensions for l classes.
  • Clustering: Kernel k-means clusters manifold points in a high-dimensional Hilbert space by minimizing squared distances to cluster centers.The paper contrasts this with a method that clusters after low-dimensional manifold dimensionality reduction.

8 APPLICATIONS AND EXPERIMENTS

The paper evaluates its proposed manifold kernels and kernel algorithms in experiments on the SPD-matrix manifold. These experiments use the positive definite kernels introduced earlier together with the described algorithms.

  • The experiments study SPD-matrix data using the positive definite kernels introduced in Section 6 and the algorithms described in Section 7.
  • The experimental program evaluates manifold kernel methods across the proposed kernel-based algorithms on symmetric positive definite matrices.
  • The experiments connect the theoretical positive-definiteness analysis with applications of the resulting manifold kernels.

8.1 Experiments on Sym+

Experiments on SPD-matrix data use the log-Euclidean Gaussian kernel with kernel methods for detection, categorization, texture recognition, and segmentation. Across these tasks, the manifold-aware methods outperform or improve over Euclidean and other manifold baselines.

  • Pedestrian Detection: The pedestrian-detection pipeline uses covariance descriptors on SPD matrices, selects 100 non-overlapping subwindows, and trains an SVM-MKL classifier.Descriptors are ranked using a manifold variance-like statistic, with kernels defined on the selected subwindows.
  • Pedestrian Detection: The Riemannian-kernel MKL method outperforms both Euclidean-kernel MKL and manifold LogitBoost for pedestrian detection.The comparison is made using DET curves while varying the final MKL decision threshold.
  • Visual Object Categorization: Manifold kernel k-means with the log-Euclidean Gaussian kernel performs significantly better than all other tested methods in every object-categorization test case.The methods are evaluated on ETH-80 using positive-definite Gaussian kernels generated by different metrics.
  • Texture Recognition: Kernel PCA with the proposed log-Euclidean kernel captures texture information more effectively than the usual Euclidean Gaussian kernel.Texture recognition uses k-nearest neighbors in an l-dimensional Euclidean space obtained from kernel PCA.
  • Segmentation: The proposed kernel k-means approach yields cleaner segmentation than the baselines by clustering in a high-dimensional feature space.For DTI segmentation, each pixel is represented by a 3×3 SPD matrix, and the corpus callosum is correctly separated up to some noise.

8.2 Experiments on Gr

Experiments on the Grassmann manifold apply projection Gaussian kernels with kernel FDA, SVM, and k-means to face recognition, action recognition, and pose grouping. The manifold-kernel methods outperform the compared approaches, with manifold kernel SVM best in recognition and MKKM best across clustering scenarios.

  • 8.2 Experiments on Gr: Projection Gaussian kernels are evaluated with kernel FDA, one-vs-all SVM, and clustering methods on Grassmann-manifold representations.Image sets are modeled as linear subspaces obtained from principal components.
  • 8.2 Experiments on Gr: For 2D motion segmentation on Sym+ 3, kernel k-means with the Riemannian kernel produces a much cleaner segmentation than LLE, LE, and HLLE.The baseline results were reproduced from [5].
  • 8.2.1 Video Based Face Recognition: On YouTube Celebrity face recognition, manifold kernel SVM achieves the best accuracy among the compared image-set classification methods.The comparison includes DCC, KAHM, GDA, and GGDA; Gaussian kernels outperform projection kernels for both FDA and SVM.
  • 8.2.2 Action Recognition: On Ballet action recognition, manifold kernel FDA and manifold kernel SVM outperform the state-of-the-art methods, with manifold kernel SVM achieving the highest accuracy.The methods are compared with DCC, KAHM, GDA, GGDA, and Linear SVM.
  • 8.2.3 Pose Categorization: On CMU-PIE pose grouping, manifold kernel k-means yields the best performance in all test cases, with larger gains as the number of clusters increases.The results compare MKKM with k-means using arc-length and projection metrics.

9 CONCLUSION

The paper introduces a unified framework for analyzing Gaussian RBF positive definiteness on manifolds and uses it to derive positive definite kernels for SPD and Grassmann manifolds. These kernels extend Euclidean learning algorithms such as SVM and FDA to manifold-valued data.

  • 9 CONCLUSION: The paper derives provably positive definite Gaussian kernels for the SPD and Grassmann manifolds using a unified framework.The framework analyzes Gaussian RBF kernels on a manifold or more general metric space.
  • 9 CONCLUSION: The resulting kernels extend Euclidean algorithms including SVM and FDA to manifold-valued data.The paper reports experimental evaluation across several computer vision tasks.
Loading 1412.0265v2…