# A General Kernel Framework for Non-CND Distance Measures Using |D|-Dimensional Sparse Landmark Embeddings

arXiv: https://arxiv.org/abs/2609.19083 · HTML: https://mlsanity.com/paper/2609.19083/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 32 references that are in the map.
- First posted on arXiv 16 Sep 2026.

## Builds on (most cited first, 11 of 11)

- [Gaussian Processes for Big Data](https://mlsanity.com/paper/1309.6835/) (2013)
- [Mat'ern Gaussian processes on Riemannian manifolds](https://mlsanity.com/paper/2006.10160/) (2020)
- [Mat'ern Gaussian Processes on Graphs](https://mlsanity.com/paper/2010.15538/) (2020)
- [Geodesic Exponential Kernels: When Curvature and Linearity Conflict](https://mlsanity.com/paper/1411.0296/) (2014)
- [Graph Kernels: A Survey](https://mlsanity.com/paper/1904.12218/) (2019)
- [Asymptotic Guarantees for Learning Generative Models with the Sliced-Wasserstein Distance](https://mlsanity.com/paper/1906.04516/) (2019)
- [Kernel Methods on the Riemannian Manifold of Symmetric Positive Definite Matrices](https://mlsanity.com/paper/1412.4172/) (2014)
- [The GeometricKernels Package: Heat and Mat'ern Kernels for Geometric Learning on Manifolds, Meshes, and Graphs](https://mlsanity.com/paper/2407.08086/) (2024)
- [Gaussian Process Landmarking on Manifolds](https://mlsanity.com/paper/1802.03479/) (2018)
- [FastKASSIM: A Fast Tree Kernel-Based Syntactic Similarity Metric](https://mlsanity.com/paper/2203.08299/) (2022)
- [D2KE: From Distance to Kernel and Embedding](https://mlsanity.com/paper/1802.04956/) (2018)

## Abstract (arXiv)

Kernel methods, and Gaussian Processes (GPs) in particular, require a Hilbertian distance measure---one whose square is conditionally negative definite (CND)---to guarantee positive semi-definiteness (PSD) of the kernel matrix; a condition that fails for many natural input spaces, including smooth manifolds and spaces of probability distributions. We propose the Sparse Landmark Embedding (SLE) kernel, which eliminates this requirement entirely. Each input is embedded into a sparse feature vector via compactly supported bump functions centered at all |D| training points; applying any standard PSD kernel in this embedding space yields a kernel that is provably PSD for arbitrary distance measures. The compact support automatically controls embedding sparsity, keeping kernel matrices well-conditioned and computationally tractable despite the high ambient dimension. We provide theoretical guarantees on PSD, sparsity, stability, and universal approximation, and demonstrate, using geodesic and Wasserstein distances, that the SLE kernel matches or substantially exceeds domain-specific baselines in both predictive accuracy and uncertainty quantification.