Geodesic Exponential Kernels: When Curvature and Linearity Conflict
Aasa Feragen1 , François Lauze1 , Søren Hauberg2
1 DIKU, University of Copenhagen. 2 Cognitive Systems, DTU Compute.

Enforcing known constraints in data models often provides more faithfuldata representations and stronger results than simple Euclidean approaches.
Constraints lead to nonlinear data spaces such as Riemannian manifolds ormore general metric spaces. Data types typically modeled this way include
shapes, DTI tensors, symmetric positive definite matrices, human poses,
probability distributions and graphs. However, data analysis methods innonlinear spaces often suffer from lack of computational efficiency, accuracy or both. Motivated by this, a recent trend in computer vision has been
to define kernel methods in nonlinear data spaces. A popular way to generate kernels on nonlinear data spaces is through exponential kernels k(x, y)
which only rely on geodesic distances d(x, y) between observations:k(x, y) = exp (−λ (d(x, y))q ) ,λ , q > 0.

(1)

For q = 2 this gives a geodesic generalization of the Gaussian kernel, andq = 1 gives the geodesic Laplacian kernel. While this idea has an appealing
similarity to familiar Euclidean kernel methods, we show that it is highly
limited if the metric space is curved. In Theorem 1 of this paper we provethat geodesic Gaussian kernels on metric spaces are positive definite(PD) for all λ > 0 only if the metric space is flat.

Geodesic
metric metric
Geodesic
Chordal metric

Chordal metricFigure 1: The sphere Sd ⊂ Rd+1 is an example of a popular manifold data spaceparametrizing e.g. SIFT features or probability distributions. The Euclidean chordal
metric on Sd ⊂ Rd+1 is measured directlyin Rd+1 and therefore relies on the embedding, while the geodesic metric is measured
along Sd .

The existence of a λ > 0 such that the kernel is not PD may seem innocent, but this means that the kernel bandwidth parameter cannot be learned.
In contrast, the choice q = 1 in Equation (1), giving a geodesic Laplacian kernel, leads to a more positive result: The geodesic Laplacian kernel
will be positive definite if and only if the distance d is conditionally negative definite (CND). This provides a PD kernel framework which, for several popular Riemannian data manifolds, takes advantage of the geodesic
distance.

i) The geodesic distance d in a geodesic metric space (X, d)Theorem 1 Let (X, d) be a geodesic metric space, and assume that k(x, y) = Theorem 4
is CND if and only if the corresponding geodesic Laplacian kernel isexp(−λ d 2 (x, y)) is a PD geodesic Gaussian kernel on X for all λ > 0. Then
PD for all λ > 0.
(X, d) is flat in the sense of Alexandrov.
pii) In this case, the square root metric d√ (x, y) = d(x, y) is also aThis is a negative result, in the sense that most metric spaces of interest
distance metric, and (X, d√ ) can be isometrically embedded as aare not flat. As a straightforward consequence of Theorem 1, we show thatmetric space into a Hilbert space H.
geodesic Gaussian kernels on Riemannian manifolds are PD for all λ >iii) The square root metric d√ is not a geodesic metric, and d√ cor0 only if the Riemannian manifold is a Euclidean space:responds to the chordal metric in H, not the intrinsic metric on theimage of X in H.
Theorem 2 Let M be a complete, smooth Riemannian manifold with its
associated geodesic distance metric d. Assume, moreover, that k(x, y) =In Theorem 4, for φ : X → H, the chordal metric kφ (x) − φ (y)kH meaexp(−λ d 2 (x, y)) is a PD geodesic Gaussian kernel for all λ > 0. Then thesures distances directly in H rather than intrinsically in the image φ (X) ⊂ H,Riemannian manifold M is isometric to a Euclidean space.
see also Fig. 1.
We study PD’ness of Laplacian kernels in several popular data spaces;
These two theorems raise several points. The first and main point isthat defining geodesic Gaussian kernels on Riemannian manifolds or other see Table 2. Part ii) of Theorem 4 illustrates that any geodesic metric space
geodesic metric spaces has limited applicability as most relevant spaces are whose geodesic Laplacian kernel is always PD must necessarily have strong
curved. In particular, on Riemannian manifolds the kernels will generally linear properties: Its square root metric is isometrically embeddable in a
only be PD if the original data space is Euclidean, in which case the geodesic Hilbert space. This illustrates an intuitively simple point: A PD kernel has
no choice but to linearize the data space through the reproducing kernel
Gaussian kernel is just the standard Gaussian kernel.
Second, this result is not surprising: Curvature cannot be captured by Hilbert space. Therefore, its ability to capture the original data space geoma flat space, and the classical Schönberg theorem indicates a strong connec- etry is deeply connected to the linear properties of the original metric.
tion between PD Gaussian kernels and linearity of the employed distancemeasure. This is made explicit by Theorems 1 and 2.
Third, do these results depend on the choice q = 2 in Equation (1)? For
Riemannian manifolds, a higher power q > 2 never leads to a PD kernel forSpace
Distance metric
PD Gaussian PD Laplacian
all λ > 0:
Theorem 3 Let M be a Riemannian manifold with its associated geodesic
distance metric d, and let q > 2. Then there is some λ > 0 so that the kernel
in Equation (1) is not PD.
This is an extended abstract. The full paper is available at the Computer Vision Foundationwebpage.

RnRn , n > 2

Sphere Sn
Real projective space Pn (R)Grassmannian
Sym+dSym+dSym+dSym+dHyperbolic space Hn
1-dimensional normal distributions
Metric trees
Geometric graphs (e.g. kNN)
Strings
Trees, graphs

Euclidean metriclq -norm k · kq , q > 2
classical intrinsic
classical intrinsic
classical intrinsic
Frobenius
Log-Euclidean
Affine invariant
Fisher information metricclassical intrinsic
Fisher information metrictree metricshortest path distancestring edit distancetree/graph edit distancekernel?
X÷
÷
÷
÷
XX
÷
÷÷÷÷÷÷
÷

kernel?
X
÷
X
÷
÷
XX
÷
÷
X
XX
÷
÷
÷

Extends to general
Metric spaces
Riemannian manifolds
Gaussian (q = 2)
No (only if flat)
No (only if Euclidean)
Laplacian (q = 1)
Yes, iff metric is CND
Yes, iff metric is CND
Table 2: For a set of popular metric and manifold data spaces and metrics,
Geodesic exp. (q > 2)
Not knownNoTable 1: Overview of results: For a geodesic metric, when is the geodesic we record whether the metric is a geodesic metric, and whether its correexponential kernel in Equation (1) positive definite for all λ > 0?
sponding Gaussian and Laplacian kernels are PD.
Kernel