Incremental Roseland: Batch-wise Landmark Diffusion via Kernelized Sequential Karhunen--Loève Update
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
| Singular values | Eigenfunctions | Embedding | ||||
|---|---|---|---|---|---|---|
| iRoseland | capped | iRoseland | capped | iRoseland | capped | |
| 5,000 | ||||||
| 40,000 | ||||||
| 80,000 | ||||||
| 905,000 | ||||||
| 2,000,000 | ||||||
| Singular values | Eigenfunctions | Embedding | |
| Error decay, log–log slope | |||
| Linearization error, log–log slope ( ) | |||
| Linearization error / sampling error | 1.5–5% | 0.5–3% | 0.7–3% |
| Accuracy crossover at equal memory | 80,000 | 40,000 | 55,000 |
| Error ratio, capped plain / iRoseland , at | 13.0 | 13.0 † | 12.5 |
| Error ratio, capped plain / iRoseland , at | 43.4 | 42.9 | 31 |
| Drift per batch | |||||
|---|---|---|---|---|---|
| Window | |||||
| 0 (stationary) | |||||
| 0.002 rad | |||||
| 0.01 rad | |||||
| 0.05 rad |
| Drift per batch | 0.99 | 0.95 | 0.9 | 0.8 | 0.7 | 0.6 | 0.5 | 0.4 | 0 | |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 (stationary) | 1.6 | 2.0 | 4.3 | 6.3 | 9.0 | 11.1 | 12.8 | 14.3 | 15.6 | 18.0 |
| 0.002 rad | 67.2 | 36.2 | 9.2 | 7.5 | 9.2 | 11.1 | 12.8 | 14.3 | 15.6 | 18.0 |
| 0.01 rad | 320 | 174 | 40.6 | 19.8 | 12.1 | 12.0 | 13.1 | 14.4 | 15.6 | 18.0 |
| 0.05 rad | 478 | 437 | 182 | 91.0 | 39.9 | 23.7 | 17.7 | 16.0 | 16.1 | 18.0 |
| Drift per batch | Singular values | Eigenspace | Embedding |
|---|---|---|---|
| 0 | 1 | 1 | 1 |
| 0.002 rad | 0.99 ( ) | 0.95 | 0.9 |
| 0.01 rad | 0.95 | 0.9 | 0.7 (0.7–0.8) |
| 0.05 rad | 0.8 | 0.7 | 0.5 (0.4–0.6) |
| Drift per batch | Embedding error, first order / exact | Singular-value error, first order / exact | ||
|---|---|---|---|---|
| 0 | 0.95 | / | / | |
| 0 | 0.4 | / | / | |
| 0.01 rad | 0.95 | / | / | |
| 0.01 rad | 0.8 | / | / | |
| 0.05 rad | 0.95 | / | / | |
| 0.05 rad | 0.9 | / | / |
Manifold Learning
Manifold learning finds low-dimensional structure in complex data to support visualization, geometric analysis, and more efficient learning.
See all 129 papers