Source-linked AI summary
Geodesic Exponential Kernels: When Curvature and Linearity Conflict
Aasa Feragen, Francois Lauze, Søren Hauberg
TL;DR
The paper asks when geodesic exponential kernels remain positive definite on general geodesic metric spaces. It proves that Gaussian kernels require flatness, while Laplacian kernels work when distances are conditionally negative definite, including on some curved spaces, and discusses the resulting scope limits.
Problem
The paper addresses the limited availability of machine-learning tools for data in nonlinear metric spaces and the need to determine when geodesic kernel generalizations remain positive definite.
Method
The paper analyzes positive definiteness of geodesic exponential kernels and relates the Laplacian case to conditional negative definiteness and Hilbert-space embeddings.
Results
Gaussian kernels are positive definite for all λ > 0 only on flat or Euclidean spaces, whereas Laplacian kernels are positive definite on spaces such as spheres and hyperbolic spaces.
Takeaways & Limitations
Geodesic exponential kernels have limited applicability on curved spaces, with Laplacian kernels providing a supported exception for selected metric spaces.
Takeaways & Limitations
The results show that geodesic exponential kernels are not well-suited for curved spaces except for select metric spaces.
Abstract
from arXiv · showhide
We consider kernel methods on general geodesic metric spaces and provide both negative and positive results. First we show that the common Gaussian kernel can only be generalized to a positive definite kernel on a geodesic metric space if the space is flat. As a result, for data on a Riemannian manifold, the geodesic Gaussian kernel is only positive definite if the Riemannian manifold is Euclidean. This implies that any attempt to design geodesic Gaussian kernels on curved Riemannian manifolds is futile. However, we show that for spaces with conditionally negative definite distances the geodesic Laplacian kernel can be generalized while retaining positive definiteness. This implies that geodesic Laplacian kernels can be generalized to some curved spaces, including spheres and hyperbolic spaces. Our theoretical results are verified empirically.
1 Introduction
The paper examines geodesic exponential kernels for nonlinear metric-space data, finding that positive definiteness sharply restricts Gaussian generalizations but permits Laplacian kernels under specific geometric conditions.
- Motivation: Many data types are better represented in nonlinear metric spaces, whose geodesic metrics encode domain-specific constraints.Examples include shapes, diffusion tensor images, motion models, poses, trees, and probability distributions.
- Kernel construction: Geodesic exponential kernels use only distances, with q = 2 yielding a Gaussian kernel and q = 1 yielding a Laplacian kernel.Their general form is k(x, y) = exp(−λ(d(x, y))^q), with λ, q > 0.
- Kernel construction: Positive definiteness is essential for kernel methods including support vector machines and kernel PCA.The paper therefore analyzes when geodesic exponential kernels remain positive definite for all λ > 0.
- Main results: The geodesic Gaussian kernel is positive definite for all λ > 0 only when the underlying metric space is flat, while the Laplacian kernel remains positive definite under conditional negative definiteness.The paper also reports that q > 2 cannot yield positive definiteness for all λ > 0 on any Riemannian manifold.
- Implications: These results combine negative and positive conclusions: Gaussian generalization is highly limited on curved spaces, whereas Laplacian kernels apply to some such spaces.The paper postpones proofs to later sections and reports empirical experiments confirming and extending the theoretical results.
2 Main results and their consequences
The paper establishes that geodesic Gaussian kernels retain positive definiteness across all bandwidths only in flat spaces, whereas geodesic Laplacian kernels remain positive definite under conditional negative definiteness, including some curved spaces.
- Gaussian kernels: Positive definiteness of a geodesic Gaussian kernel for every λ > 0 forces a geodesic metric space to be flat in the sense of Alexandrov.Flatness means every geodesic triangle can be isometrically embedded into a Euclidean space.
- Gaussian kernels: On complete smooth Riemannian manifolds, the geodesic Gaussian kernel is positive definite for every λ > 0 only when the manifold is isometric to Euclidean space.Thus, applying this kernel to most non-flat manifolds has limited applicability.
- Gaussian kernels: For q > 2, every Riemannian manifold has some λ > 0 for which the corresponding exponential kernel is not positive definite.Consequently, the bandwidth parameter cannot generally be learned across all λ.
- Laplacian kernels: The geodesic Laplacian kernel is positive definite for every λ > 0 exactly when the geodesic distance is conditionally negative definite.This condition implies that the square-root metric is isometrically embeddable in a Hilbert space.
- Laplacian kernels: Geodesic Laplacian kernels therefore apply to some curved spaces, including spheres and hyperbolic spaces, while their Hilbert-space embedding uses the chordal rather than intrinsic metric.The chordal metric measures distances directly in the embedding space, unlike the geodesic metric measured along the original space.
- Interpretation: The results reflect a broader constraint: positive-definite kernels linearize the data space, linking kernel validity to the metric's linear properties.This explains why curvature conflicts with the Gaussian construction but does not rule out Laplacian kernels under conditional negative definiteness.
3 Proofs of main results
The proofs connect positive definiteness of geodesic exponential kernels to Hilbert-space embeddings and metric curvature. They show that geodesic Gaussian kernels force flatness, whereas geodesic Laplacian kernels are characterized by conditional negative definiteness.
- 3.1 Kernels: Positive definiteness of e^(−λψ) for all λ ≥ 0 is equivalent to ψ being conditionally negative definite.This is the kernel-distance equivalence used throughout the proofs.
- 3.3 Geodesic Gaussian kernels on metric spaces: If the geodesic Gaussian kernel is positive definite for all λ > 0, the distance embeds isometrically into a Hilbert space after taking its square root.The resulting map need not be the kernel's feature map.
- 3.3 Geodesic Gaussian kernels on metric spaces: Hilbert-space images of geodesics are straight segments, so every geodesic triangle is isometrically embedded into a Euclidean comparison triangle.This establishes flatness in the sense of Alexandrov.
- 3.3 Geodesic Gaussian kernels on metric spaces: Therefore, a geodesic metric space with a geodesic Gaussian kernel positive definite for all λ > 0 is flat and contractible.The contractibility conclusion follows from the CAT(0) property.
- 3.4 Geodesic Gaussian kernels on Riemannian manifolds: For complete smooth Riemannian manifolds, universal positive definiteness of the geodesic Gaussian kernel implies zero sectional curvature and a Euclidean manifold.The proof obtains Alexandrov curvature ≤ 0 and transfers it to sectional curvature.
- 3.6 Geodesic Laplacian kernels: The geodesic Laplacian kernel is positive definite for all λ > 0 exactly when the geodesic distance is conditionally negative definite.This condition holds for several popular Riemannian data manifolds.
4 Implications for popular manifolds and related work
The implications depend on whether a manifold's intrinsic geodesic distance is conditionally negative definite. Spheres and hyperbolic spaces support geodesic Laplacian kernels, while several non-Euclidean metrics do not support either exponential-kernel family universally.
- Popular manifolds: The intrinsic metrics on R^n, H^n, and S^n are conditionally negative definite, so their geodesic Laplacian kernels are positive definite.The Fisher information metric on one-dimensional normal distributions induces hyperbolic geometry H^2 and likewise has a CND geodesic metric.
- Popular manifolds: Affine-invariant and Fisher information metrics on symmetric positive definite matrices empirically do not induce conditionally negative definite geodesic metrics.The affine-invariant and Log-Euclidean metrics therefore differ in whether their exponential kernels are positive definite.
- Non-manifold spaces: String, tree, and graph edit distances generally fail conditional negative definiteness, whereas metric-tree distances are conditionally negative definite.The paper also reports that shortest-path metrics on geometric neighborhood graphs do not generalize this favorable case.
- Related work: Many published Gaussian kernels on curved manifolds use chordal, projection, or Procrustes distances rather than intrinsic geodesic distances.Their positive definiteness therefore does not contradict the geodesic Gaussian result.
- Related work: The log-Euclidean metric makes the SPD manifold Euclidean through the matrix logarithm, so its geodesic Gaussian kernel is positive definite.In this setting, the Riemannian formulation adds complexity without changing the underlying Euclidean structure.
- Related work: Tangent-space or ambient-space linearizations can produce positive definite kernels but discard distances or constraints encoded by the original Riemannian structure.Chordal kernels similarly disregard constraints represented by geodesic distance.
5 Experiments
Experiments evaluate Gram-matrix eigenspectra for geodesic Gaussian and Laplacian kernels across SPD matrices, spheres, Grassmannians, and neighborhood graphs. The observed negative eigenvalues largely match the theoretical positive-definiteness predictions, with an explicit caveat for Grassmannian Laplacian kernels.
- SPD matrices: All four kernels on 3 × 3 SPD matrices under affine-invariant and Fisher information metrics have negative Gram-matrix eigenvalues.The experiment therefore finds neither metric's Gaussian nor Laplacian kernel positive definite.
- Sphere: On the unit sphere, the geodesic Gaussian Gram matrix has negative eigenvalues, whereas the geodesic Laplacian Gram matrix does not.This agrees with the theoretical classification for these kernels.
- Grassmannian: For one-dimensional Grassmannian subspaces, only the Gaussian kernel under the intrinsic metric appears to have negative eigenvalues.The other tested intrinsic and extrinsic configurations have strictly positive eigenspectra.
- Grassmannian: For 15-dimensional Grassmannian subspaces under the intrinsic metric, the Gaussian kernel has negative eigenvalues but the Laplacian kernel does not.The absence of negative eigenvalues does not prove positive definiteness, since theory shows the Grassmannian Laplacian kernel is generally not PD.
- Geometric graphs: Both Gaussian and Laplacian kernels on shortest-path distances from a neighborhood graph have negative eigenvalues.The data consist of 124 MNIST one-digits projected into two principal components before graph construction.
6 Discussion and outlook
Geodesic exponential kernels require strong linearization properties: Gaussian kernels require flat or Euclidean spaces, while Laplacian kernels require conditionally negative definite metrics. These limits leave geodesic exponential kernels poorly suited to most curved spaces, motivating alternatives that either use different kernels or avoid linearization.
- Kernel-specific conditions: Gaussian geodesic kernels are positive definite only when the metric space is flat or Euclidean.For Riemannian manifolds, positive definiteness for all λ > 0 holds if and only if the manifold is Euclidean.
- Kernel-specific conditions: Laplacian geodesic kernels require conditionally negative definite metrics, which imply that the square root metric embeds in a Hilbert space.
- Scope and limitations: Except for select metric spaces, geodesic exponential kernels are not well-suited to data analysis in curved spaces.
- Alternatives: Kernel methods can still extend to metric spaces through geometry-based kernels or diffusion kernels, although diffusion kernels generally lack closed-form expressions.A Grassmann-manifold kernel incorporates geodesic structure without being a geodesic exponential kernel.
- Outlook: The results indicate that learning tools operating directly in nonlinear data spaces may be preferable to methods that linearize the data.