betaFeedback

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 O(n2)O(n^2) memory and O(n3)O(n^3) decomposition for a dense n×nn \times n kernel matrix. Roseland (RObust and Scalable Embedding via LANdmark Diffusion) [3, 4] reduces this cost by routing the diffusion through a small landmark set Y={yk}k=1mY = \{y_k\}_{k=1}^{m} with m≪nm \ll n. It forms the thin n×mn \times m data-to-landmark cross kernel W(r)W^{(r)}, 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 nn data points in Rp\mathbb{R}^{p} and m=nβm = n^{\beta} landmarks the cost is O(pn1+β+n1+2β)O(pn^{1+\beta} + n^{1+2\beta}), 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 O(nm2)O(nm^2) 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 A^=D−1/2W(r)∈Rn×m\hat{A} = D^{-1/2}W^{(r)} \in\mathbb{R}^{n \times m}, has the same form as the matrix SKL maintains. A new batch of data points appends rows to A^\hat{A} while the landmark dimension mm stays fixed. Transposed, A^T\hat{A}^{\mathsf{T}} 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 xix_i is di=wiTcd_i = w_i^{\mathsf{T}}c, where c=W(r)1∈Rmc = W^{(r)}\mathbf{1} \in\mathbb{R}^{m} is the landmark column sum. When a batch arrives, cc changes to c+cBc + c_B and every stored degree changes, so every old row of A^\hat{A} is rescaled by diold/dinew≤1\sqrt{d_i^{\mathrm{old}}/d_i^{\mathrm{new}}} \le1. 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 nn, or re-read the data. iRoseland instead replaces the per-point degree correction by a first-order expansion with nn-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 T0∈Rm×mT_0 \in\mathbb{R}^{m \times m} and T1∈Rm×m×mT_1 \in\mathbb{R}^{m \times m \times m}, 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 mm landmark directions are tracked, the SKL rotations collapse to a single eigendecomposition of an m×mm \times m 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 aa batches ago has weight f2af^{2a}, where f∈[0,1]f \in[0,1] is the forgetting factor. The choice of ff trades two kinds of error. Sampling error falls like 1/nESS1/\sqrt{n_{\mathrm{ESS}}}, where nESSn_{\mathrm{ESS}} 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 f=1f = 1 is the right choice for stationary sampling, and f<1f < 1 is best when the distribution drifts, with ff chosen so that the window spans a stretch of the stream over which the data are roughly unchanged (§ 3.3).

With f=1f = 1 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 f<1f < 1 the method additionally adapts to a changing distribution, at the price of a permanent sampling-error floor set by the effective sample size nESSn_{\mathrm{ESS}}. 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 f=1f = 1, a heuristic argument gives a linearization error of O(log⁡n/n)O(\log n/n). When measured, it stays within 0.5–5% of the O(n−1/2)O(n^{-1/2}) sampling error. The same construction supports f<1f < 1 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 ff but not for windows that are too long. Finally, we provide numerical results on S1S^1 and S2S^2, 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.

SymbolMeaning
xi∈Rp, i=1,…,nx_i \in\mathbb{R}^{p},\ i=1,\ldots,ndata points seen so far
yk, k=1,…,my_k,\ k=1,\ldots,mfixed landmarks, m≪nm \ll n
Kϵ(x,y)=e−∥x−y∥2/ϵK_{\epsilon}(x,y)=e^{-\lVert x-y\rVert^2/\epsilon}Gaussian kernel with bandwidth ϵ\epsilon
wi∈Rm, (wi)k=Kϵ(xi,yk)w_i \in\mathbb{R}^{m},\ (w_i)_k=K_{\epsilon}(x_i,y_k)kernel row of xix_i
W∈Rn×mW \in\mathbb{R}^{n\times m}landmark-set affinity with rows wiTw_i^{\mathsf{T}} (denoted W(r)W^{(r)} in [3])
WB∈RnB×m, nBW_B \in\mathbb{R}^{n_B\times m},\ n_Bkernel rows of an incoming batch; batch size
c=WT1∈Rmc=W^{\mathsf{T}}\mathbf{1}\in\mathbb{R}^{m}column sum of WW; cB=WBT1c_B=W_B^{\mathsf{T}}\mathbf{1} for a batch
di=wiTc, D=diag⁡(d)d_i=w_i^{\mathsf{T}}c,\ D=\operatorname{diag}(d)ROSELAND degrees
A^=D−1/2W=UΛVT\widehat{A}=D^{-1/2}W=U\Lambda V^{\mathsf{T}}normalized affinity and its SVD; U∈Rn×k, V∈Rm×kU\in\mathbb{R}^{n\times k},\ V\in\mathbb{R}^{m\times k}
Λ=diag⁡(σ1,…,σk)\Lambda=\operatorname{diag}(\sigma_1,\ldots,\sigma_k)singular values, σ1≥σ2≥⋯\sigma_1\ge\sigma_2\ge\cdots
B^=diag⁡(WBc)−1/2WB\widehat{B}=\operatorname{diag}(W_Bc)^{-1/2}W_Bdegree-normalized batch rows
q, tq,\ tembedding dimension; diffusion time
f∈[0,1]f\in[0,1]forgetting factor
ωi, Ω=diag⁡(ω)\omega_i,\ \Omega=\operatorname{diag}(\omega)sample weights, ωi=f2ai\omega_i=f^{2a_i} with aia_i the number of updates since xix_i arrived
nw=∑iωin_w=\sum_i\omega_iweighted sample count (effective window); nw=nn_w=n when f=1f=1
nESS=(∑iωi)2/∑iωi2n_{\mathrm{ESS}}=(\sum_i\omega_i)^2/\sum_i\omega_i^2effective sample size of the weights; nESS=nn_{\mathrm{ESS}}=n when f=1f=1
Ma:bM_{a:b}columns aa through bb of a matrix MM (1-based)
G\mathcal{G}orthogonal gauge (Procrustes) matrix, § 3.4
Δ, τ\Delta,\ \taudrift per batch; batch index in the drift study
qr⁡(M)\operatorname{qr}(M)economy QR factorization

Table 1.

Two identities are used repeatedly. The right Gram matrix of A^\widehat{A} is

G:=A^TA^=∑i=1nwiwiTwiTc∈Rm×m,(1)G := \widehat{A}^{\mathsf{T}}\widehat{A} = \sum_{i=1}^{n}\frac{w_iw_i^{\mathsf{T}}}{w_i^{\mathsf{T}}c} \in\mathbb{R}^{m\times m}, \tag*{(1)}

so that VV and Λ2\Lambda^2 are its eigenvectors and eigenvalues. Because A^=UΛVT\widehat{A}=U\Lambda V^{\mathsf{T}}, the left singular vector of any point with kernel row ww extends out of sample through

u(x)T=wTwTcVΛ−1.(2)u(x)^{\mathsf{T}}=\frac{w^{\mathsf{T}}}{\sqrt{w^{\mathsf{T}}c}}V\Lambda^{-1}. \tag*{(2)}

Roseland

ROSELAND (RObust and Scalable Embedding via LANdmark Diffusion) [3] builds a diffusion-map-like embedding without forming an n×nn \times n affinity. Instead of connecting data points directly, it connects each data point to a small landmark set YY and lets diffusion pass through the landmarks. The induced n×nn \times n affinity is WWTWW^{\mathsf{T}}, and D−1WWTD^{-1}WW^{\mathsf{T}} 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 W∈Rn×mW \in\mathbb{R}^{n \times m} with entries Wik=K(xi,yk)W_{ik}=K(x_i,y_k). Next, form the column sum c=WT1c=W^{\mathsf{T}}\mathbf{1} and the degrees d=Wcd=Wc, so that Dii=eiTWWT1D_{ii}=e_i^{\mathsf{T}}WW^{\mathsf{T}}\mathbf{1}. Then compute the thin SVD of the degree-normalized cross kernel, D−1/2W=UΛVTD^{-1/2}W=U\Lambda V^{\mathsf{T}}. The left singular vectors are rescaled as U~=D−1/2U\widetilde{U}=D^{-1/2}U. Discard the first column, which is the trivial constant mode, and keep columns 2,…,q+12,\ldots,q+1, with Λ2:q+1=diag⁡(σ2,…,σq+1)\Lambda_{2:q+1}=\operatorname{diag}(\sigma_2,\ldots,\sigma_{q+1}). Finally, each point is embedded as Φt(xi)=eiTU~2:q+1Λ2:q+12t\Phi_t(x_i)=e_i^{\mathsf{T}}\widetilde{U}_{2:q+1}\Lambda_{2:q+1}^{2t}, where tt is the diffusion time.

As n→∞n \to\infty the singular vectors converge to eigenfunctions of the Laplace–Beltrami operator on the underlying manifold [3, 4]. With m=nβm=n^\beta landmarks the cost is O(pn1+β+n1+2β)O(pn^{1+\beta}+n^{1+2\beta}), substantially below the cost of full diffusion maps, and the choice β<1/2\beta<1/2 is recommended.

Algorithm 1 ROSELAND

Input: data X={xi}i=1nX=\{x_i\}_{i=1}^{n}; landmarks Y={yk}k=1mY=\{y_k\}_{k=1}^{m}; bandwidth ϵ\epsilon; embedding dimension qq; diffusion time tt

Output: embedding Φ∈Rn×q\Phi\in\mathbb{R}^{n \times q}

  1. Wik←Kϵ(xi,yk)W_{ik}\leftarrow K_\epsilon(x_i,y_k)

  2. c←WT1c\leftarrow W^{\mathsf{T}}\mathbf{1}; d←Wcd\leftarrow Wc

  3. [U,Λ,V]←svd⁡(diag⁡(d)−1/2W)[U,\Lambda,V]\leftarrow\operatorname{svd}(\operatorname{diag}(d)^{-1/2}W)

  4. U‾←diag⁡(d)−1/2U\overline{U}\leftarrow\operatorname{diag}(d)^{-1/2}U

  5. Φ←U‾2:q+1Λ2:q+12t\Phi\leftarrow\overline{U}_{2:q+1}\Lambda_{2:q+1}^{2t}

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 Ω\Omega, and ROSELAND is the case Ω=I\Omega=I.

Lemma 1. Let Ω\Omega be any positive diagonal weight matrix and let WW be entrywise positive, as for the Gaussian kernel. Define the weighted column sum c=WTΩ1c=W^{\mathsf{T}}\Omega\mathbf{1}, the degrees D=diag⁡(Wc)D=\operatorname{diag}(Wc), and A^=Ω1/2D−1/2W\widehat{A}=\Omega^{1/2}D^{-1/2}W. Then σ1(A^)=1\sigma_1(\widehat{A})=1, this singular value is simple, and the corresponding right singular vector is v1=c/∥c∥v_1=c/\lVert c\rVert (unique up to sign).

Proof. Let X=Ω1/2D1/2X=\Omega^{1/2}D^{1/2}. Then X−1(A^A^T)X=D−1WWTΩX^{-1}(\widehat{A}\widehat{A}^{\mathsf{T}})X=D^{-1}WW^{\mathsf{T}}\Omega. This matrix is entrywise nonnegative with row sums D−1W(WTΩ1)=D−1Wc=1D^{-1}W(W^{\mathsf{T}}\Omega\mathbf{1})=D^{-1}Wc=\mathbf{1}, so its spectral radius is 11. 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 A^A^T\widehat{A}\widehat{A}^{\mathsf{T}}, whose eigenvalues are the σi2\sigma_i^2, hence σ12=1\sigma_1^2=1. The left singular vector is u1∝X1=Ω1/2D1/21u_1\propto X\mathbf{1}=\Omega^{1/2}D^{1/2}\mathbf{1}, and A^Tu1∝WTΩ1=c\widehat{A}^{\mathsf{T}}u_1\propto W^{\mathsf{T}}\Omega\mathbf{1}=c. Since WW is entrywise positive, D−1WWTΩD^{-1}WW^{\mathsf{T}}\Omega is a positive matrix, so by Perron–Frobenius [20] the eigenvalue 11 is simple, which gives simplicity of σ1\sigma_1 and uniqueness of v1v_1 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, A∈Rp×NA \in\mathbb{R}^{p \times N} has the rank-kk truncated SVD A≈UAΣVATA \approx U_A \Sigma V_A^{\mathsf{T}}, and B∈Rp×ℓB \in\mathbb{R}^{p \times\ell} is a batch of ℓ\ell new columns. Then

[A B]=[UA B~]R[VAT00I],R=[ΣUATB0B~T(B−UAUATB)],(3)[A\ B] = [U_A\ \widetilde{B}]R \begin{bmatrix} V_A^{\mathsf{T}} & 0 \\ 0 & I \end{bmatrix}, \qquad R = \begin{bmatrix} \Sigma& U_A^{\mathsf{T}}B \\ 0 & \widetilde{B}^{\mathsf{T}}(B-U_AU_A^{\mathsf{T}}B) \end{bmatrix}, \tag*{(3)}

where B~=orth⁡(B−UAUATB)\widetilde{B} = \operatorname{orth}(B-U_AU_A^{\mathsf{T}}B) is an orthonormal basis for the component of BB orthogonal to UAU_A. The update proceeds in three steps. First, compute the orthonormal basis B~\widetilde{B} of the residual B−UAUATBB-U_AU_A^{\mathsf{T}}B and form the small core matrix RR of (3). Second, compute the SVD of the small core, R=U~Σ~V~TR = \widetilde{U}\widetilde{\Sigma}\widetilde{V}^{\mathsf{T}}. Third, rotate the basis, UA←[UA B~]U~U_A \leftarrow[U_A\ \widetilde{B}]\widetilde{U}, set Σ←Σ~\Sigma\leftarrow\widetilde{\Sigma}, and discard the components beyond rank kk. The matrix RR has size (k+r)×(k+ℓ)(k+r) \times(k+\ell), where r≤ℓr \le\ell is the rank of the residual, so the cost per update depends on pp, kk and ℓ\ell but not on the number NN of columns already processed.

Algorithm 2 SKL update with forgetting (notation of [13])

Input: current factors UA∈Rp×kU_A \in\mathbb{R}^{p \times k}, Σ∈Rk×k\Sigma\in\mathbb{R}^{k \times k}; new columns B∈Rp×ℓB \in\mathbb{R}^{p \times\ell}; forgetting factor ff; rank kk Output: updated UA′U_A^{\prime}, Σ′\Sigma^{\prime}

  1. B~←orth⁡(B−UAUATB)\widetilde{B} \leftarrow\operatorname{orth}(B-U_AU_A^{\mathsf{T}}B)

  2. R←[fΣUATB0B~T(B−UAUATB)]R \leftarrow\begin{bmatrix} f\Sigma& U_A^{\mathsf{T}}B \\ 0 & \widetilde{B}^{\mathsf{T}}(B-U_AU_A^{\mathsf{T}}B) \end{bmatrix} \hspace{1em} ▹\triangleright forgetting enters here

  3. [U~,Σ~,∼]←svd⁡(R)[\widetilde{U},\widetilde{\Sigma},\sim] \leftarrow\operatorname{svd}(R)

  4. UA′←[UA B~]U~:,1:kU_A^{\prime} \leftarrow[U_A\ \widetilde{B}]\widetilde{U}_{:,1:k}; Σ′←Σ~1:k\Sigma^{\prime} \leftarrow\widetilde{\Sigma}_{1:k}

Ross et al. add a forgetting factor f∈[0,1]f \in[0,1] by replacing Σ\Sigma with fΣf\Sigma in RR, which is equivalent to factorizing [fUAΣ B][fU_A\Sigma\ B]. Each update multiplies the amplitude of all earlier columns by ff, so a block added jj updates ago contributes to the modelled covariance with weight f2jf^{2j}. With f=1f=1 all blocks count equally, which is the stationary setting. With f<1f<1 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 n←fn+ℓn \leftarrow fn+\ell and equilibrates at ℓ/(1−f)\ell/(1-f).

Remark 1. Three points to note for ROSELAND:

  1. The covariance (spectral) weight of old data is f2jf^{2j}, whereas the mean-history count uses ff. The spectral weight mass, or window, is therefore nw=ℓ/(1−f2)n_{\mathrm{w}}=\ell/(1-f^2), not ℓ/(1−f)\ell/(1-f).

  1. Because the weights are unequal, the number of equally weighted points with the same variance is the Kish effective sample size [21]

nESS=(∑iωi)2∑iωi2=ℓ1+f21−f2=(1+f2)nw≈2nwn_{\mathrm{ESS}}=\frac{\left(\sum_i \omega_i\right)^2}{\sum_i \omega_i^2} =\ell\frac{1+f^2}{1-f^2} =(1+f^2)n_{\mathrm{w}}\approx2n_{\mathrm{w}}

and estimates have sampling error of order nESS−1/2n_{\mathrm{ESS}}^{-1/2}, so a shorter window is noisier. Its benefit is a smaller lag behind a changing distribution. The window nwn_{\mathrm{w}} sets the time scale of the lag, while nESSn_{\mathrm{ESS}} 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 ff.

  1. 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 D−1/2WD^{-1/2}W is the quantity from which the embedding is read off. In SKL, appending columns to AA leaves the existing columns unchanged. In Roseland, however, appending rows to WW changes cc and therefore every degree di=wiTcd_i = w_i^{\mathsf{T}}c, so the existing rows of A^\hat{A} 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, ktk_t denotes the number of singular triplets tracked by the state, and k≤ktk \leq k_t the number reported. The state after nn points is (U,Λ,V)(U,\Lambda,V) with U∈Rn×ktU \in\mathbb{R}^{n \times k_t}, Λ∈Rkt×kt\Lambda\in\mathbb{R}^{k_t \times k_t} and V∈Rm×ktV \in\mathbb{R}^{m \times k_t}, such that UΛVTU\Lambda V^{\mathsf{T}} approximates A^=D−1/2W\hat{A} = D^{-1/2}W. We also write QB=B^T∈Rm×nBQ_B = \hat{B}^{\mathsf{T}} \in\mathbb{R}^{m \times n_B} for the degree-normalized batch stored as columns.

The correspondence

A new batch appends nBn_B rows to A^∈Rn×m\hat{A} \in\mathbb{R}^{n \times m} while the landmark dimension mm stays fixed. Transposing, A^T∈Rm×n\hat{A}^{\mathsf{T}} \in\mathbb{R}^{m \times n} gains columns, which is the setting of § 2.3. The tracked basis is therefore the landmark-side factor VV, and SKL’s never-formed right factor is Roseland’s left factor UU.

SKL (Ross et al.)Row-growing Roseland (this paper)
Data matrix AA, observations as columnsA^T∈Rm×n\hat{A}^{\mathsf{T}} \in\mathbb{R}^{m \times n}
Tracked basis UAU_A and values Σ\SigmaLandmark-side VV and Λ\Lambda
New columns BBQB=B^T∈Rm×nBQ_B = \hat{B}^{\mathsf{T}} \in\mathbb{R}^{m \times n_B}
Ambient dimension pp (fixed)Number of landmarks mm (fixed)
Number of observations (growing)Number of data points nn (growing)
Batch size ℓ\ellnBn_B
Retained rank kkTracked rank ktk_t
Residual basis B~\tilde{B}Vp∈Rm×rV_p \in\mathbb{R}^{m \times r}
[U~,Σ~,V~][\tilde{U},\tilde{\Sigma},\tilde{V}] from the SVD of RR[UR,ΣR,ZR][U_R,\Sigma_R,Z_R]

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 A^\hat{A} is the degree-normalized vector of kernel evaluations Kϵ(xi,⋅)K_\epsilon(x_i,\cdot) against the landmarks. In this notation, identity (3) reads

\begin{bmatrix} \hat{A}^{\mathsf{T}} \\ \hat{B}^{\mathsf{T}} \end{bmatrix} = [V\Lambda U^{\mathsf{T}}\ \ Q_B] = [V\ \ V_p]R \begin{bmatrix} U^{\mathsf{T}} & 0 \\ 0 & I \end{bmatrix}, \qquad R = \begin{bmatrix} \Lambda& V^{\mathsf{T}}Q_B \\ 0 & V_p^{\mathsf{T}}(Q_B - VV^{\mathsf{T}}Q_B) \end{bmatrix}, \tag*{(4)}\end{bmatrix}

where VpV_p is an orthonormal basis of the residual QB−VVTQBQ_B - VV^{\mathsf{T}}Q_B. Writing the SVD R=URΣRZRTR = U_R\Sigma_R Z_R^{\mathsf{T}}, the stacked matrix has

V′=[V  Vp]UR,Λ′=ΣR,U′=blkdiag⁡(U,InB)ZR.(5)V' = [V\ \ V_p]U_R,\qquad\Lambda' = \Sigma_R,\qquad U' = \operatorname{blkdiag}(U,I_{n_B})Z_R. \tag*{(5)}

Because VV has mm rows, the SVD of RR has size (kt+r)×(kt+nB)(k_t + r) \times(k_t + n_B) with r≤m−ktr \leq m-k_t, which does not depend on nn. Since A^TA^=G\hat{A}^{\mathsf{T}}\hat{A} = G in (1), tracking (V,Λ)(V,\Lambda) determines the eigenpairs of the transition operator D−1WWTD^{-1}W W^{\mathsf{T}} 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 A^\hat{A} were unchanged by new data. In Roseland however, the rows of A^\hat{A} are normalized by a degree that depends on all of the data. A batch updates the column sum to c←c+cBc \leftarrow c+c_B with cB=WBT1c_B=W_B^{\mathsf{T}}\mathbf{1}, and since di=wiTcd_i=w_i^{\mathsf{T}}c, the degree of every stored point changes:

dinew=diold+wiTcB,i≤n.(6)d_i^{\mathrm{new}}=d_i^{\mathrm{old}}+w_i^{\mathsf{T}}c_B,\qquad i\le n. \tag*{(6)}

The old rows of A^\hat{A} are therefore rescaled by

si=diold/dinew,(7)s_i=\sqrt{d_i^{\mathrm{old}}/d_i^{\mathrm{new}}}, \tag*{(7)}

so the old block of the updated matrix is diag⁡(s)UΛVT\operatorname{diag}(s)U\Lambda V^{\mathsf{T}}, not UΛVTU\Lambda V^{\mathsf{T}}. 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 si=diold/dinews_i=\sqrt{d_i^{\mathrm{old}}/d_i^{\mathrm{new}}}, the rescaled left factor diag⁡(s)U\operatorname{diag}(s)U is re-orthogonalized by a thin QR factorization, and the resulting small kt×ktk_t\times k_t core is refactorized by an SVD. After this step UΛVT=diag⁡(s)UoldΛoldVoldTU\Lambda V^{\mathsf{T}}=\operatorname{diag}(s)U_{\mathrm{old}}\Lambda_{\mathrm{old}}V_{\mathrm{old}}^{\mathsf{T}} holds exactly with orthonormal UU and VV, 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, UU 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 kt=mk_t=m triplets, so that no singular value is truncated before the correction acts. The SKL core matrix requires the residual basis VpV_p to be orthonormal and orthogonal to VV as in 4. A plain economy QR of the incoming batch overlaps range⁡(V)\operatorname{range}(V) and double-counts the in-subspace part of every batch, so VpV_p 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 WW and UU for every point. Its memory is O(n⋅2m)O(n\cdot2m) and each update costs O(nm2+nBm2)O(nm^2+n_Bm^2) with kt=mk_t=m, 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 nn. 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, Λ←fΛ\Lambda\leftarrow f\Lambda. 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 xix_i carries weight wi=f2aiw_i=f^{2a_i}, where aia_i counts the updates since it arrived, and define the weighted Roseland matrix

A^=Ω1/2D−1/2W,c=WTΩ1,D=diag⁡(Wc).(8)\hat{A}=\Omega^{1/2}D^{-1/2}W,\qquad c=W^{\mathsf{T}}\Omega\mathbf{1},\qquad D=\operatorname{diag}(Wc). \tag*{(8)}

At a batch update, old weights become ωi←f2ωi\omega_i \leftarrow f^2\omega_i and new points get weight one, so

c←f2c+cB,di←f2diold+wiTcB,(9)c \leftarrow f^2c+c_B,\qquad d_i \leftarrow f^2d_i^{\mathrm{old}}+w_i^{\mathsf T}c_B, \tag*{(9)}

and each old row ωi wiT/di\sqrt{\omega_i}\,w_i^{\mathsf T}/\sqrt{d_i} of A^\hat{A} is multiplied by fsifs_i, with sis_i as in (7) computed from the new degrees. The factor ff is Ross’s forgetting applied to Λ\Lambda, and the factor sis_i is the degree correction. Since dinew≥f2dioldd_i^{\mathrm{new}} \ge f^2d_i^{\mathrm{old}}, the product satisfies fsi≤1fs_i \le1 for all ff. The two factors must use the same weights, so forgetting has to enter the degrees through (9).

The factor ff sets the effective window

nw=∑iωi⟶nB1−f2(10)n_w=\sum_i\omega_i\longrightarrow\frac{n_B}{1-f^2} \tag*{(10)}

of points that really count. For example, f=0.95f=0.95 with batches of 5,000 points gives a window of about 5.1×1045.1\times10^4 points. The choice of ff is a bias–variance trade-off between two kinds of error.

  • Sampling error falls like 1/nESS1/\sqrt{n_{\mathrm{ESS}}}, so a smaller window is noisier. Because the geometric weights are unequal, it is the error of a Roseland fit to nESS=(1+f2)nwn_{\mathrm{ESS}}=(1+f^2)n_w (about 2nw2n_w for ff near one) equally weighted points (Remark 1), not to nwn_w 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 f2f^2, so its mean is f2/(1−f2)f^2/(1-f^2) batches and its standard deviation is f/(1−f2)f/(1-f^2) batches. A density moving by Δ\Delta per batch is therefore described by a mixture that is both shifted, by about Δf2/(1−f2)\Delta f^2/(1-f^2), and broadened, by about Δf/(1−f2)\Delta f/(1-f^2).

When the sampling distribution is stationary, one should use f=1f=1 so that every point counts equally. In that case there is no lag error and the sampling error decreases as n−1/2n^{-1/2} without a floor. Using f<1f<1 on stationary data only discards information, so the error against Roseland on all data grows as ff decreases. When the sampling distribution drifts, one should instead use f<1f<1, chosen so that the window nw≈nB/(1−f2)n_w\approx n_B/(1-f^2) spans the stretch of the stream over which the data are roughly unchanged. One approach is to tune ff on held-out recent batches. § 5 quantifies the trade-off on stationary and drifting streams.

Embedding-level considerations

Because UU has orthonormal columns over nn points, its entries are O(n−1/2)O(n^{-1/2}), and an embedding read from UΛ2tU\Lambda^{2t} shrinks as data accumulate. We therefore embed with

Φ(x)=nww(x)Tw(x)TcV2:q+1Λ2:q+12t−1=nw u(x)2:q+1Λ2:q+12t,(11)\Phi(x)=\sqrt{n_w}\frac{w(x)^{\mathsf T}}{\sqrt{w(x)^{\mathsf T}c}}V_{2:q+1}\Lambda_{2:q+1}^{2t-1}=\sqrt{n_w}\,u(x)_{2:q+1}\Lambda_{2:q+1}^{2t}, \tag*{(11)}

with nw=∑iωin_w=\sum_i\omega_i (nw=nn_w=n for plain Roseland with f=1f=1). 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 ωi u(xi)T\sqrt{\omega_i}\,u(x_i)^{\mathsf T}, so ∑iuij2=1\sum_i u_{ij}^2=1 reads ∑iωiuj(xi)2=1\sum_i\omega_i u_j(x_i)^2=1, and the factor nw\sqrt{n_w} rescales to eigenfunctions of unit norm in the ω\omega-weighted empirical measure (the empirical L2(ρ)L^2(\rho) norm when f=1f=1), so the scale is O(1)O(1) for every nn. Equation (11) is the symmetric form based on UU, while Roseland’s published embedding uses Uˉ=D−1/2U\bar{U}=D^{-1/2}U, and a scale-invariant version of that form is Φ(x)=(wT/(wTμ))VΛ2t−1\Phi(x)=(w^{\mathsf T}/(w^{\mathsf T}\mu))V\Lambda^{2t-1} with μ=c/nw\mu=c/n_w. The two forms are related by the point-dependent factor (wTμ)−1/2(w^{\mathsf T}\mu)^{-1/2}, 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 S1S^1), but for nonuniform densities they differ.

On symmetric manifolds such as S1S^1 the population eigenvalues come in exactly degenerate groups, and with finitely many samples the groups are split only by O(n−1/2)O(n^{-1/2}). 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

G=arg⁡min⁡G⊤G=I∥V2:q+1G−Vframe∥F,(12)\mathcal{G} = \underset{\mathcal{G}^{\top}\mathcal{G}=I}{\arg\min}\left\|V_{2:q+1}\mathcal{G}-V_{\mathrm{frame}}\right\|_{F}, \tag*{(12)}

which is orthogonal Procrustes [23] with solution G=UGVG⊤\mathcal{G}=U_{\mathcal{G}}V_{\mathcal{G}}^{\top} from the SVD V2:q+1⊤Vframe=UGΣGVG⊤V_{2:q+1}^{\top}V_{\mathrm{frame}}=U_{\mathcal{G}}\Sigma_{\mathcal{G}}V_{\mathcal{G}}^{\top} [24]. The frame is initialized as Vframe←V2:q+1V_{\mathrm{frame}}\leftarrow V_{2:q+1} after the first batch. We then rotate the embedding coordinates by G\mathcal{G}, and set Vframe←V2:q+1GV_{\mathrm{frame}}\leftarrow V_{2:q+1}\mathcal{G}. Since G\mathcal{G} is applied after the eigenvalue weighting, it is an isometry of the embedding. Note that G\mathcal{G} is a full q×qq \times q orthogonal matrix, not a block-diagonal one per degenerate group. When the eigenvalues within a group are split, as in the drift study, G\mathcal{G} may mix modes with different eigenvalues, so that V2:q+1GV_{2:q+1}\mathcal{G} 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 kk 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 kt=mk_t=m, the tracked state (V,Λ)(V,\Lambda) is the eigendecomposition of the m×mm \times m matrix G=A^⊤A^G=\hat{A}^{\top}\hat{A} of (1). For the age-weighted target (8), write nw=∑iωin_w=\sum_i\omega_i and μ=c/nw\mu=c/n_w for the weighted mean kernel row. Then

G(μ)=∑iωiwiwi⊤wi⊤c=1nw∑iωiwiwi⊤wi⊤μ,(13)G(\mu)=\sum_i\frac{\omega_i w_i w_i^{\top}}{w_i^{\top}c}=\frac{1}{n_w}\sum_i\frac{\omega_i w_i w_i^{\top}}{w_i^{\top}\mu}, \tag*{(13)}

which for f=1f=1 is ωi=1\omega_i=1 and nw=nn_w=n. The only obstacle to a single pass is the degree wi⊤μw_i^{\top}\mu, which depends on all the data and so changes for every old point as μ\mu evolves. Instead of correcting stored rows, we expand about a fixed reference μr\mu_r. Define δ=μ−μr\delta=\mu-\mu_r, with gi=wi⊤μr>0g_i=w_i^{\top}\mu_r>0 the fixed reference degree. Then

wi⊤μ=gi(1+ϵi),ϵi=wi⊤δwi⊤μr,(14)w_i^{\top}\mu=g_i(1+\epsilon_i),\qquad\epsilon_i=\frac{w_i^{\top}\delta}{w_i^{\top}\mu_r}, \tag*{(14)}

so ϵi\epsilon_i is the relative change in the degree of xix_i when the mean kernel row moves from μr\mu_r to μ\mu. Since all kernel entries are positive, we have 1+ϵi=wi⊤μ/wi⊤μr>01+\epsilon_i=w_i^{\top}\mu/w_i^{\top}\mu_r>0 and the identity 1/(1+εi)=1−εi+εi2/(1+εi)1/(1+\varepsilon_i)=1-\varepsilon_i+\varepsilon_i^2/(1+\varepsilon_i) gives

1wiTμ=1gi⋅11+εi=1gi−wiTδgi2+1giεi21+εi.(15)\frac{1}{w_i^{\mathsf T}\mu}=\frac{1}{g_i}\cdot\frac{1}{1+\varepsilon_i}=\frac{1}{g_i}-\frac{w_i^{\mathsf T}\delta}{g_i^2}+\frac{1}{g_i}\frac{\varepsilon_i^2}{1+\varepsilon_i}. \tag*{(15)}

Multiplying (15) by ωiwiwiT/nw\omega_iw_iw_i^{\mathsf T}/n_w and summing,

G(μ)=1nw[∑iωiwiwiTgi−∑iωi(wiTδ)wiwiTgi2+∑iωiwiwiTgiεi21+εi].(16)G(\mu)=\frac{1}{n_w}\left[\sum_i\frac{\omega_iw_iw_i^{\mathsf T}}{g_i}-\sum_i\frac{\omega_i(w_i^{\mathsf T}\delta)w_iw_i^{\mathsf T}}{g_i^2}+\sum_i\frac{\omega_iw_iw_i^{\mathsf T}}{g_i}\frac{\varepsilon_i^2}{1+\varepsilon_i}\right]. \tag*{(16)}

The first sum is independent of δ\delta and defines T0T_0. In the second, wiTδ=∑cwicδcw_i^{\mathsf T}\delta=\sum_cw_{ic}\delta_c is linear in δ\delta, so exchanging the sums over ii and cc gives, entrywise,

∑iωiwiawib(wiTδ)gi2=∑c(∑iωiwiawibwicgi2)δc=(T1⋅δ)ab,\sum_i\frac{\omega_iw_{ia}w_{ib}(w_i^{\mathsf T}\delta)}{g_i^2}=\sum_c\left(\sum_i\frac{\omega_iw_{ia}w_{ib}w_{ic}}{g_i^2}\right)\delta_c=(T_1\cdot\delta)_{ab},

with

T0=∑iωiwiwiTwiTμr∈Rm×m,(T1)abc=∑iωiwiawibwic(wiTμr)2∈Rm×m×m,(17)T_0=\sum_i\frac{\omega_iw_iw_i^{\mathsf T}}{w_i^{\mathsf T}\mu_r}\in\mathbb{R}^{m\times m},\qquad(T_1)_{abc}=\sum_i\frac{\omega_iw_{ia}w_{ib}w_{ic}}{(w_i^{\mathsf T}\mu_r)^2}\in\mathbb{R}^{m\times m\times m}, \tag*{(17)}

and (T1⋅δ)ab=∑c(T1)abcδc(T_1\cdot\delta)_{ab}=\sum_c(T_1)_{abc}\delta_c. Dropping the last O(εi2)O(\varepsilon_i^2) sum in (16),

G(μ)≈1nw(T0−T1⋅δ).(18)G(\mu)\approx\frac{1}{n_w}(T_0-T_1\cdot\delta). \tag*{(18)}

Let ε=max⁡i∣εi∣\varepsilon=\max_i|\varepsilon_i| and assume ε<1\varepsilon<1. Each term of the dropped sum is positive semidefinite with coefficient in [0,ε2/(1−ε)][0,\varepsilon^2/(1-\varepsilon)], so

0⪯G(μ)−1nw(T0−T1⋅δ)⪯ε21−εT0nw.0\preceq G(\mu)-\frac{1}{n_w}(T_0-T_1\cdot\delta)\preceq\frac{\varepsilon^2}{1-\varepsilon}\frac{T_0}{n_w}.

Hence the first-order Gram matrix never overestimates GG and has relative error at most ε2/(1−ε)\varepsilon^2/(1-\varepsilon) with respect to T0/nwT_0/n_w.

The sums T0T_0 and T1T_1 depend on the data only through the fixed μr\mu_r, so each batch can be added to them and then discarded. Since every old weight is multiplied by f2f^2 at each update, T0T_0 and T1T_1 are multiplied by f2f^2 before the new batch is added, and likewise c←f2c+cBc\leftarrow f^2c+c_B and nw←f2nw+nBn_w\leftarrow f^2n_w+n_B. 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 μ\mu moves away from μr\mu_r. Re-referencing moves the reference to the current mean. Observe that ∇ν(wTν)−1=−w/(wTν)2\nabla_\nu(w^{\mathsf T}\nu)^{-1}=-w/(w^{\mathsf T}\nu)^2, so

DT0(μr)[δ]=−∑iωi(wiTδ)wiwiT(wiTμr)2=−T1(μr)⋅δ.DT_0(\mu_r)[\delta]=-\sum_i\frac{\omega_i(w_i^{\mathsf T}\delta)w_iw_i^{\mathsf T}}{(w_i^{\mathsf T}\mu_r)^2}=-T_1(\mu_r)\cdot\delta.

Thus a first order Taylor expansion of T0(⋅)T_0(\cdot) from μr\mu_r to μ\mu is

T0(μ)≈T0(μr)−T1(μr)⋅(μ−μr),T_0(\mu)\approx T_0(\mu_r)-T_1(\mu_r)\cdot(\mu-\mu_r),

and we re-reference as

T0←T0−T1⋅(μ−μr),μr←μ,(19)T_0\leftarrow T_0-T_1\cdot(\mu-\mu_r),\qquad\mu_r\leftarrow\mu, \tag*{(19)}

at a cost of O(m3)O(m^3). Two approximations are made at each re-reference: the second-order remainder of the expansion for all accumulated points is dropped permanently, and T1T_1 is not moved to the new reference (doing so would need the next-order tensor). This gives a relative error of O(ε)O(\varepsilon) in T1T_1, which later multiplies the next δ\delta, so its effect on GG is again second order.

The re-referencing schedule depends on the forgetting factor, because ff determines whether the weighted count nwn_w keeps growing. For stationary data with f=1f=1, we re-reference whenever nn doubles. Heuristically, each reference epoch ee bakes in an O(εe2)O(\varepsilon_e^2) error for its share ne/nn_e/n of the points, and the stale T1T_1 adds a term of the same order. Because εe2∼1/ne\varepsilon_e^2 \sim1/n_e, each epoch contributes O(1/n)O(1/n), and the total linearization error over the O(log⁡n)O(\log n) epochs is O(log⁡n/n)O(\log n/n), which is asymptotically negligible against the O(n−1/2)O(n^{-1/2}) sampling error. This is an argument and not a proof. It predicts a local log–log slope near −1-1 (about −0.9-0.9 over 104≤n≤10610^4 \le n \le10^6 once the logarithm is included), whereas the measured slopes in § 5 are −0.77-0.77 to −0.84-0.84. We attribute the gap to the stale T1T_1 term, but we have not verified this separately.

For f<1f<1 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 O(m3)O(m^3) operation. On stationary data the step between consecutive references is δ≈(nB/nw)(μB−μr)\delta\approx(n_B/n_w)(\mu_B-\mu_r), where μB\mu_B is the batch mean kernel row. Since μB−μr=O(nB−1/2)\mu_B-\mu_r=O(n_B^{-1/2}), this gives δ=O(nB/nw)\delta=O(\sqrt{n_B}/n_w) and ε2=O(nB/nw2)\varepsilon^2=O(n_B/n_w^2) per re-reference. A point remains in the window for about nw/nBn_w/n_B re-references, so the accumulated relative error in GG is of order

nwnB⋅nBnw2=1nw=1−f2nB.\frac{n_w}{n_B}\cdot\frac{n_B}{n_w^2}=\frac{1}{n_w}=\frac{1-f^2}{n_B}.

which is 2×10−52\times10^{-5} at f=0.95f=0.95 and nB=5000n_B=5000, in agreement with the measured value in Table 7. In § 5.3 the relative error in GG is 1.6×10−51.6\times10^{-5} to 4.6×10−44.6\times10^{-4} for 0.4≤f≤10.4\le f\le1, negligible against the O(nw−1/2)O(n_w^{-1/2}) sampling error. Under drift, however, each batch’s mean differs from the window mean by the lag, so δ\delta 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 ff that is best for a given drift, the penalty is small, at most about 5% in the embedding error.

Drift per batchff∥G1−Gx∥F/∥Gx∥F\lVert G_1-G_x\rVert_F/\lVert G_x\rVert_FEmbedding error, first order / exactSingular-value error, first order / exact
00.952×10−52 \times10^{-5}4.50×10−34.50 \times10^{-3} / 4.50×10−34.50 \times10^{-3}1.15×10−31.15 \times10^{-3} / 1.15×10−31.15 \times10^{-3}
00.45×10−45 \times10^{-4}1.66×10−21.66 \times10^{-2} / 1.66×10−21.66 \times10^{-2}5.44×10−35.44 \times10^{-3} / 5.39×10−35.39 \times10^{-3}
0.01 rad0.955.4×10−35.4 \times10^{-3}4.10×10−24.10 \times10^{-2} / 3.99×10−23.99 \times10^{-2}2.69×10−32.69 \times10^{-3} / 1.41×10−31.41 \times10^{-3}
0.01 rad0.83.8×10−43.8 \times10^{-4}1.19×10−21.19 \times10^{-2} / 1.19×10−21.19 \times10^{-2}2.76×10−32.76 \times10^{-3} / 2.72×10−32.72 \times10^{-3}
0.05 rad0.959.0×10−29.0 \times10^{-2}2.33×10−12.33 \times10^{-1} / 1.81×10−11.81 \times10^{-1}3.67×10−23.67 \times10^{-2} / 1.35×10−21.35 \times10^{-2}
0.05 rad0.93.1×10−23.1 \times10^{-2}1.03×10−11.03 \times10^{-1} / 9.05×10−29.05 \times10^{-2}1.17×10−21.17 \times10^{-2} / 4.7×10−34.7 \times10^{-3}
0.05 rad0.88.5×10−38.5 \times10^{-3}4.20×10−24.20 \times10^{-2} / 3.98×10−23.98 \times10^{-2}5.0×10−35.0 \times10^{-3} / 3.0×10−33.0 \times10^{-3}
0.05 rad0.62.4×10−32.4 \times10^{-3}1.85×10−21.85 \times10^{-2} / 1.81×10−21.81 \times10^{-2}4.6×10−34.6 \times10^{-3} / 4.2×10−34.2 \times10^{-3}

Table 7. Drifting data: first-order iRoseland (G1G_1) against Roseland on the same age-weighted data (GxG_x), same stream (seed 1). Errors against the n→∞n \to\infty solution for the current density, averaged as in Table 4.

When all mm right directions are tracked, the SKL state (V,Λ)(V,\Lambda) is determined by GG, and the first-order algorithm obtains it directly from the accumulated statistics T0T_0, T1T_1 and cc by an eigendecomposition, not by SKL rotations of a stored basis. The stored left factor UU is never needed, and with it the row-by-row bookkeeping of the exact method disappears.

The state consists of T1T_1, T0T_0, cc and one batch, which is 8(m3+m2+3m+2nBm)8(m^3+m^2+3m+2n_Bm) bytes, independent of nn and ff. For m=50m=50 and nB=5000n_B=5000 this is 5,021,200 bytes, that is 5.0 MB, of which the batch buffers (16nBm16n_Bm bytes) take 4.0 MB and T1T_1 (8m38m^3 bytes) 1.0 MB. This count excludes the m×mm\times m arrays GG, VV and VframeV_{\mathrm{frame}} formed at each step (24m224m^2 bytes, 60 kB here), just as the equal-memory count for Roseland in § 5 excludes its SVD workspace. Each batch costs O(nBm3)O(n_Bm^3) to accumulate T1T_1 and O(m3)O(m^3) for the eigendecomposition and for re-referencing. Any point is embedded on demand at cost O(mk)O(mk) from (V,Λ,μ)(V,\Lambda,\mu) alone, so no stored data are needed.

The accuracy depends on the relative degree fluctuation ε\varepsilon, 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 O(m4)O(m^4) memory and O(nBm4)O(n_Bm^4) time (50 MB at m=50m=50). For f<1f<1 an alternative is to keep the last K≈log⁡(tol)/(2log⁡f)K\approx\log(\mathrm{tol})/(2\log f) batches, beyond which the weights are negligible, and form the weighted Gram matrix exactly. For large mm the O(m3)O(m^3) state is the bottleneck (about 1 GB at m=500m=500), and a truncated or sketched T1T_1 would be needed. Points embedded on arrival use the estimate available at that time. A final re-embedding with the final (V,Λ)(V,\Lambda) requires keeping each point’s kernel row (O(m)O(m) 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 GG 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 f2f^2, including the weighted column sum cc, the weighted count nwn_w, and the moment statistics T0T_0 and T1T_1. The degrees of the new points are computed against the reference row μr\mu_r, and the batch is added into T0T_0 and T1T_1 and then discarded. Depending on the forgetting factor, the reference is moved to the current mean at every batch (f<1f < 1) or whenever nn doubles (f=1f = 1). The Gram matrix is then assembled from T0T_0, T1T_1 and μ=c/nw\mu= c/n_w as in (18), symmetrized, and eigendecomposed with negative eigenvalues clamped to zero, which yields the tracked right factor VV and singular values Λ\Lambda. Finally, the gauge is updated by orthogonal Procrustes, and points are embedded with the scale-invariant formula (11). Because we track all mm right directions, the SKL residual basis, core matrix and small SVD reduce to a single eigendecomposition of GG 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 f∈[0,1]f \in[0,1])

Input: landmarks YY; batches X0,X1,…X_0, X_1, \ldots; forgetting factor ff; qq, tt, ϵ\epsilon

Output: tracked (V,Λ)(V,\Lambda) after every batch; on-demand embedding Φ(x)\Phi(x)

  1. c←0c \leftarrow0; nw←0n_w \leftarrow0; T0←0T_0 \leftarrow0; T1←0T_1 \leftarrow0; μr←\mu_r \leftarrow unset

  2. for each batch XBX_B do

  3. WB←Kϵ(XB,Y)W_B \leftarrow K_\epsilon(X_B,Y); cB←WBT1c_B \leftarrow W_B^{\mathsf T}\mathbf{1}

  4. c←f2c+cBc \leftarrow f^2c+c_B; nw←f2nw+nBn_w \leftarrow f^2n_w+n_B; μ←c/nw\mu\leftarrow c/n_w ▹\triangleright ff enters

  5. T0←f2T0T_0 \leftarrow f^2T_0; T1←f2T1T_1 \leftarrow f^2T_1

  6. if μr\mu_r is unset then μr←μ\mu_r \leftarrow\mu; nref←nwn_{\mathrm{ref}} \leftarrow n_w

  7. end if

  8. g←WBμrg \leftarrow W_B\mu_r ▹\triangleright reference degrees of the batch

  9. T0←T0+∑i∈BwiwiT/giT_0 \leftarrow T_0+\sum_{i\in B}w_iw_i^{\mathsf T}/g_i; T1←T1+∑i∈Bwi⊗wi⊗wi/gi2T_1 \leftarrow T_1+\sum_{i\in B}w_i\otimes w_i\otimes w_i/g_i^2

  10. if f<1f<1 or nw≥2nrefn_w\geq2n_{\mathrm{ref}} then ▹\triangleright each batch if f<1f<1; on doubling if f=1f=1

  11. T0←T0−T1⋅(μ−μr)T_0 \leftarrow T_0-T_1\cdot(\mu-\mu_r); μr←μ\mu_r\leftarrow\mu; nref←nwn_{\mathrm{ref}}\leftarrow n_w ▹\triangleright (19)

  12. end if

  13. G←(T0−T1⋅(μ−μr))/nwG\leftarrow\left(T_0-T_1\cdot(\mu-\mu_r)\right)/n_w; G←(G+GT)/2G\leftarrow(G+G^{\mathsf T})/2 ▹\triangleright (18)

  14. [V,Λ2]←eigh⁡(G)[V,\Lambda^2]\leftarrow\operatorname{eigh}(G), clamping negative eigenvalues to zero, sorted descending

  15. update the gauge G\mathcal{G} by orthogonal Procrustes against VframeV_{\mathrm{frame}}

  16. end for

  17. embedding: Φ(x)=(wT/wTμ)V2:q+1Λ2:q+12t−1G\Phi(x)=\left(w^{\mathsf T}/\sqrt{w^{\mathsf T}\mu}\right)V_{2:q+1}\Lambda_{2:q+1}^{2t-1}\mathcal{G}

Experiments

Unless stated otherwise, data points on S1\mathbb{S}^1 are xi=(cos⁡θi,sin⁡θi)x_i=(\cos\theta_i,\sin\theta_i) with θi∼Unif⁡[0,2π)\theta_i\sim\operatorname{Unif}[0,2\pi). The m=50m=50 landmarks are equispaced, yk=(cos⁡2π(k−1)m,sin⁡2π(k−1)m)y_k=\left(\cos\frac{2\pi(k-1)}{m},\sin\frac{2\pi(k-1)}{m}\right). The kernel is Gaussian, Kϵ(x,y)=K_\epsilon(x,y)= e−∥x−y∥2/ϵe^{-\lVert x-y\rVert^{2}/\epsilon} with ϵ=0.5\epsilon=0.5, the embedding dimension is q=2q=2 and the diffusion time is t=1t=1. All computations use float64. The drift study (§ 5.3) uses the same landmarks and parameters with a non-uniform, rotating density.

Quantityf=0.95f = 0.95f=1f = 1
max⁡j≤11∣σj−σjbatch∣\max_{j \le11} \lvert\sigma_j - \sigma_j^{\mathrm{batch}} \rvert6.2×10−46.2 \times10^{-4}round-off
Eigenvector error, modes 1–11 (pair-aligned)4.54.5–8.6×10−38.6 \times10^{-3}round-off
Subspace error, top 112.8×10−32.8 \times10^{-3}round-off
max⁡(∣VTV−I∣,∣UTU−I∣)\max(\lvert V^{\mathsf{T}}V-I\rvert,\lvert U^{\mathsf{T}}U-I\rvert) over the run4.8×10−144.8 \times10^{-14}∼10−14\sim10^{-14}
Embedding RMSE, final re-embedding3.8×10−33.8 \times10^{-3}3.2×10−143.2 \times10^{-14}
Embedding RMSE, arrival-time, gauge-fixed8.3×10−38.3 \times10^{-3}4.1×10−34.1 \times10^{-3}
Embedding RMSE, arrival-time, without gauge fixing1.081.08—
max⁡j≤11∣σj−σjw∣\max_{j \le11} \lvert\sigma_j - \sigma_j^{\mathrm{w}} \rvert, same age weights7×10−157 \times10^{-15}8×10−148 \times10^{-14}
Max eigenspace distance, same age weights3.5×10−143.5 \times10^{-14}6×10−146 \times10^{-14}

Table 1 (PDF p. 14). Exact iRoseland against plain Roseland on 1.6×1051.6 \times10^{5} stationary points. The last two rows compare with Roseland computed directly on the same data with the same age weights ωi=f2ai\omega_i=f^{2a_i} (for f=1f=1 this is plain Roseland). The rows above the rule compare both columns with unweighted plain Roseland on all data, so for f=0.95f=0.95 they measure the effect of the shorter window, not an algorithmic error.

On S1S^{1} the Laplace–Beltrami eigenfunctions are 1,cos⁡jθ,sin⁡jθ1,\cos j\theta,\sin j\theta with eigenvalues 0,1,1,4,4,9,9,…0,1,1,4,4,9,9,\ldots, so the embedding with q=2q=2 should recover the circle (cos⁡θ,sin⁡θ)(\cos\theta,\sin\theta). At the fixed bandwidth ϵ=0.5\epsilon=0.5 the reference is not the Laplace–Beltrami limit but the landmark kernel operator itself (for example σ2=0.8644\sigma_{2}=0.8644). For uniform sampling and equispaced landmarks this operator is circulant, so its eigenvectors on the landmarks are exactly the constant and the cos⁡jθ,sin⁡jθ\cos j\theta,\sin j\theta 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 k=11k=11 modes (the constant mode plus five pairs). A choice of k=10k=10 would split the cos⁡5θ/sin⁡5θ\cos5\theta/\sin5\theta 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 f=1f=1 and f=0.95f=0.95. For f=1f=1 the tracked (V,Λ)(V,\Lambda) and the final embedding match plain Roseland to round-off, as Proposition 1 predicts. For f=0.95f=0.95 the method computes Roseland on age-weighted data, whose effective window is about nB/(1−f2)≈1.5×104n_B/(1-f^2)\approx1.5\times10^{4} points against all 1.6×1051.6\times10^{5} 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, A^=Ω1/2D−1/2W\hat{A}=\Omega^{1/2}D^{-1/2}W with c=WTΩ1c=W^{\mathsf{T}}\Omega\mathbf{1}. With the correct weights, plain Roseland agrees with exact iRoseland to 7×10−157\times10^{-15} in the singular values and 3.5×10−143.5\times10^{-14} 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 cos⁡θ/sin⁡θ\cos\theta/\sin\theta pair, and the arrival-time RMSE is 1.08. With it, the RMSE is 8.3×10−38.3 \times10^{-3} at f=0.95f = 0.95 (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 f=1f = 1 and full storage, exact iROSELAND and ROSELAND on the same nn 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 n×mn \times m matrix A^\hat{A}, so its memory grows with nn, and keeping a current estimate after every batch costs a full O(nm2)O(nm^2) 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 (n→∞n \to\infty) solution for the same landmarks, G∞=Exw[wwT/(wTμ∞)]G_{\infty} = \mathbb{E}_{x_w}\left[ww^{\mathsf{T}}/(w^{\mathsf{T}}\mu_{\infty})\right], 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 mm, the matrix G∞G_{\infty} is circulant, so its eigenspaces are exactly the constant mode and the cos⁡jθ,sin⁡jθ\cos j\theta,\sin j\theta pairs on the landmarks. We compare first-order iROSELAND against two versions of plain ROSELAND. The first runs with unlimited memory on the first nn points, up to 9.05×1059.05 \times10^5. The second runs at equal memory, holding as many points as fit in the 5.0 MB state of iROSELAND, which is ncap=12,553n_{\mathrm{cap}} = 12{,}553 points. This equal-memory count includes only WW and ignores the SVD workspace, which favors plain ROSELAND (with full accounting iROSELAND would overtake plain ROSELAND sooner). Beyond ncapn_{\mathrm{cap}}, capped ROSELAND is in effect a fixed-size window of ncapn_{\mathrm{cap}} points, so its accuracy plateaus.

Errors are reported for the leading 11 modes through three metrics. The singular-value error is max⁡j∣σj−σj∞∣\max_j \lvert\sigma_j - \sigma_j^{\infty} \rvert. The eigenfunction error is max⁡γ∥P^γ−Pγ∥2\max_{\gamma} \lVert\hat{P}_{\gamma} - P_{\gamma} \rVert_2 over the population eigenspaces γ\gamma, where P^γ\hat{P}_{\gamma} and PγP_{\gamma} 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 n∗n^* 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 30×10630 \times10^6 points.

Table 2 gives the mean error against the population solution. Plain ROSELAND with unlimited memory matches iRoseland at every nn it reaches (up to 9.05×1059.05 \times10^{5}), to within the linearization error discussed below. Above ncapn_{\mathrm{cap}}, the error of capped plain Roseland is frozen at its ncapn_{\mathrm{cap}} value, as expected of a fixed window, while the error of iRoseland keeps decreasing. A log–log fit gives slopes of −0.52-0.52 (singular values), −0.52-0.52 (eigenfunctions) and −0.54-0.54 (embedding), consistent with the n−1/2n^{-1/2} rate of sampling error. The linearization error, measured as the difference between iRoseland and plain Roseland on the same data, is at most 6×10−46 \times10^{-4} (eigenfunctions) for n≤1.5×104n \le1.5 \times10^{4} and falls to 8×10−68 \times10^{-6} (embedding) and 4×10−64 \times10^{-6} (singular values) by 9×1059 \times10^{5}. Its log–log slopes over 104≤n≤9×10510^{4} \le n \le9 \times10^{5} are −0.77-0.77 (singular values), −0.84-0.84 (eigenfunctions) and −0.82-0.82 (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 (n=1n = 1–1.5×1041.5 \times10^{4}) and decreasing with nn.

nnSingular values — iROSELANDSingular values — cappedEigenfunctions — iROSELANDEigenfunctions — cappedEmbedding — iROSELANDEmbedding — capped
5,0005.1×10−35.1 \times10^{-3}5.1×10−35.1 \times10^{-3}2.8×10−22.8 \times10^{-2}2.8×10−22.8 \times10^{-2}2.2×10−22.2 \times10^{-2}2.2×10−22.2 \times10^{-2}
40,0001.4×10−31.4 \times10^{-3}2.6×10−32.6 \times10^{-3}9.1×10−39.1 \times10^{-3}1.5×10−21.5 \times10^{-2}6.7×10−36.7 \times10^{-3}9.5×10−39.5 \times10^{-3}
80,0009.4×10−49.4 \times10^{-4}2.6×10−32.6 \times10^{-3}5.3×10−35.3 \times10^{-3}1.5×10−21.5 \times10^{-2}4.4×10−34.4 \times10^{-3}9.5×10−39.5 \times10^{-3}
905,0002.3×10−42.3 \times10^{-4}2.6×10−32.6 \times10^{-3}1.6×10−31.6 \times10^{-3}1.5×10−21.5 \times10^{-2}1.2×10−31.2 \times10^{-3}9.5×10−39.5 \times10^{-3}
2,000,0002.0×10−42.0 \times10^{-4}2.6×10−32.6 \times10^{-3}1.2×10−31.2 \times10^{-3}1.5×10−21.5 \times10^{-2}7.6×10−47.6 \times10^{-4}9.5×10−39.5 \times10^{-3}
10,000,0008.8×10−58.8 \times10^{-5}2.6×10−32.6 \times10^{-3}6.2×10−46.2 \times10^{-4}1.5×10−21.5 \times10^{-2}5.5×10−45.5 \times10^{-4}9.5×10−39.5 \times10^{-3}
30,000,0005.9×10−55.9 \times10^{-5}2.6×10−32.6 \times10^{-3}3.5×10−43.5 \times10^{-4}1.5×10−21.5 \times10^{-2}3.1×10−43.1 \times10^{-4}9.5×10−39.5 \times10^{-3}

Table 2. Stationary scaling study, f=1f = 1: mean error (5 seeds) against the population solution. “Capped” is plain ROSELAND at equal memory (ncap=12,553n_{\mathrm{cap}} = 12{,}553).

Singular valuesEigenfunctionsEmbedding
Error decay, log–log slope−0.52-0.52−0.52-0.52−0.54-0.54
Linearization error, log–log slope (104≤n≤9×10510^{4} \le n \le9 \times10^{5})−0.77-0.77−0.84-0.84−0.82-0.82
Linearization error / sampling error1.5–5%0.5–3%0.7–3%
Accuracy crossover n∗n^* at equal memory80,00040,00055,000
Error ratio, capped plain / iRoseland, at 2×1062 \times10^{6}13.0×13.0\times13.0×13.0\times†12.5×12.5\times
Error ratio, capped plain / iRoseland, at 30×10630 \times10^{6}43.4×43.4\times42.9×42.9\times31×31\times

Table 3. Summary of scaling-study findings (5 seeds, batch size 5,000, f=1f = 1).

Stationary scaling study plots

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 m=50m = 50 and nB=5,000n_B = 5{,}000, independent of nn. For a memory budget MM and mm landmarks, plain Roseland holds ncap≈M/(8m)n_{\mathrm{cap}} \approx M/(8m) points, while iRoseland needs 8(m3+m2+3m+2nBm)8(m^3 + m^2 + 3m + 2n_Bm) bytes, that is O(m3+nBm)O(m^3 + n_Bm). At these settings the batch buffers (16nBm16n_Bm bytes, 4.0 MB) dominate T1T_1 (8m38m^3 bytes, 1.0 MB), and 8m38m^3 dominates only when m2≳2nBm^2 \gtrsim2n_B. The crossover therefore sits a few multiples above ncapn_{\mathrm{cap}}. Beyond ncapn_{\mathrm{cap}} the error ratio of capped

Roseland to iRoseland grows like n/ncap\sqrt{n/n_{\mathrm{cap}}}, 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 n∗≈(3n^* \approx(3–6.5)ncap6.5)n_{\mathrm{cap}} here. iRoseland is preferable whenever the expected stream length exceeds a few times m2+2nBm^2 + 2n_B. An iRoseland update takes 39.7 ms per batch of 5,000 points, constant in nn. A plain Roseland refit to keep a current estimate takes 8 ms at 5×1035 \times10^3 points, 319 ms at 1.6×1051.6 \times10^5 and 2.1 s at 9.05×1059.05 \times10^5. The latency crossover is at n≈40,000n \approx40{,}000.

We repeat the stationary scaling study on S2S^2 with f=1f = 1, using the same protocol as on S1S^1 (5 seeds, errors against the n→∞n \to\infty population solution), and extend it to n=107n = 10^7 points. The results closely mirror those of the circle (Figure 2). Plain Roseland with unlimited memory is matched by iRoseland at every nn for which it was computed (up to n=106n = 10^6), to within the linearization error. iRoseland begins to show improvement over memory capped Roseland beyond ncapn_{\mathrm{cap}}, and continues to improve as more points are processed.

Stationary scaling study on the sphere

Figure 2. Stationary (f=1f = 1) scaling study on the sphere, up to 10710^7 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 f=1f = 1 regime. With f<1f < 1 the error of first-order iRoseland would level off at the noise floor of an effective sample of about nESS=(1+f2)nwn_{\mathrm{ESS}} = (1 + f^2)n_w 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 f<1f < 1 and at every batch for f=1f = 1 as well, so that comparisons are fair (the doubling rule of Algorithm 3, line 10, is not used in this study). Here points on S1S^1 follow a von Mises density with concentration κ=1\kappa= 1 whose peak is at Δτ\Delta\tau in batch τ=0,1,…,199\tau= 0, 1, \ldots, 199, so it rotates by Δ\Delta radians per batch, Δ∈{0,0.002,0.01,0.05}\Delta\in\{0, 0.002, 0.01, 0.05\}. At Δ=0.05\Delta= 0.05 the total rotation is 10 rad, more than one revolution. There are 200 batches of nB=5,000n_B = 5{,}000 points. Errors are measured against the n→∞n \to\infty 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 (max⁡j≤5∣σj−σj∞∣)(\max_{j \le5} \lvert\sigma_j - \sigma_j^\infty\rvert), eigenspace (the subspace distance between the leading three right singular vectors V:,1:3V_{:,1:3} 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 ff, with f∈{1,0.995,0.99,0.98,0.95,0.9,0.8}f \in\{1, 0.995, 0.99, 0.98, 0.95, 0.9, 0.8\} (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 (Δ,f)(\Delta, f) (Table 7).

Drift per batchf=1f=1f=0.99f=0.99f=0.95f=0.95f=0.9f=0.9f=0.8f=0.8
Window nwn_w10610^62.5×1052.5\times10^55.1×1045.1\times10^42.6×1042.6\times10^41.4×1041.4\times10^4
0 (stationary)1.1×10−31.1\times10^{-3}1.8×10−31.8\times10^{-3}4.5×10−34.5\times10^{-3}6.2×10−36.2\times10^{-3}8.7×10−38.7\times10^{-3}
0.002 rad6.7×10−26.7\times10^{-2}3.6×10−23.6\times10^{-2}8.8×10−38.8\times10^{-3}7.2×10−37.2\times10^{-3}8.9×10−38.9\times10^{-3}
0.01 rad3.4×10−13.4\times10^{-1}2.0×10−12.0\times10^{-1}4.1×10−24.1\times10^{-2}2.0×10−22.0\times10^{-2}1.2×10−21.2\times10^{-2}
0.05 rad4.7×10−14.7\times10^{-1}4.5×10−14.5\times10^{-1}2.3×10−12.3\times10^{-1}1.0×10−11.0\times10^{-1}4.2×10−24.2\times10^{-2}

Table 4. Table 4: Drifting data: embedding error of first-order iROSELAND against the n→∞n\to\infty solution for the current density (von Mises, κ=1\kappa=1; 200 batches of 5,000; one seed). The bold entry is the smallest in each row. The window nw≈nB/(1−f2)n_w\approx n_B/(1-f^2) is shown for each ff at the end of the stream; for f=1f=1 it is the total of 10610^6 points, and over the averaging window it ranges from 5.5×1055.5\times10^5 to 10610^6 (from 2.2×1052.2\times10^5 to 2.5×1052.5\times10^5 for f=0.99f=0.99).

Drift per batchf=1f=10.990.950.90.80.70.60.50.40
0 (stationary)1.62.04.36.39.011.112.814.315.618.0
0.002 rad67.236.29.27.59.211.112.814.315.618.0
0.01 rad32017440.619.812.112.013.114.415.618.0
0.05 rad47843718291.039.923.717.716.016.118.0

Table 5. Table 5: Drifting data: embedding error (in units of 10−310^{-3}) of ROSELAND on the same age-weighted data, computed directly, against the n→∞n\to\infty solution for the current density (protocol of Table 4; mean over 5 seeds). The bold entry is the smallest in each row. Here f=0f=0 uses only the latest batch.

Table 6 gives the best ff 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 f=1f=1 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 f=1f=1 about 9 times less accurate in the embedding than the best ff (6.7×10−26.7\times10^{-2} against 7.5×10−37.5\times10^{-3} at f=0.9f=0.9, 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 ff (Table 6). The extended grid of Table 5 brackets every optimum, and using only the latest batch (f=0f=0) is never best. The best ff 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 batchSingular valuesEigenspaceEmbedding
0111
0.002 rad0.99 (≈1\approx1)0.950.9
0.01 rad0.950.90.7 (0.7–0.8)
0.05 rad0.80.70.5 (0.4–0.6)

Table 6. Table 6: Drifting data: best ff 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 GG of 1.6×10−51.6\times10^{-5} to 4.6×10−44.6\times10^{-4}, so the errors in Table 4 are those of the age-weighted estimator. Under drift the linearization error grows roughly as Δ2/(1−f2)2\Delta^2/(1-f^2)^2 (driven mainly by the stale T~1\widetilde{T}_1): at 0.05 rad per batch and f=0.95f=0.95 the relative error in GG 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 ff that suits the drift, the penalty is small: at 0.01 rad and f=0.8f = 0.8 the embedding errors agree to three digits, and at 0.05 rad the embedding error is 5% larger at f=0.8f = 0.8 and 2% larger at f=0.6f = 0.6. 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 d←f2dold+WcBd \leftarrow f^2d_{\mathrm{old}} + Wc_B, and each old row of A^\hat{A} is rescaled by si=diold/dis_i = \sqrt{d_i^{\mathrm{old}}/d_i}. Because di≥f2dioldd_i \ge f^2d_i^{\mathrm{old}}, the combined factor satisfies fsi≤1fs_i \le1, although sis_i alone may exceed one when f<1f < 1. 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 diag⁡(s)UAVT\operatorname{diag}(s)UAV^{\mathsf{T}} is then refactorized in two steps. First, re-orthogonalize the rescaled left factor, diag⁡(s)U=QURqr\operatorname{diag}(s)U = Q_U R_{\mathrm{qr}}, with QUQ_U having orthonormal columns. Then

diag⁡(s)UΛVT=QU(RqrΛ)VT.\operatorname{diag}(s)U\Lambda V^{\mathsf{T}} = Q_U (R_{\mathrm{qr}}\Lambda) V^{\mathsf{T}}.

The core RqrΛR_{\mathrm{qr}}\Lambda is upper triangular, not diagonal, because the non-uniform scaling ss mixes the modes. Replacing it by its diagonal discards this mixing and fixes VV, which is not a valid refactorization. The exact step takes the SVD of the small kt×ktk_t \times k_t core,

RqrΛ=PΛcQ~T,U←QUP,V←VQ~,Λ←Λc,R_{\mathrm{qr}}\Lambda= P\Lambda_c\widetilde{Q}^{\mathsf{T}}, \qquad U \leftarrow Q_UP,\quad V \leftarrow V\widetilde{Q},\quad\Lambda\leftarrow\Lambda_c,

after which UΛVT=diag⁡(s)UoldΛoldVoldTU\Lambda V^{\mathsf{T}} = \operatorname{diag}(s)U_{\mathrm{old}}\Lambda_{\mathrm{old}}V_{\mathrm{old}}^{\mathsf{T}} exactly, with orthonormal UU and VV. The cost is a QR of an n×ktn \times k_t matrix per batch, O(nkt2)O(nk_t^2). 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 VpV_p in Equation (4), which must be an orthonormal basis of the part of QBQ_B orthogonal to VV, as in Ross et al. A residual QB−VVTQBQ_B - VV^{\mathsf{T}}Q_B has rank at most m−ktm-k_t, whereas a plain economy QR of an m×nBm \times n_B matrix with nB≥mn_B \ge m returns a full m×mm \times m orthogonal matrix that spans Rm\mathbb{R}^m and therefore overlaps range⁡(V)\operatorname{range}(V). The core matrix then double-counts the in-subspace part of every batch and [V Vp][V\ V_p] is no longer orthonormal. We therefore compute VpV_p from a rank-revealing SVD of the residual, projected against VV twice, keeping the left singular vectors whose singular value exceeds τ∥QB∥F\tau\lVert Q_B\rVert_F (we use τ=10−12\tau= 10^{-12}), orthogonalizing once more against VV, and finishing with a QR. The tolerance is relative to ∥QB∥F\lVert Q_B\rVert_F, not to the largest residual singular value, so that a numerically zero residual yields r=0r = 0. Because Vp⊥VV_p \perp V, the lower-right block of RR can then be written as VpTQBV_p^{\mathsf{T}}Q_B, which equals VpT(QB−VVTQB)V_p^{\mathsf{T}}(Q_B - VV^{\mathsf{T}}Q_B).

The second detail concerns the stored left factor, which must be carried along. Ross et al. discard ZRZ_R because they never revisit old observations. Here the degree correction revisits the stored UU at every update, so UU is updated as U←[U00I]ZRU \leftarrow\begin{bmatrix} U & 0 \\ 0 & I \end{bmatrix} Z_R. The old block is rotated by the first block of rows of ZRZ_R, 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 VV and Λ\Lambda. If the old block were left unrotated, UU 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 kt<mk_t < m at each SKL step would leave the degree correction acting on a truncated UΛVTU\Lambda V^{\mathsf{T}}, so the identity could not be maintained. Since the right space is only mm-dimensional, tracking all mm triplets is inexpensive for moderate mm. In that case VpV_p is empty and no singular value is lost, and the leading kk modes are reported. When mm is large and nn is larger still, truncation to kt<mk_t < m 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 kt=mk_t = m and ninit≥mn_{\mathrm{init}} \ge m, let the kernel be entrywise positive, and work in exact arithmetic. After every update of Algorithm 4, with any f∈[0,1]f \in[0,1], UΛVTU\Lambda V^{\mathsf{T}} equals the weighted ROSELAN D matrix (8) of all data seen so far, with ωi=f2ai\omega_i = f^{2a_i}, and UU and VV have orthonormal columns. In particular, for f=1f = 1 the tracked (V,Λ)(V,\Lambda) are those of plain ROSELAN D on all data, and for every ff the tracked σ1\sigma_1 equals one.

Algorithm 4 Exact iROSELAND (any f∈[0,1]f \in[0,1])

Input: landmarks YY; initial batch X0X_0; batches X1,X2,…X_1, X_2, \ldots; forgetting factor ff (f=1f=1 for stationary data, f<1f<1 for drifting data); qq, tt, ϵ\epsilon; tracked rank kt=mk_t=m

Output: tracked (V,Λ)(V,\Lambda); arrival-time embedding Φ\Phi; final embedding Φfinal\Phi_{\mathrm{final}}

  1. W←Kϵ(X0,Y)W \leftarrow K_{\epsilon}(X_0,Y); c←WT1c \leftarrow W^{\mathsf{T}}\mathbf{1}; d←Wcd \leftarrow Wc

  2. [U,Λ,V]←svd⁡(diag⁡(d)−1/2W)[U,\Lambda,V] \leftarrow\operatorname{svd}(\operatorname{diag}(d)^{-1/2}W), keeping kt=mk_t=m triplets

  3. nw←∣X0∣n_w \leftarrow|X_0|; G←Iq\mathcal{G} \leftarrow I_q; Vframe←V2:q+1V_{\mathrm{frame}} \leftarrow V_{2:q+1}

  4. Φ←Embed⁡(W,d)\Phi\leftarrow\operatorname{Embed}(W,d)

  5. for each batch XBX_B do

  6. WB←Kϵ(XB,Y)W_B \leftarrow K_{\epsilon}(X_B,Y); cB←WBT1c_B \leftarrow W_B^{\mathsf{T}}\mathbf{1}

  7. dold←dd^{\mathrm{old}} \leftarrow d; d←f2dold+WcBd \leftarrow f^2d^{\mathrm{old}}+Wc_B; s←dold/ds \leftarrow\sqrt{d^{\mathrm{old}}/d} ▷ ff enters

  8. [QU,Rqr]←qr⁡(diag⁡(s)U)[Q_U,R_{\mathrm{qr}}] \leftarrow\operatorname{qr}(\operatorname{diag}(s)U)

  9. [P,Λc,Q~]←svd⁡(RqrΛ)[P,\Lambda_c,\widetilde{Q}] \leftarrow\operatorname{svd}(R_{\mathrm{qr}}\Lambda); U←QUPU \leftarrow Q_UP; V←VQ~V \leftarrow V\widetilde{Q}

  10. Λf←fΛc\Lambda_f \leftarrow f\Lambda_c; nw←f2nw+nBn_w \leftarrow f^2n_w+n_B

  11. c←f2c+cBc \leftarrow f^2c+c_B; dB←WBcd_B \leftarrow W_Bc; B^←diag⁡(dB)−1/2WB\widehat{B} \leftarrow\operatorname{diag}(d_B)^{-1/2}W_B

  12. [V,Λ,ZR]←SKL⁡(V,Λf,B^,kt)[V,\Lambda,Z_R] \leftarrow\operatorname{SKL}(V,\Lambda_f,\widehat{B},k_t)

  13. U←[U(ZR)1:kt,:(ZR)kt+1:,:]U \leftarrow\begin{bmatrix} U(Z_R)_{1:k_t,:} \\ (Z_R)_{k_t+1:,:} \end{bmatrix}; W←[WWB]W \leftarrow\begin{bmatrix} W \\ W_B \end{bmatrix}; d←[ddB]d \leftarrow\begin{bmatrix} d \\ d_B \end{bmatrix}

  14. [UG,∼,VG]←svd⁡(V2:q+1TVframe)[U_G,\sim,V_G] \leftarrow\operatorname{svd}(V_{2:q+1}^{\mathsf{T}}V_{\mathrm{frame}}); G←UGVGT\mathcal{G} \leftarrow U_GV_G^{\mathsf{T}}; Vframe←V2:q+1GV_{\mathrm{frame}} \leftarrow V_{2:q+1}\mathcal{G}

  15. Φ←[ΦEmbed⁡(WB,dB)]\Phi\leftarrow\begin{bmatrix} \Phi\\ \operatorname{Embed}(W_B,d_B) \end{bmatrix}

  16. end for

  17. Φfinal←Embed⁡(W,d)\Phi_{\mathrm{final}} \leftarrow\operatorname{Embed}(W,d) ▷ optional re-embedding

Proof. We argue by induction on the number of updates. The invariant is that after the jjth update, the tracked triple satisfies

UΛVT=A^j,UTU=I,VTV=I,(20)U\Lambda V^{\mathsf{T}}=\widehat{A}_j,\qquad U^{\mathsf{T}}U=I,\qquad V^{\mathsf{T}}V=I, \tag*{(20)}

where A^j=Ω1/2D−1/2W\widehat{A}_j=\Omega^{1/2}D^{-1/2}W is the weighted matrix in Equation (8) built from all data seen so far, with weights ωi=f2ai\omega_i=f^{2a_i}, where aia_i is the number of updates since xix_i arrived.

Base case. The initial batch has ninit≥mn_{\mathrm{init}}\ge m points and every weight equals one, so A^0=D−1/2W\widehat{A}_0=D^{-1/2}W. The initialization computes its thin SVD and keeps all mm triplets, so (20) holds, and no singular value is discarded.

Inductive step. Suppose (20) holds before a batch XBX_B arrives, so that UΛVT=A^oldU\Lambda V^{\mathsf{T}}=\widehat{A}_{\mathrm{old}}. We first record how the target matrix changes. All old weights are multiplied by f2f^2 and the new points receive weight one, so the weighted column sum and degrees become

c←f2cold+cB,di=f2diold+wiTcBfor old points,c \leftarrow f^2c_{\mathrm{old}}+c_B,\qquad d_i=f^2d_i^{\mathrm{old}}+w_i^{\mathsf{T}}c_B\quad\text{for old points},

and the new points have degrees dB=WBcd_B=W_Bc computed with the updated cc. Each old row of A^\widehat{A} therefore changes from ωiold/diold wi\sqrt{\omega_i^{\mathrm{old}}/d_i^{\mathrm{old}}}\,w_i to f2ωiold/di wi\sqrt{f^2\omega_i^{\mathrm{old}}/d_i}\,w_i, which equals fsifs_i times the old row with si=diold/dis_i=\sqrt{d_i^{\mathrm{old}}/d_i}. The new target matrix is thus

A^new=[fdiag⁡(s) UΛVTA^B],A^B=DB−1/2WB,(21)\widehat{A}_{\mathrm{new}}= \begin{bmatrix} f\operatorname{diag}(s)\,U\Lambda V^{\mathsf{T}}\\ \widehat{A}_B \end{bmatrix}, \qquad \widehat{A}_B=D_B^{-1/2}W_B, \tag*{(21)}

and we show that the update produces an exact SVD of this matrix. The thin QR factorization diag⁡(s)U=QURqr\operatorname{diag}(s)U=Q_U R_{\mathrm{qr}} is exact, with QUQ_U having orthonormal columns, so diag⁡(s)UΛV⊤=QURqrΛV⊤\operatorname{diag}(s)U\Lambda V^\top=Q_U R_{\mathrm{qr}}\Lambda V^\top. The SVD of the small core, RqrΛ=PΛcQ~⊤R_{\mathrm{qr}}\Lambda=P\Lambda_c\widetilde{Q}^\top, gives diag⁡(s)UΛV⊤=U′ΛcV′⊤\operatorname{diag}(s)U\Lambda V^\top=U'\Lambda_cV'^\top with U′=QUPU'=Q_UP and V′=VQ~V'=V\widetilde{Q}. Both U′U' and V′V' have orthonormal columns, being products of matrices with orthonormal columns and orthogonal factors. Multiplying by ff then gives fdiag⁡(s)UΛV⊤=U′(fΛc)V′⊤f\operatorname{diag}(s)U\Lambda V^\top=U'(f\Lambda_c)V'^\top, which is exactly the first block of (21).

Because cc and dBd_B have been updated to the weights above, A^B\widehat{A}_B is by construction exactly the new block of A^new\widehat{A}_{\mathrm{new}}, with weight one.

Transposing (21) gives the form of Equation (4),

[V′fΛcU′⊤ A^B⊤]=[V′ Vp]R[U′00I]⊤,R=[fΛcV′⊤A^B⊤0Vp⊤A^B⊤]\left[V'f\Lambda_cU'^\top\ \widehat{A}_B^\top\right] = \left[V'\ V_p\right]R \begin{bmatrix} U' & 0 \\ 0 & I \end{bmatrix}^{\top}, \qquad R= \begin{bmatrix} f\Lambda_c & V'^\top\widehat{A}_B^\top\\ 0 & V_p^\top\widehat{A}_B^\top \end{bmatrix}

where VpV_p is an orthonormal basis of the part of A^B⊤\widehat{A}_B^\top orthogonal to V′V'. By construction the matrix [V′ Vp][V'\ V_p] has orthonormal columns, and when kt=mk_t=m the matrix V′V' is already orthogonal, so VpV_p 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 RR, R=URΣRZR⊤R=U_R\Sigma_R Z_R^\top.

The updated right factor Vnew=[V′ Vp]URV_{\mathrm{new}}=[V'\ V_p]U_R lives in Rm\mathbb{R}^m, so A^new\widehat{A}_{\mathrm{new}} has at most mm nonzero singular values. Since we keep kt=mk_t=m triplets, no nonzero singular value is discarded.

The left factor is updated as Unew=[U′00I]ZRU_{\mathrm{new}}=\begin{bmatrix}U' & 0 \\ 0 & I\end{bmatrix}Z_R. This is a product of two matrices with orthonormal columns, so Unew⊤Unew=IU_{\mathrm{new}}^\top U_{\mathrm{new}}=I. The old block is rotated, and the new points receive their own left vectors.

Together these steps give UnewΣRVnew⊤=A^newU_{\mathrm{new}}\Sigma_RV_{\mathrm{new}}^\top=\widehat{A}_{\mathrm{new}} 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 f=1f=1 all weights equal one and A^=D−1/2W\widehat{A}=D^{-1/2}W 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 ff, the tracked matrix is the weighted A^\widehat{A} of Equation (8), and Lemma 1 gives σ1=1\sigma_1=1 for any positive diagonal weighting.

References

  1. [1]Ronald R. Coifman and Stéphane Lafon. Diffusion maps. Applied and Computational Harmonic Analysis, 21(1):5–30, 2006.DOI
  2. [2]Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 15(6):1373–1396, 2003.DOI
  3. [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. [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. [5]Amit Singer. From graph to manifold Laplacian: The convergence rate. Applied and Computational Harmonic Analysis, 21(1):128–134, 2006.DOI
  6. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [19]Fan R. K. Chung. Spectral Graph Theory. American Mathematical Society, Providence, 1997.
  20. [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. [21]Leslie Kish. Survey Sampling. Wiley, New York, 1965.
  22. [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. [23]Peter H. Schönemann. A generalized solution of the orthogonal Procrustes problem. Psychometrika, 31(1):1–10, 1966.DOI
  24. [24]Gene H. Golub and Charles F. Van Loan. Matrix Computations. Johns Hopkins University Press, Baltimore, 4 edition, 2013.
  25. [25]Lloyd N. Trefethen and J. A. C. Weideman. The exponentially convergent trapezoidal rule. SIAM Review, 56(3):385–458, 2014.DOI

Paper details

vlnc:W_egyupscc
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 8

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

AI

View statement
Looking for related papers…
Contents