Positive Definite Kernels on Curved Manifolds

52 concepts22 papers1 proposal

The "kernel trick" is a cornerstone of modern machine learning, allowing algorithms like Support Vector Machines (SVMs) and Gaussian Processes (GPs) to operate in high-dimensional feature spaces by computing simple similarity scores. Traditionally, these kernels rely on Euclidean distances. However, much of the world’s data—from the rotations of a robot arm to the hierarchical structure of a phylogenetic tree—lives on curved surfaces known as Riemannian manifolds.

A natural intuition is to simply replace the Euclidean distance in a standard kernel, such as the Gaussian Radial Basis Function (RBF), with the geodesic distance (the shortest path along the manifold). Unfortunately, as Feragen et al. demonstrate, this simple substitution is mathematically invalid on almost all curved spaces.

The Requirement of Positive Definiteness

For a kernel function $k(x, y)$ to be valid, it must be positive definite (pd). This property ensures that for any set of data points, the resulting Gram matrix is positive semi-definite. As Bernhard Schölkopf explains in The Kernel Trick for Distances, a valid kernel corresponds to a dot product in some Reproducing Kernel Hilbert Space (RKHS).

If a kernel fails to be positive definite, the mathematical foundation of the model collapses. In SVMs, the optimization problem may no longer be convex, leading to non-unique or unstable solutions. In Gaussian Processes, an invalid kernel can result in impossible predictions, such as negative variances, as noted by Borovitskiy et al..

The Schoenberg Constraint

The bridge between distances and kernels is defined by Schoenberg’s theorem. It states that a Gaussian-style kernel $k(x, y) = \exp(-\gamma d(x, y)^2)$ is positive definite for all $\gamma > 0$ if and only if the squared distance $d(x, y)^2$ is conditionally negative definite (cnd).

In Euclidean space, the standard distance satisfies this naturally. But on curved manifolds, the geometry often prevents the geodesic distance from being cnd. Jayasumana et al. point out that natural geodesic distances on most curved manifolds are mathematically incompatible with Gaussian kernels because they fail this requirement. For example, the Affine-Invariant metric, widely used for Symmetric Positive Definite (SPD) matrices, does not yield a valid Gaussian kernel (Jayasumana et al.).

The Conflict Between Curvature and Linearity

The core issue is that curvature introduces global topological constraints that "flat" kernels cannot accommodate. Feragen et al. proved a "no-go" theorem: a geodesic Gaussian kernel is mathematically invalid on any Riemannian manifold that is not flat.

This failure is particularly acute in spaces with specific topologies. Da Costa et al. showed that the Gaussian kernel is never positive definite on a circle, or any space containing a circle (like spheres or Grassmannians), regardless of the chosen scale parameter. As the density of data points increases, the Gram matrix will inevitably develop negative eigenvalues.

Similarly, in hyperbolic spaces—often used to represent hierarchies—Fang et al. and Fan et al. note that directly substituting hyperbolic geodesic distances into standard RBFs fails to maintain positive definiteness, necessitating specialized mapping strategies.

Practical Implications and Workarounds

Despite these theoretical warnings, practitioners often find that geodesic kernels "work" for specific finite datasets. Feragen et al. suggest that while these kernels fail in the limit of infinite data, they may remain numerically stable for small, sparse samples. However, this offers no guarantees as models scale.

To achieve rigorous mathematical validity, researchers have developed several alternatives:

  1. Alternative Metrics: Instead of the shortest-path geodesic, one can use metrics that are provably cnd. For SPD matrices, the Log-Euclidean distance is a popular choice because it transforms the manifold into a flat space where the Gaussian kernel becomes valid (Jayasumana et al.).
  2. Spectral Kernels: Rather than relying on distances, one can define kernels using the spectral properties of the manifold. Borovitskiy et al. introduced Matérn kernels on Riemannian manifolds by leveraging the Laplace–Beltrami operator, providing a constructive way to build valid kernels that respect the manifold's global topology.
  3. Geometry-Aware Optimization: In robotics, Jaquier et al. have successfully applied these valid Riemannian Matérn kernels to Bayesian Optimization, allowing robots to learn efficiently on spheres and tori without risking the mathematical failures of naive geodesic kernels.

By moving beyond simple distance substitution and respecting the underlying constraints of positive definiteness, these methods bridge the gap between geometric intuition and statistical rigor.

Key Foundational Work

Context-dependent kernel design for object matching and recognition (2008) — contributed 1 concept elements to this direction.
The Kernel Trick for Distances (2000) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_geodesic_kernel_invalidity_b5c106d2,
  title = {geodesic kernel invalidity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/geodesic-kernel-invalidity/rdr_b5c106d210664852ad13eec93afea4a1},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_geodesic_kernel_invalidity_b5c106d2_v1,
  title = {geodesic kernel invalidity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/geodesic-kernel-invalidity/rdr_b5c106d210664852ad13eec93afea4a1/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake