Source-linked AI summary
Kernel Methods on the Riemannian Manifold of Symmetric Positive Definite Matrices
Sadeep Jayasumana, Richard Hartley, Mathieu Salzmann, Hongdong Li, Mehrtash Harandi
TL;DR
Existing methods often approximate the nonlinear SPD manifold locally in tangent spaces, limiting faithful geometric treatment. The paper instead constructs provably positive definite Gaussian-based kernels using manifold metrics, enabling kernel algorithms on SPD data; experiments show these methods outperform Euclidean and tangent-space alternatives across several computer-vision tasks.
Problem
Existing computer-vision algorithms primarily target Euclidean data, while tangent-space approaches only locally approximate SPD-manifold geometry and can be computationally expensive.
Method
The paper maps SPD matrices into a high-dimensional RKHS using a family of provably positive definite Gaussian kernels derived from metrics on the Riemannian manifold.
Results
Manifold kernel methods outperform corresponding Euclidean Gaussian-kernel methods and tangent-space manifold methods across the reported computer-vision experiments.
Takeaways & Limitations
The kernels extend kernel-based algorithms such as SVM and kernel k-means to SPD-manifold data while retaining the manifold geometry.
Takeaways & Limitations
The visual object-categorization experiment assumes the kernel k is known.
Abstract
from arXiv · showhide
Symmetric Positive Definite (SPD) matrices have become popular to encode image information. Accounting for the geometry of the Riemannian manifold of SPD matrices has proven key to the success of many algorithms. However, most existing methods only approximate the true shape of the manifold locally by its tangent plane. In this paper, inspired by kernel methods, we propose to map SPD matrices to a high dimensional Hilbert space where Euclidean geometry applies. To encode the geometry of the manifold in the mapping, we introduce a family of provably positive definite kernels on the Riemannian manifold of SPD matrices. These kernels are derived from the Gaussian ker- nel, but exploit different metrics on the manifold. This lets us extend kernel-based algorithms developed for Euclidean spaces, such as SVM and kernel PCA, to the Riemannian manifold of SPD matrices. We demonstrate the benefits of our approach on the problems of pedestrian detection, ob- ject categorization, texture analysis, 2D motion segmentation and Diffusion Tensor Imaging (DTI) segmentation.
1. Introduction
SPD matrices lie on a nonlinear Riemannian manifold, but standard computer-vision algorithms often use Euclidean or tangent-space approximations. The paper introduces provably positive definite manifold kernels that preserve manifold geometry and improve results over Euclidean and tangent-space methods.
- SPD matrices encode computer-vision information but lie on a nonlinear Riemannian manifold rather than a Euclidean vector space.
- Directly applying Euclidean algorithms can yield poor accuracy and diffusion-tensor swelling, while tangent-space methods are computationally expensive and locally approximate the manifold.
- The paper proposes mapping SPD matrices into a high-dimensional RKHS through kernels that account for manifold geometry.
- A theoretical framework analyzes Gaussian-kernel positive definiteness on nonlinear manifolds and establishes valid kernels for a family of metrics on Sym+^d.
- The log-Euclidean metric is a notable special case because it defines a true geodesic distance on Sym+^d.
- Manifold kernel methods outperform corresponding Euclidean Gaussian-kernel methods and tangent-space manifold methods in the reported experiments.
2. Related Work
Prior work applies manifold optimization, dimensionality reduction, clustering, and kernels to SPD data, but often relies on approximations or kernels lacking universal positive definiteness. This paper introduces positive definite SPD kernels for broader kernel-based use.
- SPD matrices support applications including object detection, texture classification, tracking, action recognition, face recognition, and DTI.
- Earlier manifold algorithms include LogitBoost, Laplacian Eigenmaps, Locally Linear Embedding, Hessian LLE, and clustering after dimensionality reduction.
- Tangent-space approximations can be computationally expensive, fail to scale with training samples, and may not preserve the original data distribution.
- Previously proposed SPD kernels may be non-positive definite, use a non-geodesic distance, or be positive definite only for some Gaussian bandwidth values.
- Positive definiteness is required for valid RKHS construction and supports convergence or convexity guarantees in kernel algorithms such as SVM and MKL.
- The paper introduces provably positive definite kernels on Sym+^d and demonstrates their benefits across kernel algorithms and computer-vision tasks.
3. Background
Riemannian geometry supplies intrinsic distances for nonlinear manifolds, while kernel methods map data into Hilbert spaces where Euclidean algorithms can operate. For SPD matrices, geodesic metrics better reflect manifold structure than Euclidean distance.
- A differentiable manifold is locally similar to Euclidean space but has a globally defined differential structure; each tangent space is a vector space of curve tangent vectors.
- A Riemannian manifold assigns a smoothly varying inner product to each tangent space, defining curve lengths, geodesics, and geodesic distances.
- For SPD matrices, the Riemannian geodesic distance is a more natural dissimilarity measure than Euclidean distance when the appropriate metric is used.
- Not every distance proposed for Sym+^d arises from a smoothly varying tangent-space inner product and therefore defines a true geodesic distance.
- Affine-invariant and log-Euclidean distances are widely used because they are true geodesic distances induced by Riemannian metrics.
- Kernel methods map data into high-dimensional feature spaces, but only positive definite kernels define valid RKHSs under Mercer’s theorem.
- Tangent-space mappings do not globally preserve distances and can poorly represent the original manifold-valued data distribution.
4. Positive Definite Kernels on Manifolds
The paper establishes when Gaussian kernels built from manifold distances are positive definite, then applies this criterion to construct valid kernels on SPD matrices using several metrics.
- Gaussian kernels on metric spaces: The proposed framework analyzes Gaussian kernels generated by distances on non-linear manifolds, including metrics that do not yield positive definite kernels.Thus, replacing Euclidean distance with a geodesic distance is not sufficient by itself.
- Gaussian kernels on metric spaces: Theorem 4.1 states that exp(−d^2(x_i, x_j)/2σ^2) is positive definite for all σ > 0 exactly when d is induced by an inner-product-space embedding.This converts kernel validity into the existence of a distance-preserving map into an inner product space.
- Gaussian kernels on metric spaces: Positive definiteness of the Gaussian kernel is equivalent to negative definiteness of the squared distance function.The paper uses Schoenberg’s theorem to reduce kernel analysis to a property of the squared metric.
- Kernels on Sym+^d: The resulting Gaussian kernel on Sym+^d is provably positive definite for all σ ∈ R.The paper also identifies Cholesky and power-Euclidean metrics as generating positive definite Gaussian kernels for all σ, while some metrics work only for selected σ values.
- Kernels on Sym+^d: The log-Euclidean distance is d_g(X_i, X_j) = ||log(X_i) − log(X_j)||_F and defines a true geodesic distance on Sym+^d.Its construction exploits the Lie-group structure and maps SPD matrices through the matrix logarithm.
5. Kernel-based Algorithms on Sym+
The paper generalizes Euclidean kernel algorithms to SPD manifolds by operating in an RKHS, where classification, feature selection, dimensionality reduction, and clustering can use manifold-aware kernels.
- Overview: Positive definite kernels on Sym+^d let Euclidean algorithms operate on manifold-valued data while accounting for the manifold geometry.The paper presents four kernel-based algorithms using the kernel, RKHS, and implicit feature map.
- Kernel SVM: Kernel SVM separates mapped SPD feature vectors in an RKHS and classifies test points by their position relative to the separating hyperplane.Prediction requires evaluating the kernel only at support vectors.
- Kernel SVM: The proposed SPD classification approach is simpler to implement and less computationally demanding in training and testing than manifold LogitBoost.LogitBoost repeatedly combines weak learners on tangent spaces and uses expensive gradient descent for weighted means.
- Multiple Kernel Learning: Multiple Kernel Learning combines descriptor-specific kernel matrices as K* = Σ_j λ_jK^(j), with nonnegative weights preserving positive definiteness.An L1-regularized min-max procedure can learn a sparse combination, and convergence requires all kernels to be positive definite.
- Kernel PCA: Kernel PCA maps SPD matrices to an RKHS, computes the kernel matrix, and uses its eigenvectors to obtain a Euclidean representation that accounts for Sym+^d geometry.Because the computation occurs in feature space, the representation may have more dimensions than the input space.
- Kernel k-means: Kernel k-means clusters SPD matrices in a high-dimensional RKHS by minimizing squared distances to cluster centers, rather than clustering after low-dimensional manifold reduction.The paper argues this high-dimensional representation better captures the data distribution.
6. Applications and Experiments
The paper evaluates Riemannian kernel methods across detection, categorization, texture recognition, and image segmentation tasks using SPD descriptors. Across these applications, the methods generally outperform Euclidean-kernel or tangent-space-based alternatives.
- Experimental scope: The evaluation applies Riemannian kernels to pedestrian detection, object categorization, texture recognition, DTI segmentation, and 2D motion segmentation.The experiments use kernel SVM/MKL, kernel k-means, and kernel PCA on SPD-valued descriptors.
- Pedestrian Detection: Pedestrian detection with Riemannian-kernel MKL outperforms Euclidean-kernel MKL and manifold LogitBoost on the INRIA dataset.The comparison uses detection-error tradeoff curves and indicates that accounting for manifold geometry matters.
- Visual Object Categorization: Manifold kernel k-means with the log-Euclidean metric performs significantly better than all other tested methods in every ETH-80 clustering case.The comparison includes k-means and kernel k-means with metrics generating positive definite Gaussian kernels.
- Texture Recognition: Kernel PCA with the Riemannian kernel achieves better texture recognition accuracy than the Euclidean-kernel comparison on Brodatz.Recognition uses k-nearest neighbors after projection into an l-dimensional Euclidean space obtained through kernel PCA.
- Segmentation: For DTI segmentation, Riemannian kernel k-means correctly segments the corpus callosum from the rest of a human-brain image, aside from some noise.Each pixel is represented directly as a 3 × 3 SPD matrix, and the passage attributes residual noise to the lack of spatial smoothing.
- Segmentation: In 2D motion segmentation, the proposed approach produces much cleaner segmentations than LLE, LE, and HLLE baselines.The method clusters in a high-dimensional feature space, whereas the baselines cluster after dimensionality reduction.
7. Conclusion
The paper introduces provably positive definite kernels for the SPD-matrix Riemannian manifold and uses them to extend kernel algorithms. Experiments show benefits over Euclidean Gaussian kernels and other manifold-based methods across several tasks.
- Conclusion: The paper introduces a family of provably positive definite kernels on the Riemannian manifold of SPD matrices.These kernels support Riemannian extensions of existing kernel-based algorithms such as SVM and kernel k-means.
- Conclusion: Experiments demonstrate benefits over the Euclidean Gaussian kernel and other manifold-based algorithms on several tasks.The conclusion summarizes the empirical advantage across the paper’s evaluated applications.