CS Paper Radar

Spectral Landmarks: Alignment of Landmark Kernel Translates with the Leading Eigenfunctions of a Kernel Operator

Jeanie Schreiber

cs.LG math.NAmath.FAmath.MG ·submitted 2026-11-16 00:01 UTC · v1

Abstract

We study the problem of choosing $m$ landmark points so that the span of the kernel translates is as close as possible to the leading $s$-dimensional eigenspace of a positive-definite kernel. The natural measure is the Hilbert-Schmidt operator discrepancy between the reproducing-kernel-Hilbert-space (RKHS) projectors onto the two subspaces. We give a closed form spectral alignment function in terms of the truncated Mercer kernel and relate it to the classical integrated power function (Nyström trace error) through a two-sided sandwich bound. Minimizing the function by gradient descent on the landmark coordinates produces landmark sets that are evenly spaced. Theoretical results show that optimal configurations are those whose eigenfunction sampling matrix is a scaled isometry. On homogeneous spaces these are exactly the minimal equal-weight cubature rules for products of leading eigenfunctions, and for every $m\ge s$ they are the configurations whose sampled eigenfunctions form a unit-norm tight frame. Experiments on $\mathbb{S}^1$ and $\mathbb{S}^2$ agree with the theory. On the circle, with $s\le2m$ and a moderate bandwidth, every random start converges to equispaced landmarks, and on the sphere the optimizer recovers the regular tetrahedron, octahedron, and icosahedron from random starts. Finally, we analyze the numerical conditioning of the problem.

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.LG stat.MLmath.PR ·2026-09-16 ·Marcus M. Noack, Maher B. Alghalayini, Mark D. Risser
similarity 0.63
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.

0.18

A Subsampled Davis-Kahan Bound for Large-Scale Eigenspace Estimation

cs.LG stat.MLstat.ME ·2026-09-06 ·Huan Qing
theoryhot direction similarity 0.62
Abstract · 24 pages

The Davis-Kahan theorem is a fundamental tool in spectral analysis, providing quantitative control over the distance between the eigenspaces of a symmetric matrix and its perturbation. However, when the matrix dimension is large, computing leading eigenvectors is computationally expensive, limiting the practical use of spectral methods in modern large-scale applications. This paper addresses this problem by proposing an independent Bernoulli sampling scheme and proves that the leading left singular vectors of the subsampled matrix faithfully approximate the target subspace of a low-rank symmetric matrix. Our main result is a subsampled Davis-Kahan bound that gives an explicit error bound depending directly on the sampling probability. The bound reveals the trade-off: the computational cost scales linearly with the sampling probability, while the statistical error scales as the inverse square root of the sampling probability. Our result thus extends the Davis-Kahan theorem to the subsampled setting, enabling scalable spectral analysis of large-scale symmetric matrices.

0.25

Random Projections for Spectral Algorithms: Optimal Rates in Sobolev Norms

cs.LG stat.ML ·2026-10-22 ·Caixing Wang, Yue Wang
similarity 0.60
Abstract

Random projections (RP) offer an effective method for reducing computational and storage overhead while preserving the geometric structure of data. However, existing studies have primarily focused on the optimal generalization performance of specific kernel-regularized algorithms with RP in the well-specified setting and under restrictive conditions. In this paper, we provide a comprehensive and improved analysis of the generalization performance of RP-based spectral algorithms under general conditions \change{without sacrificing statistical efficiency}. By leveraging the embedding property of the reproducing kernel Hilbert space (RKHS) and a refined analysis of the operator similarity, we establish optimal learning rates in Sobolev norms that match the minimax lower bounds up to logarithmic factors. For two common implementations of RP, randomized sketches and Nyström sub-sampling (uniform or leverage-based), we show that the projection dimension required for optimality is proportional to the average or maximal effective dimension, yielding a significant reduction in computational cost while maintaining the statistical efficiency. Our results do not rely on the uniform boundedness assumption on the regression function and are valid across a wide range of source conditions, i.e., $s> α_0-1/β$, where $s,β$, and $α_0$ denote the smoothness index, capacity index, and the embedding index, respectively. In the benign case when $α_0=1/β$, the optimality holds for all $s\in (0,2τ]$ with $τ$ and $γ$ denoting the qualification index and norm index. Experimental results demonstrate both the theoretical validity and the practical effectiveness of the proposed method.

0.29

Certified Approximation for Interpretable Representer Landmarks

cs.LG ·2026-09-30 ·Jayanta Mukherjee, Shourya Verma, Mengbo Wang, Jasorsi Ghosh, Ananth Grama
similarity 0.60
Abstract · 29 pages, 8 figures

Representer explanations rank the training landmarks that most influence a self-supervised representation. At scale, this ranking rests on up to four stacked approximations of the empirical neural tangent kernel (eNTK). These are random output heads, a parameter sketch, landmark sampling and a coefficient fit. Existing analyses bound each approximation separately, but none certifies the top-$K$ set against their combined error. We introduce CAIRN (Certified Approximation for Interpretable Representer laNdmarks), a framework that carries this error through to the ranking. We derive the exact variance of the sketched multi-head eNTK, which matches measurement within $4\%$ where Johnson-Lindenstrauss bounds err by up to $2.5\times$. This yields a high-probability top-$K$ certificate for a fixed coefficient fit, alongside exact residual-trace certificates for discarded spectral mass. An exact product-variance identity separates kernel error from fit variability and identifies when a larger kernel budget can still sharpen a ranking. Stochastic Lanczos Quadrature (SLQ) estimates the effective dimension within $0.72\%$ and guides the landmark budget without dense eigendecomposition. We show that residual mass does not control class coverage, and residual-greedy selection cuts the worst coverage excess of $k$-means++ from $8.5\times$ to $1.55\times$ ($4\times$ on the sketched eNTK). Cross-view initializers outperform principal-component initialization in five (AUI) to all six (CSI) settings. Against the KREPES Gauss-Newton solver, CAIRN converges $2.5$ to $11.3\times$ faster, trails by at most $0.31$ points and gains up to $3.14$ points on MNIST. Together, these results make the reliability of representer explanations measurable and show where approximation budgets are best spent.

0.22

Low-Dimensional Embeddings for Gaussian Kernels on Manifolds

cs.CG cs.LG ·2026-09-14 ·Soumik Dutta, Kunal Dutta
theory similarity 0.59
Abstract · 57 pages, 3 figures

The Gaussian kernel is a widely used similarity measure underlying kernel methods such as kernel PCA and spectral clustering, but computing Gaussian kernel distances for many pairs of points can be expensive. Using Random Fourier Features (RFF), Chen and Phillips [ALT 2017] showed that for points in a $d$-dimensional Euclidean ball in ${\mathbb R}^N$, $t=Ω((d/\varepsilon^2)\log(dR/\varepsilon))$ features suffice to preserve all pairwise Gaussian kernel distances within a $(1\pm\varepsilon)$ factor with high probability. We establish a uniform relative-error embedding theorem for the more general setting of an arbitrary positive-reach submanifold $\mathcal M\subset{\mathbb R}^N$ of intrinsic dimension $d$. We show that $t=O((d/\varepsilon^2)\log(\operatorname{vol}(\mathcal M)^2N^{2d}/(\operatorname{vol}(B_1^d(0))^2\operatorname{rch}(\mathcal M)^{2d}\varepsilon^{2d+1}δ)))$, or approximately $O((d^2/\varepsilon^2)(\log N+\log(1/(\varepsilonδ))))$, RFFs suffice, with probability $1-δ$, to preserve the Gaussian kernel distance between every pair of manifold points up to relative error $\varepsilon$. Thus the bound depends only logarithmically on the ambient dimension and on manifold parameters such as volume and reach, while retaining the $1/\varepsilon^2$ Euclidean rate. We also prove a topological consequence: under the same RFF embedding, persistent homology is preserved in the sense that weighted Cech and Rips filtrations built from Gaussian kernel power distance are $(1\pm\varepsilon_\star)$-interleaved, where $\varepsilon_\star$ accounts for both distance distortion and kernel-weight approximation.

0.22

Incremental Roseland: Batch-wise Landmark Diffusion via Kernelized Sequential Karhunen--Loève Update

cs.LG math.FAmath.NA ·2026-11-17 ·Jeanie Schreiber
code/data similarity 0.59
Abstract

Landmark diffusion (Roseland) computes a diffusion-map-style spectral embedding from the singular value decomposition of a degree-normalized data-to-landmark kernel matrix, at a cost far below that of full diffusion maps. It assumes, however, that all data are available at once. We introduce incremental Roseland (iRoseland), which casts the landmark affinity as a row-growing matrix whose SVD can be updated with a kernelized Sequential Karhunen--Loève (SKL) scheme. Degre correction is handled by a first order expansion about a reference mean kernel row and so that the landmark-side eigenbasis may be recovered from a single landmark-by-landmark eigendecomposition at each step. The presented method requires only a single pass over the data and runs in bounded-memory with state independent of the number of points processed. A forgetting factor lets the method track drifting distributions, and a sample-size-invariant embedding keeps outputs comparable across time. Experiments show agreement with Roseland to round-off on stationary data, and accuracy that exceeds equal-memory Roseland by an order of magnitude on long streams. On drifting data, we observe large gains from forgetting with a window matched to the drift.

0.41

Bayesian Optimization on Function Spaces via Sparse RKHS Manifolds

cs.LG stat.ML ·2026-10-05 ·Davide Sartor, Meghan E. Huber, Donghyun Kim, Nathan Wycoff
benchmark similarity 0.56
Abstract

Bayesian Optimization (BO) has become an established methodology for minimizing black-box functions of a vector input. Often, however, this parameter vector arises from the discretization of an inherently functional relationship. Several recent articles have considered the Functional Bayesian Optimization (FBO) setting, in which the variable to be optimized is not a member of a finite dimensional vector space, but rather an infinite dimensional function space. In this work, we propose $L^0$ Manifold Optimization (L0MO), a simple approach to FBO which searches the subset of a Reproducing Kernel Hilbert Space (RKHS) consisting of functions with a sparse representation in the kernel functions, optimizing both the kernel locations and their coefficients. We discuss in detail the relationship between our method and existing ones, providing a unifying lens through which to view prior works. To assess our method against the state of the art, we conduct an extensive computational study, and along the way develop a novel set of benchmark test functions which port standard finite-dimensional ones to the infinite dimensional domain. Our experiments demonstrate that, on balance, the proposed method achieves superior performance across a wide range of test benchmarks.

0.19

Compressing Value Predictions for Learning-Augmented Metrical Task Systems

cs.LG cs.AIcs.GT ·2026-09-27 ·Sizhe Li, Yecheng Li, Kun He
theory similarity 0.56
Abstract · 33 pages

Learning-augmented algorithms for metrical task systems (MTS) can exploit predictions of canonical dual values, but existing formulations typically require a prediction for every state. We study whether these predictions can be compressed to a small set of representative states while retaining their algorithmic value. We introduce landmark-compressed value predictions, in which the predictor reports predicted dual values only at $m$ landmarks and the remaining values are reconstructed by a Lipschitz extension. Our algorithm achieves additive excess cost $O(T\,r(L) + \sum_t δ_t)$, where $r(L)$ is the covering radius of the landmarks and $δ_t$ measures prediction error up to additive shifts; local and value-dependent bounds refine this guarantee. For sparse landmark sets on unit-spaced finite lines, we prove a matching $Ω(T r_m)$ lower bound for every randomized algorithm using fixed landmarks, even with advance access to their entire exact absolute-value table. The prediction interface also matters: on two states with one landmark, exact absolute values permit horizon-independent excess, whereas exact relative values force worst-case expected excess linear in $T$. We give PAC guarantees for learning compressed prediction tables, with efficient empirical-risk minimization for fixed landmarks. Our results connect metric coverage, prediction interfaces, and learning guarantees for compressed predictions in online MTS.

0.36