WorksComputer Science
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.
AI was used for copy editing and language polishing.
Introduction
Spectral embeddings such as diffusion maps [1] and Laplacian eigenmaps [2] recover the geometry of a data manifold from the leading eigenpairs of a graph operator built on the samples. However their high memory cost is an obstacle to large scale use, requiring memory and decomposition for a dense kernel matrix. Roseland (RObust and Scalable Embedding via LANdmark Diffusion) [3, 4] reduces this cost by routing the diffusion through a small landmark set with . It forms the thin data-to-landmark cross kernel , degree-normalizes it, and computes a singular value decomposition (SVD). The resulting singular vectors converge to eigenfunctions of the Laplace–Beltrami operator [3, 4, 5, 6] while remaining robust to noise. For data points in and landmarks the cost is , comparable to Nyström-type methods [7, 8].
Many scientific and sensor datasets are not available all at once. Long-term physiological recordings [9], bedside monitoring signals [10], and wearable sensor streams [11] arrive in batches, may be too large to store or re-read, and are most useful when the embedding is current after every batch [3]. Refitting Roseland on all data seen so far costs per batch and requires every kernel row to be retained, so both latency and memory grow with the stream. What is wanted is an update whose cost depends on the batch size and the landmark count, not on the amount of data already processed.
The Sequential Karhunen–Loève (SKL) algorithm of Levy and Lindenbaum [12], as extended by Ross et al. [13], provides exactly this for principal component analysis by maintaining a truncated SVD of a growing matrix and updating it from each new batch without revisiting old observations. The premise of this paper is that Roseland’s central computational object, the SVD of the degree-normalized affinity , has the same form as the matrix SKL maintains. A new batch of data points appends rows to while the landmark dimension stays fixed. Transposed, grows by columns, which is precisely the SKL setting. The matrix being factored is a kernel (Gram-type) block rather than raw data, so the scheme is a kernelized SKL update, and tracking its SVD amounts to tracking the diffusion eigenbasis of a streaming manifold. We call the resulting method incremental Roseland (iRoseland).
The central difficulty in applying SKL to Roseland’s degree normalized affinity matrix is that degree normalization couples every row to all of the data. The degree of point is , where is the landmark column sum. When a batch arrives, changes to and every stored degree changes, so every old row of is rescaled by . In SKL, old observations never change, so the standard update does not model this. A correct combination must therefore update the old rows for the change in degree and apply any forgetting factor consistently to the degrees as well as the spectrum. Any exact method must either retain per-point information growing with , or re-read the data. iRoseland instead replaces the per-point degree correction by a first-order expansion with -independent state. We also fix a sample-size-invariant embedding scale and a gauge for the near-degenerate eigenspaces that arise on symmetric manifolds. § 3 develops these requirements.
An exact version of iROSELAND maintains a direct correspondence with ROSELAND by rescaling and refactorizing every stored row. This requires the kernel row and left singular vector of every point (or alternatively, re-reading each batch), so its cumulative cost is no lower than that of ROSELAND on all of the data. The first-order correction used by the main version of iROSELAND instead expands the degrees about a reference mean kernel row and accumulates the statistics and , giving a true single-pass batching scheme whose state does not grow with the stream. The exact version serves as a correctness reference for small streams, and the first-order version targets long streams under a memory budget. We emphasize that SKL enters the first-order method only through the correspondence of § 3. Once all landmark directions are tracked, the SKL rotations collapse to a single eigendecomposition of an matrix assembled from accumulated statistics, and no SKL update is performed explicitly.
Both versions maintain ROSELAND on data weighted by age, such that a point that arrived batches ago has weight , where is the forgetting factor. The choice of trades two kinds of error. Sampling error falls like , where is the effective sample size of the geometric weights, and lag error arises from describing the data as it was over the window rather than as it is now. It vanishes if the sampling distribution is fixed and grows with the window if the distribution drifts. We argue, and confirm empirically, that is the right choice for stationary sampling, and is best when the distribution drifts, with chosen so that the window spans a stretch of the stream over which the data are roughly unchanged (§ 3.3).
With and full storage, exact iROSELAND and ROSELAND on the same points are the same estimator, so iROSELAND offers no accuracy advantage on equal data. Its advantages are in resources, i.e. a bounded memory, single-pass operation without re-reading or storing the stream, supplying current estimates after every batch at constant cost. With the method additionally adapts to a changing distribution, at the price of a permanent sampling-error floor set by the effective sample size . A chunked two-pass ROSELAND can also run in bounded memory, but it requires the data to be read twice and does not provide a running estimate. We also note that the landmark set is fixed in the present work, so drift in the landmark geometry is not tracked. Forgetting acts on the sample weights, and data that move away from the landmarks produce small, poorly conditioned degrees. Future work will address the case where landmarks are updated to more accurately reflect streaming data.
Contributions. We first establish the correspondence between ROSELAND and SKL (§ 3) and identify what must be added to SKL in order to track a degree-normalized landmark affinity. To make embeddings from different times directly comparable we also describe a sample-size-invariant, gauge-fixed embedding. We then present the main iROSELAND algorithm based on a first-order degree expansion with periodic re-referencing (§ 4). For , a heuristic argument gives a linearization error of . When measured, it stays within 0.5–5% of the sampling error. The same construction supports by weighting the accumulated statistics. Under drift its linearization error grows with the window length and the drift rate, and is small at a well-chosen but not for windows that are too long. Finally, we provide numerical results on and , comparing exact iROSELAND with ROSELAND on the same data, as well as an equal-memory scaling study where resources are constrained to the same 5.0 MB budget. We also give results for data with drifting distribution to gauge the effects of the forgetting factor.
Background
Incremental spectral computations have been studied in several settings. Brand [14] and Baker et al. [15] give low-rank updates of the thin SVD, and incremental eigen-system updates have been developed for spectral clustering of evolving data [16, 17]. Law and Jain [18] extend manifold-learning embeddings to incremental data. These approaches update a fixed matrix factorization or a graph, whereas the degree normalization in ROSELAND rescales every previously processed row when a batch arrives. Handling this coupling, and doing so under a bounded-memory budget, is the main focus of the present work.
Notation
We follow the notation convention of ROSELAND (with the exception of § 2.3) and translate SKL into this notation in § 3. The symbols below are used in the remainder of the paper.
| Symbol | Meaning |
| data points seen so far | |
| fixed landmarks, | |
| Gaussian kernel with bandwidth | |
| kernel row of | |
| landmark-set affinity with rows (denoted in [3]) | |
| kernel rows of an incoming batch; batch size | |
| column sum of ; for a batch | |
| ROSELAND degrees | |
| normalized affinity and its SVD; | |
| singular values, | |
| degree-normalized batch rows | |
| embedding dimension; diffusion time | |
| forgetting factor | |
| sample weights, with the number of updates since arrived | |
| weighted sample count (effective window); when | |
| effective sample size of the weights; when | |
| columns through of a matrix (1-based) | |
| orthogonal gauge (Procrustes) matrix, § 3.4 | |
| drift per batch; batch index in the drift study | |
| economy QR factorization |
Table 1.
Two identities are used repeatedly. The right Gram matrix of is
so that and are its eigenvectors and eigenvalues. Because , the left singular vector of any point with kernel row extends out of sample through
Roseland
ROSELAND (RObust and Scalable Embedding via LANdmark Diffusion) [3] builds a diffusion-map-like embedding without forming an affinity. Instead of connecting data points directly, it connects each data point to a small landmark set and lets diffusion pass through the landmarks. The induced affinity is , and is a row-stochastic transition matrix on the data, which is never formed explicitly.
The algorithm proceeds as follows. First, compute the data-to-landmark cross kernel matrix with entries . Next, form the column sum and the degrees , so that . Then compute the thin SVD of the degree-normalized cross kernel, . The left singular vectors are rescaled as . Discard the first column, which is the trivial constant mode, and keep columns , with . Finally, each point is embedded as , where is the diffusion time.
As the singular vectors converge to eigenfunctions of the Laplace–Beltrami operator on the underlying manifold [3, 4]. With landmarks the cost is , substantially below the cost of full diffusion maps, and the choice is recommended.
Algorithm 1 ROSELAND
Input: data ; landmarks ; bandwidth ; embedding dimension ; diffusion time
Output: embedding
;
The following lemma shows that age-weighted ROSELAND is well-posed. This is the form that the forgetting factor produces. It holds for any positive diagonal weighting , and ROSELAND is the case .
Lemma 1. Let be any positive diagonal weight matrix and let be entrywise positive, as for the Gaussian kernel. Define the weighted column sum , the degrees , and . Then , this singular value is simple, and the corresponding right singular vector is (unique up to sign).
Proof. Let . Then . This matrix is entrywise nonnegative with row sums , so its spectral radius is . This is the standard argument that the normalized affinity of a nonnegative weighted graph has leading singular value one [19]. It is similar to the positive semidefinite matrix , whose eigenvalues are the , hence . The left singular vector is , and . Since is entrywise positive, is a positive matrix, so by Perron–Frobenius [20] the eigenvalue is simple, which gives simplicity of and uniqueness of up to sign. □
Sequential Karhunen–Loève
SKL maintains a truncated SVD of a matrix that grows by columns, without retaining or revisiting the earlier columns. In this subsection only, we follow the presentation of Ross et al. [13]: observations are stored as columns, has the rank- truncated SVD , and is a batch of new columns. Then
where is an orthonormal basis for the component of orthogonal to . The update proceeds in three steps. First, compute the orthonormal basis of the residual and form the small core matrix of (3). Second, compute the SVD of the small core, . Third, rotate the basis, , set , and discard the components beyond rank . The matrix has size , where is the rank of the residual, so the cost per update depends on , and but not on the number of columns already processed.
Algorithm 2 SKL update with forgetting (notation of [13])
Input: current factors , ; new columns ; forgetting factor ; rank Output: updated ,
\hspace{1em} forgetting enters here
;
Ross et al. add a forgetting factor by replacing with in , which is equivalent to factorizing . Each update multiplies the amplitude of all earlier columns by , so a block added updates ago contributes to the modelled covariance with weight . With all blocks count equally, which is the stationary setting. With the decomposition follows recent data and gradually discards old data, which is useful when the sampling distribution changes. Their running count of the sample history, used in the mean update, evolves as and equilibrates at .
Remark 1. Three points to note for ROSELAND:
The covariance (spectral) weight of old data is , whereas the mean-history count uses . The spectral weight mass, or window, is therefore , not .
Because the weights are unequal, the number of equally weighted points with the same variance is the Kish effective sample size [21]
and estimates have sampling error of order , so a shorter window is noisier. Its benefit is a smaller lag behind a changing distribution. The window sets the time scale of the lag, while sets the variance. The trade-off between sampling error and lag error is the familiar one in adaptive windowing for non-stationary streams [22]. § 3.3 makes this trade-off explicit and gives guidance for choosing .
ROSELAND does not center the data, so the mean-correction variant of Ross et al. does not apply. Only plain SKL and the forgetting factor are used.
Both algorithms revolve around a thin SVD, and Roseland’s SVD of is the quantity from which the embedding is read off. In SKL, appending columns to leaves the existing columns unchanged. In Roseland, however, appending rows to changes and therefore every degree , so the existing rows of are rescaled. If old data are down-weighted using the forgetting factor, they must be down-weighted in the degrees as well as in the spectrum, so that the result is Roseland on age-weighted data (Lemma 1) rather than an inconsistent mixture. This degree coupling, together with its consequences for forgetting, is the subject of § 3.
Combining Roseland and SKL
This section explains how Roseland is cast as a row-growing SKL problem and explains where the two algorithms conflict, as well as which modifications are needed for the combination to track the Roseland SVD exactly. We then discuss the forgetting factor and when it should be used. § 4 assembles these pieces into the full algorithms.
Throughout, denotes the number of singular triplets tracked by the state, and the number reported. The state after points is with , and , such that approximates . We also write for the degree-normalized batch stored as columns.
The correspondence
A new batch appends rows to while the landmark dimension stays fixed. Transposing, gains columns, which is the setting of § 2.3. The tracked basis is therefore the landmark-side factor , and SKL’s never-formed right factor is Roseland’s left factor .
| SKL (Ross et al.) | Row-growing Roseland (this paper) |
| Data matrix , observations as columns | |
| Tracked basis and values | Landmark-side and |
| New columns | |
| Ambient dimension (fixed) | Number of landmarks (fixed) |
| Number of observations (growing) | Number of data points (growing) |
| Batch size | |
| Retained rank | Tracked rank |
| Residual basis | |
| from the SVD of |
Table 8.
The matrix being factored is a kernel block rather than raw data, so the scheme is a kernelized SKL, i.e. each row of is the degree-normalized vector of kernel evaluations against the landmarks. In this notation, identity (3) reads
where is an orthonormal basis of the residual . Writing the SVD , the stacked matrix has
Because has rows, the SVD of has size with , which does not depend on . Since in (1), tracking determines the eigenpairs of the transition operator on the data, that is, the diffusion eigenbasis of the stream.
The degree coupling
The correspondence above would be complete if the old rows of were unchanged by new data. In Roseland however, the rows of are normalized by a degree that depends on all of the data. A batch updates the column sum to with , and since , the degree of every stored point changes:
The old rows of are therefore rescaled by
so the old block of the updated matrix is , not . In SKL, old observations never change, and the update (5) does not model this rescaling.
Handling the old-row rescaling needs per-row information. This leaves a choice of how to carry out the correction. To set up a direct correspondence with Roseland, we can carry out the correction exactly at the cost of storing every kernel row and left singular vector. Doing so requires three ingredients beyond the plain SKL update, which we summarize here and discuss in more detail in Appendix § 6.
To carry out the exact degree correction, old rows are rescaled by , the rescaled left factor is re-orthogonalized by a thin QR factorization, and the resulting small core is refactorized by an SVD. After this step holds exactly with orthonormal and , however two further considerations must accompany this step if exactness is to be preserved. First, because the degree correction revisits the stored left factor at every update, must be carried along and rotated by the SKL update. Without this bookkeeping orthonormality is not maintained, and the next QR counts the previous batch’s energy a second time. Second, exactness requires tracking all triplets, so that no singular value is truncated before the correction acts. The SKL core matrix requires the residual basis to be orthonormal and orthogonal to as in 4. A plain economy QR of the incoming batch overlaps and double-counts the in-subspace part of every batch, so is instead built from a rank-revealing SVD of the projected residual (Appendix § 6). With these in place, the update maintains the SVD of the (age-weighted) Roseland matrix after every batch (Proposition 1).
The exact procedure allows us to carry out a batched version of Roseland directly, but requires storing and for every point. Its memory is and each update costs with , dominated by the QR. Cumulatively this is no cheaper than refitting plain Roseland. Its value lies in its exactness, serving as the reference against which approximations are checked. (The comparison that tests the exact scheme against plain Roseland on the same weighted data is made in § 5.1.) It is practical only for small streams, while longer streams require removing the per-row dependence. This can be done to first order by accumulating aggregate statistics of the data about a reference mean kernel row, with memory independent of . This procedure and its algorithm are developed in § 4.
The forgetting factor: stationary versus drifting data
Ross et al. apply the forgetting factor to the spectrum, . In Roseland, what this represents is a weighting of the data by age, and the degrees and column sum must be weighted the same way. Suppose point carries weight , where counts the updates since it arrived, and define the weighted Roseland matrix
At a batch update, old weights become and new points get weight one, so
and each old row of is multiplied by , with as in (7) computed from the new degrees. The factor is Ross’s forgetting applied to , and the factor is the degree correction. Since , the product satisfies for all . The two factors must use the same weights, so forgetting has to enter the degrees through (9).
The factor sets the effective window
of points that really count. For example, with batches of 5,000 points gives a window of about points. The choice of is a bias–variance trade-off between two kinds of error.
Sampling error falls like , so a smaller window is noisier. Because the geometric weights are unequal, it is the error of a Roseland fit to (about for near one) equally weighted points (Remark 1), not to points.
Lag error comes from describing the data as it was over the window rather than as it is now. It is zero if the sampling distribution never changes and grows with the window if it drifts. As a heuristic, the age of the weighted data is geometrically distributed with ratio , so its mean is batches and its standard deviation is batches. A density moving by per batch is therefore described by a mixture that is both shifted, by about , and broadened, by about .
When the sampling distribution is stationary, one should use so that every point counts equally. In that case there is no lag error and the sampling error decreases as without a floor. Using on stationary data only discards information, so the error against Roseland on all data grows as decreases. When the sampling distribution drifts, one should instead use , chosen so that the window spans the stretch of the stream over which the data are roughly unchanged. One approach is to tune on held-out recent batches. § 5 quantifies the trade-off on stationary and drifting streams.
Embedding-level considerations
Because has orthonormal columns over points, its entries are , and an embedding read from shrinks as data accumulate. We therefore embed with
with ( for plain Roseland with ). Formula (2) gives the left vector of a point of weight one. In the weighted case the in-sample row of an old point is , so reads , and the factor rescales to eigenfunctions of unit norm in the -weighted empirical measure (the empirical norm when ), so the scale is for every . Equation (11) is the symmetric form based on , while Roseland’s published embedding uses , and a scale-invariant version of that form is with . The two forms are related by the point-dependent factor , the inverse square root of the normalized degree, so they agree up to scale only when degrees are nearly constant.
Therefore the two differ only by a constant factor for uniform sampling (as with equispaced landmarks on ), but for nonuniform densities they differ.
On symmetric manifolds such as the population eigenvalues come in exactly degenerate groups, and with finitely many samples the groups are split only by . Each SVD may therefore return a degenerate pair rotated by an arbitrary angle, so that embeddings from different updates are mutually rotated and no single global Procrustes alignment applied after the fact to the concatenated embedding can undo this, because the rotation differs from batch to batch. In order to compare embeddings across updates, we compute the orthogonal map
which is orthogonal Procrustes [23] with solution from the SVD [24]. The frame is initialized as after the first batch. We then rotate the embedding coordinates by , and set . Since is applied after the eigenvalue weighting, it is an isometry of the embedding. Note that is a full orthogonal matrix, not a block-diagonal one per degenerate group. When the eigenvalues within a group are split, as in the drift study, may mix modes with different eigenvalues, so that is no longer an eigenbasis. The rotated embedding nonetheless remains an isometric copy of the unrotated one. A block-diagonal variant restricted to near-degenerate groups would avoid this mixing. Related to this, the number of reported modes should not split a degenerate group.
The iRoseland Algorithm
The exact degree correction of § 3.2 makes the tracked decomposition identical to ROSELAND on (age-weighted) data, and we give it in Appendix § 6 as a correctness reference. It is not practical for large datasets or long streams since it must retain the kernel row and left singular vector of every point seen so far. The algorithm we propose, which we simply call iRoseland, removes this per-row dependence by correcting the degrees to first order in aggregate statistics. Its state is independent of the number of points processed, and it requires a single pass over the data.
First-order degree correction with bounded memory
With , the tracked state is the eigendecomposition of the matrix of (1). For the age-weighted target (8), write and for the weighted mean kernel row. Then
which for is and . The only obstacle to a single pass is the degree , which depends on all the data and so changes for every old point as evolves. Instead of correcting stored rows, we expand about a fixed reference . Define , with the fixed reference degree. Then
so is the relative change in the degree of when the mean kernel row moves from to . Since all kernel entries are positive, we have and the identity gives
Multiplying (15) by and summing,
The first sum is independent of and defines . In the second, is linear in , so exchanging the sums over and gives, entrywise,
with
and . Dropping the last sum in (16),
Let and assume . Each term of the dropped sum is positive semidefinite with coefficient in , so
Hence the first-order Gram matrix never overestimates and has relative error at most with respect to .
The sums and depend on the data only through the fixed , so each batch can be added to them and then discarded. Since every old weight is multiplied by at each update, and are multiplied by before the new batch is added, and likewise and . Every point, old or new, then receives its current degree to first order, so there is no systematic asymmetry between old and new points in the degree correction.
The expansion degrades as moves away from . Re-referencing moves the reference to the current mean. Observe that , so
Thus a first order Taylor expansion of from to is
and we re-reference as
at a cost of . Two approximations are made at each re-reference: the second-order remainder of the expansion for all accumulated points is dropped permanently, and is not moved to the new reference (doing so would need the next-order tensor). This gives a relative error of in , which later multiplies the next , so its effect on is again second order.
The re-referencing schedule depends on the forgetting factor, because determines whether the weighted count keeps growing. For stationary data with , we re-reference whenever doubles. Heuristically, each reference epoch bakes in an error for its share of the points, and the stale adds a term of the same order. Because , each epoch contributes , and the total linearization error over the epochs is , which is asymptotically negligible against the sampling error. This is an argument and not a proof. It predicts a local log–log slope near (about over once the logarithm is included), whereas the measured slopes in § 5 are to . We attribute the gap to the stale term, but we have not verified this separately.
For the weighted count stops growing, so a doubling rule would never trigger again, and we instead re-reference at every batch, which costs only an operation. On stationary data the step between consecutive references is , where is the batch mean kernel row. Since , this gives and per re-reference. A point remains in the window for about re-references, so the accumulated relative error in is of order
which is at and , in agreement with the measured value in Table 7. In § 5.3 the relative error in is to for , negligible against the sampling error. Under drift, however, each batch’s mean differs from the window mean by the lag, so moves by an amount set by the drift rate and not by sampling noise. The error reaches several percent for long windows under fast drift (Table 7). At the that is best for a given drift, the penalty is small, at most about 5% in the embedding error.
| 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 | / | / | |
| 0.05 rad | 0.8 | / | / | |
| 0.05 rad | 0.6 | / | / |
Table 7. Drifting data: first-order iRoseland () against Roseland on the same age-weighted data (), same stream (seed 1). Errors against the solution for the current density, averaged as in Table 4.
When all right directions are tracked, the SKL state is determined by , and the first-order algorithm obtains it directly from the accumulated statistics , and by an eigendecomposition, not by SKL rotations of a stored basis. The stored left factor is never needed, and with it the row-by-row bookkeeping of the exact method disappears.
The state consists of , , and one batch, which is bytes, independent of and . For and this is 5,021,200 bytes, that is 5.0 MB, of which the batch buffers ( bytes) take 4.0 MB and ( bytes) 1.0 MB. This count excludes the arrays , and formed at each step ( bytes, 60 kB here), just as the equal-memory count for Roseland in § 5 excludes its SVD workspace. Each batch costs to accumulate and for the eigendecomposition and for re-referencing. Any point is embedded on demand at cost from alone, so no stored data are needed.
The accuracy depends on the relative degree fluctuation , which is small when each degree averages many landmarks (wide kernels, many landmarks) and larger for narrow kernels, few landmarks, or sparse regions. Under drift it is also set by the lag, so it grows with the drift rate and the window length. A second-order term is possible but costs memory and time (50 MB at ). For an alternative is to keep the last batches, beyond which the weights are negligible, and form the weighted Gram matrix exactly. For large the state is the bottleneck (about 1 GB at ), and a truncated or sketched would be needed. Points embedded on arrival use the estimate available at that time. A final re-embedding with the final requires keeping each point’s kernel row ( per point) or its raw coordinates, and under forgetting such a re-embedding describes the stream by the final, recent-weighted estimate.
The Algorithm
Algorithm 3 maintains, after every batch, the leading eigenpairs of the age-weighted Gram matrix of the degree-normalized landmark affinity, from which any point can be embedded on demand. For each incoming batch, the algorithm first evaluates the Gaussian kernel block against the fixed landmarks and forms the batch column sum, exactly as in Roseland. It then decays all accumulated quantities by , including the weighted column sum , the weighted count , and the moment statistics and . The degrees of the new points are computed against the reference row , and the batch is added into and and then discarded. Depending on the forgetting factor, the reference is moved to the current mean at every batch () or whenever doubles (). The Gram matrix is then assembled from , and as in (18), symmetrized, and eigendecomposed with negative eigenvalues clamped to zero, which yields the tracked right factor and singular values . Finally, the gauge is updated by orthogonal Procrustes, and points are embedded with the scale-invariant formula (11). Because we track all right directions, the SKL residual basis, core matrix and small SVD reduce to a single eigendecomposition of and are not needed explicitly. For reference, the exact version of the algorithm that keeps every kernel row is given in Appendix § 6.
Algorithm 3 First-order iRoseland (any )
Input: landmarks ; batches ; forgetting factor ; , ,
Output: tracked after every batch; on-demand embedding
; ; ; ; unset
for each batch do
;
; ; enters
;
if is unset then ;
end if
reference degrees of the batch
;
if or then each batch if ; on doubling if
; ; (19)
end if
; (18)
, clamping negative eigenvalues to zero, sorted descending
update the gauge by orthogonal Procrustes against
end for
embedding:
Experiments
Unless stated otherwise, data points on are with . The landmarks are equispaced, . The kernel is Gaussian, with , the embedding dimension is and the diffusion time is . All computations use float64. The drift study (§ 5.3) uses the same landmarks and parameters with a non-uniform, rotating density.
| Quantity | ||
| round-off | ||
| Eigenvector error, modes 1–11 (pair-aligned) | – | round-off |
| Subspace error, top 11 | round-off | |
| over the run | ||
| Embedding RMSE, final re-embedding | ||
| Embedding RMSE, arrival-time, gauge-fixed | ||
| Embedding RMSE, arrival-time, without gauge fixing | — | |
| , same age weights | ||
| Max eigenspace distance, same age weights |
Table 1 (PDF p. 14). Exact iRoseland against plain Roseland on stationary points. The last two rows compare with Roseland computed directly on the same data with the same age weights (for this is plain Roseland). The rows above the rule compare both columns with unweighted plain Roseland on all data, so for they measure the effect of the shorter window, not an algorithmic error.
On the Laplace–Beltrami eigenfunctions are with eigenvalues , so the embedding with should recover the circle . At the fixed bandwidth the reference is not the Laplace–Beltrami limit but the landmark kernel operator itself (for example ). For uniform sampling and equispaced landmarks this operator is circulant, so its eigenvectors on the landmarks are exactly the constant and the pairs, and the eigenvalues are exactly degenerate in pairs. Individual eigenvectors within a pair are therefore not identifiable, and only eigenspaces are. All comparisons below are made after alignment within degenerate pairs, or through rotation-invariant quantities such as subspace distances and Procrustes errors. We report modes (the constant mode plus five pairs). A choice of would split the pair.
Correctness of the tracked decomposition
In the first round of experiments we apply the exact variant of iRoseland on a data stream consisting of an initial batch of 10,000 points followed by 100 batches of 1,500, for a total of 160,000 points. To check the correctness of the tracked decomposition we compare to plain (unbatched) Roseland on the same 160,000 points. Embedding errors are orthogonal-Procrustes RMSE against the full, unbatched embedding. We report the embedding in two ways: arrival-time, where each batch is embedded when it arrives and the results are concatenated, and final, where all stored points are re-embedded with the final state (Algorithm 4, last line).
Table 1 summarizes the comparison for and . For the tracked and the final embedding match plain Roseland to round-off, as Proposition 1 predicts. For the method computes Roseland on age-weighted data, whose effective window is about points against all for the batch reference. In that case the nonzero differences from plain Roseland are the sampling cost of that shorter window (§ 3.3) and not algorithmic. This is confirmed directly by computing Roseland on the same 160,000 points with the same age weights, with . With the correct weights, plain Roseland agrees with exact iRoseland to in the singular values and in the eigenspaces (last rows of Table 1).
The arrival-time embedding is somewhat less accurate than the final one because each batch is embedded with the smaller sample available at that time. Without the Procrustes frame, consecutive batches are mutually rotated within the pair, and the arrival-time RMSE is 1.08. With it, the RMSE is at (Table 1). The rotation is applied after the eigenvalue weighting and is an exact isometry, so it removes the arbitrary rotation without changing the geometry of the embedding.
Scaling study
With and full storage, exact iROSELAND and ROSELAND on the same points are the same estimator, so there is no accuracy difference on equal data, as Table 1 shows. The advantage of batching must therefore come from resources. Plain ROSELAND materializes the matrix , so its memory grows with , and keeping a current estimate after every batch costs a full refit. Exact iROSELAND removes neither cost, because the degree correction needs all stored rows. The scaling study therefore evaluates first-order iROSELAND (Algorithm 3).
All errors are measured against the population () solution for the same landmarks, , which we compute by trapezoidal quadrature on a uniform grid of 50,000 angles. The integrand is periodic and smooth, so the trapezoidal rule is spectrally accurate [25]. When the grid size is a multiple of , the matrix is circulant, so its eigenspaces are exactly the constant mode and the pairs on the landmarks. We compare first-order iROSELAND against two versions of plain ROSELAND. The first runs with unlimited memory on the first points, up to . The second runs at equal memory, holding as many points as fit in the 5.0 MB state of iROSELAND, which is points. This equal-memory count includes only and ignores the SVD workspace, which favors plain ROSELAND (with full accounting iROSELAND would overtake plain ROSELAND sooner). Beyond , capped ROSELAND is in effect a fixed-size window of points, so its accuracy plateaus.
Errors are reported for the leading 11 modes through three metrics. The singular-value error is . The eigenfunction error is over the population eigenspaces , where and are orthogonal projection matrices onto the tracked and population eigenspaces, respectively. The embedding error is the relative orthogonal-Procrustes error on 2,000 fixed test angles. To summarize when batching pays off, we define the crossover as the first checkpoint from which the mean error of iROSELAND stays below that of capped plain ROSELAND by more than one combined standard deviation, computed over the 5 seeds. All runs use a batch size of 5,000 and extend up to points.
Table 2 gives the mean error against the population solution. Plain ROSELAND with unlimited memory matches iRoseland at every it reaches (up to ), to within the linearization error discussed below. Above , the error of capped plain Roseland is frozen at its value, as expected of a fixed window, while the error of iRoseland keeps decreasing. A log–log fit gives slopes of (singular values), (eigenfunctions) and (embedding), consistent with the rate of sampling error. The linearization error, measured as the difference between iRoseland and plain Roseland on the same data, is at most (eigenfunctions) for and falls to (embedding) and (singular values) by . Its log–log slopes over are (singular values), (eigenfunctions) and (embedding). Relative to the sampling error it is 0.5–3% for the eigenfunctions and the embedding and 1.5–5% for the singular values, largest just after the first re-reference (–) and decreasing with .
| Singular values — iROSELAND | Singular values — capped | Eigenfunctions — iROSELAND | Eigenfunctions — capped | Embedding — iROSELAND | Embedding — capped | |
| 5,000 | ||||||
| 40,000 | ||||||
| 80,000 | ||||||
| 905,000 | ||||||
| 2,000,000 | ||||||
| 10,000,000 | ||||||
| 30,000,000 |
Table 2. Stationary scaling study, : mean error (5 seeds) against the population solution. “Capped” is plain ROSELAND at equal memory ().
| 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 | † | ||
| Error ratio, capped plain / iRoseland, at |
Table 3. Summary of scaling-study findings (5 seeds, batch size 5,000, ).

Figure 1. Stationary scaling study. Error curves for iRoseland, unlimited-memory plain Roseland and capped plain Roseland; linearization error; memory; and update latency.
The state of iRoseland is 5.0 MB for and , independent of . For a memory budget and landmarks, plain Roseland holds points, while iRoseland needs bytes, that is . At these settings the batch buffers ( bytes, 4.0 MB) dominate ( bytes, 1.0 MB), and dominates only when . The crossover therefore sits a few multiples above . Beyond the error ratio of capped
Roseland to iRoseland grows like , and the crossover occurs once this ratio exceeds one by more than the relative run-to-run standard deviation of the two errors. This happens at about – here. iRoseland is preferable whenever the expected stream length exceeds a few times . An iRoseland update takes 39.7 ms per batch of 5,000 points, constant in . A plain Roseland refit to keep a current estimate takes 8 ms at points, 319 ms at and 2.1 s at . The latency crossover is at .
We repeat the stationary scaling study on with , using the same protocol as on (5 seeds, errors against the population solution), and extend it to points. The results closely mirror those of the circle (Figure 2). Plain Roseland with unlimited memory is matched by iRoseland at every for which it was computed (up to ), to within the linearization error. iRoseland begins to show improvement over memory capped Roseland beyond , and continues to improve as more points are processed.

Figure 2. Stationary () scaling study on the sphere, up to points. Error against the population solution for the singular values (left), eigenfunctions (center), and embedding (right).
The conclusions of the scaling study apply to the regime. With the error of first-order iRoseland would level off at the noise floor of an effective sample of about points, much like the memory-capped plain Roseland.
Drifting data
For drifting data we use first-order iRoseland (Algorithm 3), with the reference moved at every batch for and at every batch for as well, so that comparisons are fair (the doubling rule of Algorithm 3, line 10, is not used in this study). Here points on follow a von Mises density with concentration whose peak is at in batch , so it rotates by radians per batch, . At the total rotation is 10 rad, more than one revolution. There are 200 batches of points. Errors are measured against the Roseland solution for the current density, computed by quadrature on a grid of 20,000 angles weighted by the von Mises density, and averaged over the second half of the stream at every tenth batch. Because the density is not uniform, the eigenvalue pairs are no longer degenerate, and the metrics differ from those of the scaling study. Here we consider singular values , eigenspace (the subspace distance between the leading three right singular vectors and their population counterparts), and embedding (the relative orthogonal-Procrustes error on 2,000 uniformly spaced test angles). Table 4 uses one seed, reused for every , with (Table 4 shows a subset). To separate the forgetting trade-off from the linearization, we also compute Roseland on the same age-weighted data directly (Table 5), and compare the two on the same stream for selected (Table 7).
| Drift per batch | |||||
| Window | |||||
| 0 (stationary) | |||||
| 0.002 rad | |||||
| 0.01 rad | |||||
| 0.05 rad |
Table 4. Table 4: Drifting data: embedding error of first-order iROSELAND against the solution for the current density (von Mises, ; 200 batches of 5,000; one seed). The bold entry is the smallest in each row. The window is shown for each at the end of the stream; for it is the total of points, and over the averaging window it ranges from to (from to for ).
| 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 |
Table 5. Table 5: Drifting data: embedding error (in units of ) of ROSELAND on the same age-weighted data, computed directly, against the solution for the current density (protocol of Table 4; mean over 5 seeds). The bold entry is the smallest in each row. Here uses only the latest batch.
Table 6 gives the best for each metric for the five-seed age-weighted study. The singular-value and eigenspace errors do not follow the embedding exactly, since they prefer longer windows. The overall pattern is the trade-off of § 3.3. With no drift, the best choice is in every metric, and the error increases as the window shrinks. Even very slow drift (0.002 rad per batch, 0.4 rad in total) makes about 9 times less accurate in the embedding than the best ( against at , Table 5) and about 3 times less accurate in the leading eigenspace. The singular values are not degraded at this drift rate because a rotation of the density leaves them invariant and only the broadening of § 3.3 affects them. The faster the drift, the smaller the best (Table 6). The extended grid of Table 5 brackets every optimum, and using only the latest batch () is never best. The best depends on the metric, ordered from the longest window to the shortest as singular values, eigenspace and embedding, as expected from the different sensitivity of the metrics to the shift and the broadening.
| 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) |
Table 6. Table 6: Drifting data: best for each metric (age-weighted ROSELAND, 5 seeds).
Table 7 compares first-order iROSELAND with age-weighted ROSELAND on the same stream. On stationary data the two agree to a relative error in of to , so the errors in Table 4 are those of the age-weighted estimator. Under drift the linearization error grows roughly as (driven mainly by the stale ): at 0.05 rad per batch and the relative error in is 9%, the embedding error is 0.23 against 0.18 for the exact weighting, and the singular-value error is 2.7 times larger. At the that suits the drift, the penalty is small: at 0.01 rad and the embedding errors agree to three digits, and at 0.05 rad the embedding error is 5% larger at and 2% larger at . The entries of Table 4 for long windows under fast drift therefore combine lag error and linearization error.
Exact Degree Correction
When a batch arrives, the stored degrees are updated as , and each old row of is rescaled by . Because , the combined factor satisfies , although alone may exceed one when . Both factors are computed from the same age weights, as required for the result to be ROSELAND on age-weighted data. The rescaled old block is then refactorized in two steps. First, re-orthogonalize the rescaled left factor, , with having orthonormal columns. Then
The core is upper triangular, not diagonal, because the non-uniform scaling mixes the modes. Replacing it by its diagonal discards this mixing and fixes , which is not a valid refactorization. The exact step takes the SVD of the small core,
after which exactly, with orthonormal and . The cost is a QR of an matrix per batch, . The first-order alternative replaces this step with an expansion of the degrees in aggregate statistics, as described in § 4.1.
Two details are needed for the SKL step to remain exact once the degree correction revisits stored rows. The first concerns the residual basis in Equation (4), which must be an orthonormal basis of the part of orthogonal to , as in Ross et al. A residual has rank at most , whereas a plain economy QR of an matrix with returns a full orthogonal matrix that spans and therefore overlaps . The core matrix then double-counts the in-subspace part of every batch and is no longer orthonormal. We therefore compute from a rank-revealing SVD of the residual, projected against twice, keeping the left singular vectors whose singular value exceeds (we use ), orthogonalizing once more against , and finishing with a QR. The tolerance is relative to , not to the largest residual singular value, so that a numerically zero residual yields . Because , the lower-right block of can then be written as , which equals .
The second detail concerns the stored left factor, which must be carried along. Ross et al. discard because they never revisit old observations. Here the degree correction revisits the stored at every update, so is updated as . The old block is rotated by the first block of rows of , while the remaining rows give the left vectors of the new points, which coincide with the out-of-sample formula in Equation (2) evaluated with the updated and . If the old block were left unrotated, would lose orthonormality and the next QR factorization in the degree correction would count the previous batch’s energy a second time.
Exactness also requires that no singular value be discarded before the correction acts. Truncating to at each SKL step would leave the degree correction acting on a truncated , so the identity could not be maintained. Since the right space is only -dimensional, tracking all triplets is inexpensive for moderate . In that case is empty and no singular value is lost, and the leading modes are reported. When is large and is larger still, truncation to is unavoidable and the orthonormal residual basis becomes essential, and the guarantees stated below then hold only approximately. Each batch is embedded as described in § 3.4, using the sample-size-invariant scale and the Procrustes gauge update given there.
Exactness
Proposition 1 (Exact tracking). Assume and , let the kernel be entrywise positive, and work in exact arithmetic. After every update of Algorithm 4, with any , equals the weighted ROSELAN D matrix (8) of all data seen so far, with , and and have orthonormal columns. In particular, for the tracked are those of plain ROSELAN D on all data, and for every the tracked equals one.
Algorithm 4 Exact iROSELAND (any )
Input: landmarks ; initial batch ; batches ; forgetting factor ( for stationary data, for drifting data); , , ; tracked rank
Output: tracked ; arrival-time embedding ; final embedding
; ;
, keeping triplets
; ;
for each batch do
;
; ; ▷ enters
; ;
;
; ;
; ;
; ;
end for
▷ optional re-embedding
Proof. We argue by induction on the number of updates. The invariant is that after the th update, the tracked triple satisfies
where is the weighted matrix in Equation (8) built from all data seen so far, with weights , where is the number of updates since arrived.
Base case. The initial batch has points and every weight equals one, so . The initialization computes its thin SVD and keeps all triplets, so (20) holds, and no singular value is discarded.
Inductive step. Suppose (20) holds before a batch arrives, so that . We first record how the target matrix changes. All old weights are multiplied by and the new points receive weight one, so the weighted column sum and degrees become
and the new points have degrees computed with the updated . Each old row of therefore changes from to , which equals times the old row with . The new target matrix is thus
and we show that the update produces an exact SVD of this matrix. The thin QR factorization is exact, with having orthonormal columns, so . The SVD of the small core, , gives with and . Both and have orthonormal columns, being products of matrices with orthonormal columns and orthogonal factors. Multiplying by then gives , which is exactly the first block of (21).
Because and have been updated to the weights above, is by construction exactly the new block of , with weight one.
Transposing (21) gives the form of Equation (4),
where is an orthonormal basis of the part of orthogonal to . By construction the matrix has orthonormal columns, and when the matrix is already orthogonal, so is empty and the statement is trivial. The block matrix on the right also has orthonormal columns. Hence the singular values and right and left singular vectors of the stacked matrix are obtained exactly from the SVD of the small matrix , .
The updated right factor lives in , so has at most nonzero singular values. Since we keep triplets, no nonzero singular value is discarded.
The left factor is updated as . This is a product of two matrices with orthonormal columns, so . The old block is rotated, and the new points receive their own left vectors.
Together these steps give with orthonormal factors, which is (20) for the next update, and induction completes the proof of the first claim.
For the remaining claims, note that when all weights equal one and is the matrix used by plain Roseland on all data seen so far. An SVD is unique up to signs and rotations within repeated singular values, so the tracked singular values and singular subspaces coincide with those of plain Roseland. For every , the tracked matrix is the weighted of Equation (8), and Lemma 1 gives for any positive diagonal weighting.
References
- [1]Ronald R. Coifman and Stéphane Lafon. Diffusion maps. Applied and Computational Harmonic Analysis, 21(1):5–30, 2006.DOI
- [2]Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 15(6):1373–1396, 2003.DOI
- [3]Chao Shen, Yu-Ting Lin, and Hau-Tieng Wu. Robust and scalable manifold learning via landmark diffusion for long-term medical signal processing. Journal of Machine Learning Research, 23(86):1–30, 2022.
- [4]Chao Shen and Hau-Tieng Wu. Scalability and robustness of spectral embedding: landmark diffusion is all you need. Information and Inference, 11(4):1527–1595, 2022.arxiv.org/abs/2001.00801
- [5]Amit Singer. From graph to manifold Laplacian: The convergence rate. Applied and Computational Harmonic Analysis, 21(1):128–134, 2006.DOI
- [6]Mikhail Belkin and Partha Niyogi. Towards a theoretical foundation for Laplacian-based manifold methods. Journal of Computer and System Sciences, 74(8):1289–1308, 2008.
- [7]Christopher K. I. Williams and Matthias Seeger. Using the Nyström method to speed up kernel machines. In Advances in Neural Information Processing Systems 13, pages 682–688, 2001.
- [8]Charless Fowlkes, Serge Belongie, Fan Chung, and Jitendra Malik. Spectral grouping using the Nyström method. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(2):214–225, 2004.pubmed.ncbi.nlm.nih.gov/15376896
- [9]Ary L. Goldberger, Luis A. N. Amaral, Leon Glass, Jeffrey M. Hausdorff, Plamen Ch. Ivanov, Roger G. Mark, Joseph E. Mietus, George B. Moody, Chung-Kang Peng, and H. Eugene Stanley. PhysioBank, PhysioToolkit, and PhysioNet: Components of a new research resource for complex physiologic signals. Circulation, 101(23):e215–e220, 2000.
- [10]Alistair E. W. Johnson, Tom J. Pollard, Lu Shen, Li-wei H. Lehman, Mengling Feng, Mohammad Ghassemi, Benjamin Moody, Peter Szolovits, Leo Anthony Celi, and Roger G. Mark. MIMIC-III, a freely accessible critical care database. Scientific Data, 3:160035, 2016.DOI
- [11]Vini Vijayan, James P. Connolly, Joan Condell, Nigel McKelvey, and Philip Gardiner. Review of wearable devices and data collection considerations for connected health. Sensors, 21(16):5589, 2021.DOI
- [12]Avraham Levy and Michael Lindenbaum. Sequential Karhunen–Loeve basis extraction and its application to images. IEEE Transactions on Image Processing, 9(8):1371–1374, 2000.
- [13]David A. Ross, Jongwoo Lim, Ruei-Sung Lin, and Ming-Hsuan Yang. Incremental learning for robust visual tracking. International Journal of Computer Vision, 77(1):125–141, 2008.DOI
- [14]Matthew Brand. Fast low-rank modifications of the thin singular value decomposition. Linear Algebra and its Applications, 415(1):20–30, 2006.DOI
- [15]C. G. Baker, K. A. Gallivan, and P. Van Dooren. Low-rank incremental methods for computing dominant singular subspaces. Linear Algebra and its Applications, 436(8):2866–2888, 2012.
- [16]Huazhong Ning, Wei Xu, Yun Chi, Yihong Gong, and Thomas S. Huang. Incremental spectral clustering by efficiently updating the eigen-system. Pattern Recognition, 43(1):113–127, 2010.DOI
- [17]Charanpal Dhanjal, Romaric Gaudel, and Stéphane Clémençon. Efficient eigen-updating for spectral graph clustering. Neurocomputing, 131:440–452, 2014.arxiv.org/abs/1301.1318
- [18]Martin H. C. Law and Anil K. Jain. Incremental nonlinear dimensionality reduction by manifold learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(3):377–391, 2006.pubmed.ncbi.nlm.nih.gov/16526424
- [19]Fan R. K. Chung. Spectral Graph Theory. American Mathematical Society, Providence, 1997.
- [20]S Unnikrishna Pillai, Torsten Suel, and Seunghun Cha. The perron-frobenius theorem: some of its applications. IEEE Signal Processing Magazine, 22(2):62–75, 2005.DOI
- [21]Leslie Kish. Survey Sampling. Wiley, New York, 1965.
- [22]João Gama, Indrė Žliobaitė, Albert Bifet, Mykola Pechenizkiy, and Abdelhamid Bouchachia. A survey on concept drift adaptation. ACM Computing Surveys, 46(4):44, 2014.
- [23]Peter H. Schönemann. A generalized solution of the orthogonal Procrustes problem. Psychometrika, 31(1):1–10, 1966.DOI
- [24]Gene H. Golub and Charles F. Van Loan. Matrix Computations. Johns Hopkins University Press, Baltimore, 4 edition, 2013.
- [25]Lloyd N. Trefethen and J. A. C. Weideman. The exponentially convergent trapezoidal rule. SIAM Review, 56(3):385–458, 2014.DOI