A general kernel framework for non-CND distance measures using $|\mathcal{D}|$-dimensional sparse landmark embeddings

Kernel methods, and Gaussian Processes (GPs) in particular, require a conditionally negative-definite (CND) distance measure 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 training points $|\mathcal{D}|$; 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.