cs.LGNov 17, 2026

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

Authors: Jeanie Schreiber

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.

Figures & tables

Explore similar work

Mar 22, 2026

Accelerate Vector Diffusion Maps by Landmarks

We propose a landmark-constrained algorithm, LA-VDM (Landmark Accelerated Vector Diffusion Maps), to accelerate the Vector Diffusion Maps (VDM) framework built upon the Graph Connection Laplacian (GCL), which captures pairwise connection relationships within complex datasets. LA-VDM introduces a novel two-stage normalization that effectively address nonuniform sampling densities in both the data and the landmark sets. Under a manifold model with the frame bundle structure, we show that we can accurately recover the parallel transport with landmark-constrained diffusion from a point cloud, and hence asymptotically LA-VDM converges to the connection Laplacian. The performance and accuracy of LA-VDM are demonstrated through experiments on simulated datasets and an application to nonlocal image denoising.
Sep 18, 2026

FlashDiffusion: Fused Tiled Kernel Spectral Decomposition

Diffusion maps, and kernel methods more generally, provide an interpretable nonlinear spectral representation basis for geometric learning. In the geometric limit, small bandwidth, these matrices tend to be high rank and thus require materializing dense Gaussian kernels requires O(N2)O(N^2) memory. We introduce FlashDiffusion, a matrix-free method that evaluates dense Gaussian kernel blocks in fused GPU tiles and couples the eigensolver to an empirical ββ-flow that selects the finite-sample resolution scale. A continuation over sample size and bandwidth warm-starts increasingly expensive spectral solves from coarser resolutions.
Nov 16, 2026

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

We study the problem of choosing mm landmark points so that the span of the kernel translates is as close as possible to the leading ss-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≥sm\ge s they are the configurations whose sampled eigenfunctions form a unit-norm tight frame. Experiments on S1\mathbb{S}^1 and S2\mathbb{S}^2 agree with the theory. On the circle, with s≤2ms\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.