A General Kernel Framework for Non-CND Distance Measures Using |D|-Dimensional Sparse Landmark Embeddings
Abstract
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 show that the SLE kernel matches or substantially exceeds domain-specific baselines in both predictive accuracy and uncertainty quantification using geodesic and Wasserstein distances.
Related
- Statistical Inference for Persistence Diagrams via Landmark Embeddings: Minimax Theory and Finite Approximation
- Pointed Gromov-Hausdorff Distance between lp-Wedge Sums and Isometric Embeddings of l∞
- T-embeddings as stationary measures on T-graphs
- Complete bipartite embeddings, lattice non-embeddability, and non-Euclidean powers of information distance
- Dimension-free Convergence Rate in Sliced Wasserstein Distance for Empirical Measures of Markov Processes
BibTeX
@misc{noack2026general,
title = {{A General Kernel Framework for Non-CND Distance Measures Using |D|-Dimensional Sparse Landmark Embeddings}},
author = {Marcus M. Noack and Maher B. Alghalayini and Mark D. Risser},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.19083},
eprint = {2609.19083},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.19083},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A General Kernel Framework for Non-CND Distance Measures Using |D|-Dimensional Sparse Landmark Embeddings
AU - Marcus M. Noack
AU - Maher B. Alghalayini
AU - Mark D. Risser
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2609.19083
UR - https://arxiv.org/abs/2609.19083
AB - 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 show that the SLE kernel matches or substantially exceeds domain-specific baselines in both predictive accuracy and uncertainty quantification using geodesic and Wasserstein distances.
ER -