Consistent Low-Rank Approximation
Authors: David Woodruff
Samson Zhou
Venue: ICLR 2026 Poster (2026)
Keywords: low-rank approximation
online algorithms
consistency
recourse
Primary area: optimization

Abstract: We introduce and study the problem of consistent low-rank approximation, in which rows of an input matrix $\mathbf{A}\in\mathbb{R}^{n\times d}$ arrive sequentially and the goal is to provide a sequence of subspaces that well-approximate the optimal rank-$k$ approximation to the submatrix $\mathbf{A}^{(t)}$ that has arrived at each time $t$, while minimizing the recourse, i.e., the overall change in the sequence of solutions. We first show that when the goal is to achieve a low-rank cost within an additive $\varepsilon\cdot||\mathbf{A}^{(t)}||_F^2$ factor of the optimal cost, roughly $\mathcal{O}\left(\frac{k}{\varepsilon}\log(nd)\right)$ recourse is feasible. For the more challenging goal of achieving a relative $(1+\varepsilon)$-multiplicative approximation of the optimal rank-$k$ cost, we show that a simple upper bound in this setting is $\frac{k^2}{\varepsilon^2}\cdot\text{poly}\log(nd)$ recourse, which we further improve to $\frac{k^{3/2}}{\varepsilon^2}\cdot\text{poly}\log(nd)$ for integer-bounded matrices and $\frac{k}{\varepsilon^2}\cdot\text{poly}\log(nd)$ for data streams with polynomial online condition number. We also show that $\Omega\left(\frac{k}{\varepsilon}\log\frac{n}{k}\right)$ recourse is necessary for any algorithm that maintains a multiplicative $(1+\varepsilon)$-approximation to the optimal low-rank cost, even if the full input is known in advance. Finally, we perform a number of empirical evaluations to complement our theoretical guarantees, demonstrating the efficacy of our algorithms in practice.

Published as a conference paper at ICLR 2026
CONSISTENT LOW-RANK APPROXIMATION
David Woodruff Carnegie Mellon University
Samson Zhou Texas A&M University s samsonzhou@ggaale com
dwoodruff andrew. cmu. edu
ABSTRACT
We introduce and study the problem of consistent low-rank approximation, in which rows of an input matrix E IRaxd arrive sequentially and the goal is to provide sequence of subspaces that well-approximate the optimal rank-k approx- imation to the submatrix A (*) that has arrived at each time t, while minimizing the recourse, i.e., the overall change the sequence of solutions. We first show that when the goal to achieve low-rank cost within an additive è ||AA [1 factor of the optimal cost, roughly O ( log(nd)) recourse is feasible. For the more challenging goal of achieving relative (1 m)mulipplicaaiie approxima- tion of the optimal rank-k cost, we show that simple upper bound in this setting ka is
25 polly log(nd) recourse, which we further improve to = poly log(nd) for integer-bounded matrices and & poly log(nd) for data streams with polynomial online condition number. We also show that 2 @ log k recourse is necessary for any algorithm that maintains a multiplicative (1 + -aaaporoximttoon to the optimal low-rank cost, even if the full input is known in advance. Finally, we per- form a number of empirical evaluations to complement our theoretical guarantees, demonstrating the efficacy of our algorithms in practice.
ga/2
INTRODUCTION
Low-rank approximation is a fundamental technique that is frequently used in machine learning, data science, and statistics to identify important structural information from large datasets. Given an input matrix A Ra consisting of observations across d features, the goal of low-rank approximation is to decompose A into combination of l: independent latent variables called factors. We represent these factors by matrices U E Ra*k and V E R so that the product UV should be an "accurate" representation of the original dataset A. Formally, we want to minimize the quantity mi VeRexa L(UV A), where denotes any predetermined loss function chosen for its specific properties. Though there is variety of standard metries, such as subspace alignment angles or peak signal-to-none toiee ratio (PSNR), in this paper we focus on Frobenius loss, which is perhaps the most common loss function, due its connection with least squares regression. As result, the problem is equivalent to finding the right factor matrix V E exd of orthonormal rows to minimize the quantity A AV VI in which case the optimal left factor matrix is U AVT.
The rank parameter A is generally chosen based on the complexity of the underlying model chosen fit the data. The identification and subsequent utilization of the factors can often decrease the number of relevant features in an observation and thus simultaneously improve interpretability and decrease dimensionality. In particular, low-rank approximation facilitates using the factors U and V to approximately represent the original dataset A, thus using only (n + d)k parameters in the representation rather than the original nd entries of A. Thereafter, given a vector x E Rdd we can compute the matrix-vector product UVx as an approximation to Ax in time (n + dyk. By contrast, computing Ax requires nd time. As a result of these advantages and more, low-rank approximation is one of the most common tools, with applications in recommendation systems, mathematical modeling, predictive analytics, dimensionality reduction, computer vision, and natural language processing Chierichetti et al. (2017); Clarkson & Woodruff (2017); Cohen et al. (2017); 1);7); Musco & Woodruff (2017a;5) 70;);;;;; Bakshi & Woodruff (2018); Braverman et al. (2021a); Velingker et al. (2023); Musco & Sheth (2024); Song al. (2024); Kapralov et al. (2026).

---

Published as a conference paper at ICLR 2026
Data streams. The streaming model of computation has emerged as a popular setting for analyzing large evolving datasets, such as database logs generated from commercial transactions, financial markets, Internet of Things (IoT) devices, scientific observations, social network correspondences, or virtual traffic measurements. In the row-arrival model, each stream update provides an additional observation, i.e., additional matrix row a, Ied of the ultimate input A Raxd for low-rank approximation. Often, downstream decisions and policies must be determined with uncertainty about future inputs. That is, the input may be revealed in a data stream and practitioners may be required make irrevocable choices at time E (n], given only the dataset A (4) a o ... ar consisting of the first L data point observations. A prototypical example is the setting of online caching/paging algorithms (Fiat al., 1991; Irani, 1996), which must choose to keep or evict items in the cache at every time step. This generalizes to the k-server problem for penalties that are captured by metric spaces (Manasse et al., 1990; Bansal al., 2015; Bubeck et al., 2023).
Consistency. Although irrevocable decisions are theoretically interesting in the context of online algorithms, such a restriction may be overly stringent for many practical settings. Lattanzi & Vassil- vitskii (2017) 7) notes that in the earlier setting of caching and paging, a load balancer that receives on- line requests for assignment to different machines can simply reassign some of the past tasks to other machines to increase overall performance if necessary. Moreover, the ability of algorithms to adjust previous decisions based on updated information allows for a richer understanding of the structure of the underlying problem beyond the impossibility barriers of online algorithms. On the other hand, such adjustments have downstream ramifications to applications that rely on the decisions/policies resulting from the algorithm. Therefore, the related notions of consistency and recourse were de- fined to quantify the cumulative number of changes to the output solution of an algorithm over time. Low-recourse online algorithms have been well-studied for a number of problems (Gupta & Ku- mar, 2014; Gupta et al., 2014; Lacki et al., 2015; Gu et al., 2016; Megow et al., 2016; Gupta & al., 2023), while consistent clustering and facility location have re- cently received considerable attention (Lattanzi & Vassilvitskii, 2017; Cohen- Addad et al., 2019; Fichtenberger et al., 2021; Lacki i et al., 2023). In a standard scenario in feature engineering, low- rank approximation algorithms are used to select specific features or linear combinations of features, on which models are trained. Thus, large consistency costs correspond to expensive retrainings of whole large-scale machine learning systems (Lattanzi & Vassilvitskii, 2017), due to different sets of features being passed to the learner.
Levin, 2020; Bhattacharya
Building on the notion of consistency, we formalize the problem of consistent low-rank approxima- tion, which captures the need for online algorithms that adapt to evolving data while keeping their outputs stable for downstream use. As discussed above, low-rank approximation is widely used for feature engineering: the factors produced define the feature subspace on which downstream models trained. In dynamic settings, high recourse can cause these features to change abruptly even under minor updates, triggering frequent and costly retraining of large-scale models (Lattanzi & Vassilvitskii, 2017). Consistent, low-recourse LRA algorithms maintain feature stability over time, reducing retraining costs and improving reliability.
The importance of stability extends across many practical domains. In biometries, consistent low- dimensional representations of fingerprints or iris patterns are crucial for maintaining reliable iden- tification (Jain et al., 2004). In image processing, tasks such as object detection, handwriting recog- nition, and facial recognition depend on derived features that should not fluctuate unpredictably as new data arrives (Nixon& & Aguado, 2012). In data compression and signal processing, stable re- duced representations preserve essential structure while controlling noise (Witten & Frank, 2002; Proakis, 2007). In text mining and information retrieval, numerical features such as TF-IDF vectors or embeddings must remain coherent to maintain the quality of search and classification (Aggar- wal & Aggarwal, 2015; Schütze et al., 2008). Even in large-scale data curation for foundation models-when clustering, constrained form of low-rank approximation, is used to deduplicate hata-high recourse leads to unstable representative sets and repeated retraining of models (Lacki ① et al., 2023).
Across these settings, the underlying principle is consistent: downstream systems rely not only on the quality of the approximation but also on the stability of the feature representations over time. By explicitly accounting for this need, consistent low-rank approximation provides solutions that evolve smoothly while maintaining strong accuracy guarantees, delivering both theoretical insight and concrete practical benefits in dynamic, real-world pipelines.
2

---

Published as a conference paper at ICLR 2026
1.1 OUR CONTRIBUTIONS
In this paper, we initiate the study of consistent low-rank approximation.
Formal model. Given an accuracy parameter 0, our goal is to provide (1 + E) appprxximmaionnn to low-rank approximation at all times. We assume the input is a matrix A E R whose rows a....., an arrive sequentially, so that at each time t, the algorithm only has access to A (4), the first I rows of A. That is, the goal of the algorithm is firstly to output a set V(t) E R of k factors at each time E [ni], that
AA - A (V( T V - (1 +)) OPT,
where OPT, is the cost of the optimal low-rank approximation at time t. OPT, minve || (t) V VI In other words, we want the low-rank cost induced by the factor v(i) returned by the algorithm to closely capture the optimal low-rank approximation. Secondly, would like the sequence v ..... v(n) of factors to change minimally over time. Specifically, the goal of the algorithm is to minimize Dn= Recourse(V (t), v((-1)), where Recourse (R, T) || - P is the squared subspace distance between the orthogonal projection matrices PR. P of the two subspaces.
We remark on our choice of the cost function Recourse RR, T) for factors R and T. At first glance, a natural setting of the cost function may be the number of vectors that are different between R. and T, since in some sense it captures the change between R and T. However, it should be observed that even if there is a unique rank k subspace V that minimizes the low-rank approximation cost ||A AV VII there may be many representations of V, up any arbitrary rotation of the basis vectors within the subspace. Thus, a cost function sensitive to the choice of basis vectors may not be appropriate because a large change in the change of basis vectors may not result in any change in the resulting projection AV V. This implies that a reasonable cost function should capture the difference in the spaces spanned by the subspaces R and T. For example, the dimension of the subspace of T that is orthogonal to R would be an appropriate quantity. However, it should be small perturbation of R. for example if
noted that this quantity still punishes subspace T that R is the elementary vector (0, 1) and T is the vector (e, v1- E²) for arbitrarily small e. A more robust quantity would be continuous analogue of the dimension, which is the squared mass of the projection of T away from R; this quantity corresponds exactly to our cost function Recourse. Thus, we believe that our choice of the consistency cost function is quite natural.
We note that we can further assume that the input matrix A has integer entries bounded in magnitude by some parameter M. We remark that this assumption is standard in numerical linear algebra because in general it difficult to represent real numbers up to arbitrary precision in the input of the algorithm. Instead, for inputs that are rational, after appropriate scaling each entry of the input matrix can be written as an integer. Thus, this standard assumption can model the number bits used to encode each entry of the matrix, without loss of generality.
Theoretical results. We first note that the optimal low-rank approximation can completely change at every step, in the sense that the optimal subspace (t-1)) at time t may still have dimension k after being projected onto the optimal subspace V(0, Thus, to achieve optimality, may be possible that ((nk) recourse could be necessary, i.e., by recomputing the best & factors after the arrival of each of the n rows. Nevertheless. on the positive side, we first show sublinear recourse can be achieved if the goal is to simply achieve an additive s approximation cost at all times.
|A (+) [|3 additive error to the low-rank
Theorem 1.1. Suppose A E Zaxd is an integer matrix with rank > is and entries bounded in magnitude by M and let A (1)) denote the first rows of A, for any E [n]. There exists an algorithm that achieves e | [ additive approximation to the cost of the optimal low-rank approximation A at all times and achieves recourse O log(ndM)).
We remark that the algorithm corresponding to Theorem 1.1 uses kd polylog(ndd)) bits of space and d poly (k: J. log(ndM)) amortized update time. Since the squared Frobenius norm is an upper bound on the optimal low-rank approximation cost, achieving additive e ||A (*) I2 error to the optimal cost is significantly easier than achieving relative + e)-multipiccative error, particularly
3

---

Published as a conference paper at ICLR 2026
in the case where the top singular vectors correspond large singular values. In fact, even achieve recourse linear in & if the online condition number of the stream is at most poly(n):
Theorem 1.2. Given a stream with online condition number poly (T)) there exists an algorithm that achieves a (1 E) approximmatio for low-rank approximation, and uses recourse O ( log" n).
We remark that for streams with online condition number poly(n), actually show a stronger result in Lemma 2.1. In particular, we show that the optimal rank-k subspace changes by only a constant amount after rank-one perturbations corresponding to single-entry changes, row modifications, row insertions, and row deletions. Thus this result implies Theorem 1.2 using standard techniques for reducing the "effective" stream length and in fact, also immediately gives an algorithm that maintains the optimal rank-k k approximation under any sequence of such updates while incurring only O (n) total recourse over a stream of n operations. Hence, our approach can handle explicit distributional shifts arising in iisertion-deletion streams; extending this ability to handle implicit deletions such as in the sliding window model (Datar et al., 2002; Crouch et al., 2013; Braverman et al., 202 bb; 2018; 2020; Woodruff & Zhou, 2021; Borassi et al., 2020; Epasto et al., 2022; Jayaram et al., 2022; Blocki et al., 2023; Woodruff & Yasuda, 2023; Woodruff et al., 2023; Cohen-Addad et al., 2025; Braverman al., 2026; Nagawanshi et al., 2026) is a natural direction for future work.
For standard matrices with integer entries bounded by poly(n), however, the assumption that the online condition number is bounded by poly(n) may not hold. For example, it is known that there exist integer matrices with dimension n. x d but optimal low-rank cost as small as (xp(-((k)) To that end, we first observe that simple application of a result by Braverman al. (2020) can be used to achieve recourse - polylog(ndM) while maintaining a (1++) ([+=)-mulillliattii
approximation at all times. Indeed, for constant e, roughly k- polylog( Mn rows can be sampled through process known as online ridge-leverage score sampling, to preserve the low-rank approximation at all times. Then for quadratic recourse, suffices to recompute the top right k singular vectors for the sampled submatrix each time a new row is sampled. A natural question is whether (2(k) recourse is necessary for each step, i.e., whether recomputing the top right h singular vectors is necessary. We show this is not the case, and that overall the recourse can be made sub-quadratic.
Theorem 1.3. Suppose E Znxd an integer matrix with entries bounded magnitude by M. There exists an algorithm that achieves (1 + e)approoximation to the cost of the optimal low-rank approximation at all times and achieves recourse 63/2 polylog(ndM).
We again remark that the algorithm corresponding to Theorem 1.3 uses kd polylog(ndM) bits of space and d' poly (k. 2. log(MdM) amortized update time. Finally, show that Z ( log }) recourse is necessary for any multiplicative (1 + e)-approximation algorithm for low-rank approxi- mation, even if the full input is known in advance.
Theorem 1.4. For any parameter e > lugn there exists a sequence of rows XI,...,X, Xy E Rdd such that any algorithum that produces (1 (1++e) approxxiiatiin to the cost of the optimal low-rank approximation at all times must have consistency cost S2 (# log k
Empirical evaluations. We complement our theoretical results with a number of empirical evalua- tions in Section 4. Our results show that although formal guarantees provide worst-case analy- sis of the approximation cost of the low-rank solution output by our algorithm, the performance can be even (much) better in practice. Importantly, our results show that algorithms for online low-rank approximation such as Frequent Directions (Ghashami et al., 2016) do not achieve good recourse, motivating the study of algorithms specifically designed for consistent low-rank approximation.
Organization of the paper. We give the linear recourse algorithms in Section 2 and conduct em- pirical evaluations in Section 4 and Appendix G. We give our result for integer-valued matrices in Section 3. We defer all proofs to the full appendix, and specifically the lower bound to Appendix D. The reader may also find helpful to consult Appendix A for standard notation and additional preliminaries used in our paper.
1.2 RELATED WORK
In this section, we briefly describe a number of existing techniques in closely related models and provide intuition why they do not suffice for our setting.
4

---

Published as a conference paper at ICLR 2026
Frequent directions and online ridge leverage score sampling. The most natural approach would be to apply existing algorithms from the streaming literature for low-rank approximation. The two most related works the deterministic Frequent Directions work by Ghashami et al. (2016) and the (online) ridge leverage score sampling procedure popularized by Cohen et al. (2017); Braverman al. (2020). Both procedures maintain small number of rows that capture the "important" direc- tions of the matrix at all times. Hence to report a near-optimal rank-k approximation at each time, these algorithms simply return the top k right singular vectors of the singular value decomposition of the matrix stored by each algorithm. However, one could easily envision a situation in which the k-th and (k+ + 1)-th largest singular vectors repeatedly alternate, incurring recourse each step. For example, suppose k- = 1 and at all times 2/ for integral / > 0, the top singular vectors are (21, 0) and (0, 21- - 8), but at all times 2/ + 1 for integral 2 0, the top singular vectors are (2/ + 1 s, 0) and (0, 21 + 1). Then at all times 2/, the best rank-k solution for k = 1 would be the elementary vector e1 while at all times 2t + 1, the best rank-k solution would be the elementary vector eg- These algorithms would incur recourse n, whereas even algorithm that never changes the initial vector 22 would incur recourse O. Thus, these algorithms seem to fail catastrophically, i.e., not even provide a poly voly(n)-mulinn -ultipliicative approximation to the recourse, even for simple inputs.
One may observe that our goal is to only upper bound the total recourse, rather than to achieve multiplicative approximation to the recourse. Indeed for this purpose, the online ridge leverage sampling technique provides some gain. In particular, Braverman et al. (2020) showed that over the entirety of the stream, at most A polylog (n, d, 2) rows will be sampled into the sketch matrix in total, and moreover the sketch matrix will accurately capture the residual for the projection onto any subspace of dimension k. Thus to achieve O (k²) recourse, it suffices to simply recompute the top-k singular vectors each time new row is sampled by the online ridge leverage sampling procedure.
Singular value decomposition. Note that the previous example also shows that more generally, does not suffice to simply output the top-k right singular vectors of the singular value decomposition (SVD). However, one might hope that it suffices to replace just a single direction in the SVD each time a row is sampled into the sketch matrix by online ridge leverage score sampling. Unfortu- nately, it seems possible that an approximately optimal solution from a previous step could require all factors to be replaced by the arrival of a single row. Suppose for example, that the factor ((I) consisting of the elementary vectors ek+1:-..., E2g achieves the same loss the factor ( consist- ing of the elementary vectors ei...., ej. Now if the next row is non-zero exactly in the coordinates 1, 1,...,k, k. then the top k space could change entirely, from (l) to V While this worst-case input unavoidable, we show this can only happen small number of times. It is more problematic when only one of these factors drastically change, while the other k - 1 factors only change by a little, but we still output k completely new factors. Our algorithm avoids this by carefully choosing the factors to replace based on casework on the corresponding singular values.
2 SIMPLE ALGORITHMS WITH OPTIMAL RECOURSE
In this section, we briefly describe two simple algorithms that achieve recourse linear in k.
Additive error. The first algorithm roughly O & log n)) recourse when the goal is to maintain an additive 8 ||A (01 error at all times E [ra]. where A (4) the rows of matrix A that have arrived at time t. We simply track the squared Frobenius norm of the matrix A (9) at all times. For each time the squared Frobenius norm has increased by factor of (1 + E). then we recompute the singular value decomposition of (+) and choose (it) to be the top right singular vectors of A For all other times, we maintain the same set of factors.
The main intuition is that each time we reset V(t), we find the optimal solution at time t. Over the next few steps after t, our solution will degrade, but the most it can degrade by is the squared Frobenius norm of the submatrix formed by the incoming rows. Thus as long this quantity is less than an e-fraction of the squared Frobenius norm of the entire matrix, then our correctness guarantee will hold. On the other hand, such a guarantee must hold as long as the squared Frobenius norm has not increased by a (1 + m)-multiplicatiie factor. Thus we incur recourse k for each of the O ( log(nd))) times the matrix can have its squared Frobenius norm increase by (1 + =) multiplicatively. We give our algorithm in full in Algorithm 4 in Appendix E.
5

---

Published as a conference paper at ICLR 2026
Bounded online condition number. We next show that the optimal rank k subspace incurs at most constant recourse under rank one perturbations. In particular, it suffices to consider the case where single row is added to the matrix:
R such that A() is A with the row A appended. Let Vi-1 and Vi be the optimal rank-k subspaces (the span of the top lo right singular vectors) of A 1)-1) and A!),, respectively. Then Recourse V Vi) 8.
Lemma 2.1. Let A (t-1) E (R(t-1)xd and A )
Note that whenever a single entry of matrix is changed, any row of matrix is changed, new row of matrix added, or an existing row of matrix is deleted, these all correspond to rank one perturbations of the matrix. Thus, immediately have the following corollary:
Theorem 2.2. There exists algorithm that maintains the optimal rank-k approximation of matrix under any sequence of rank-one updates, including entry modifications, now modifications, row insertions, row deletions, and incurs total recourse O (m. on stream of n updates. Moreover, if each row has dimension d, then the update time is O ((n + d)k + K²).
Given the statement in Lemma 2.1, we immediately obtain algorithm with O (n) recourse in the row-arrival model for a stream of length n. Because n recourse is too large, we use the following standard approach to decrease the effective number of rows in the matrix.
Definition 2.3 (Projection-cost preserving sketch). Given matrix A E Band, a matrix M E Rmxd a (1 + e) projection-cos preserving sketch of for all projection matrices P E R
(1 - (1=s)]AA AP < || MP < (1 + 8) A A
Intuitively, a projection-cost preserving sketch a sketch matrix that approximately captures the residual mass after projecting away any rank i subspace. The following theorem shows that projection-con cost preserving sketch can be acquired via online ridge leverage sampling.
Theorem 2.4 (Theorem 3.1 Braverman al. (2020)), Given an accuracy parametere > O, a rank parameter k > O, and a matrix A a o. .on E R whose rows arrive sequentially in stream with condition number there exists an algorithm that outputs matrix M with ( ( log log" k) rescaled rows of A such that
(1==)llA A AM-M(ulf-- S [)++) A
so that with high probability, M is rank k projection-cost preservation of A.
In particular, if the online condition number of the stream is upper bounded by poly(n). then Theo- rem 2.4 states that online ridge leverage sampling achieves an online coreset of size O (# log" n). By applying Lemma 2.1, it follows that simply maintaining the optimal rank-k subspace for the online coreset at all times, we have Theorem 1.2.
ALGORITHM FOR RELATIVE ERROR
In this section, we give our algorithm for (1 + e) multipliicatie relative error at all times in the stream. Let t E [n], let x, E (-A..... A 1, A] and let X; = X o o... Xx, For each X, E xdd we compute a low-rank approximation U, V, of X,, where U, E Rex and V, E Rexd are the factors of X,. We abuse notation and write V, as set Vú of l points in Rd Note that the quantity Ee V. V.-l is an upper bound on the recourse or the consistency cost. Thus this section, we interchangeably refer to this quantity as the recourse or the consistency cost, can lower bound this sharper quantity.
First, we recall an important property about the optimal solution for our formulation of low-rank approximation, i.c., with Frobenius loss.
theorem). (Eckart & Young, 1936; Mirsky, 1960) Let A Raxd with rank have singular value decomposition A = UEV for U E Raxr Σ E Trx V E ig and singular values o (A) 2 (A) 2 2 aa(A). Let X be the top k right singular vectors of A, i.e. the top k rows of V, breaking ties arbitrarily. Then optimal rank k approximation of A is AX and the cost is A AX XI E (A).
Theorem 3.1 (Eckart- (Eekart-Young-No

---

Published as a conference paper at ICLR 2026
As corollary to Theorem 3.1, have that an algorithmic procedure to compute optimal rank approximation is just to take the top right singular vectors of A, c.f., procedure RECLUSTER(A. k) in Algorithm 1, though faster methods for approximate SVD can also be used.
Corollary 3.2. There exists an algorithm RECLUSTER( (A. k) that ouppus a set of orthonormal rows X that produces the optimal rank l approximation to A.
Algorithm RECLUSTER(A A, k), i.e., Truncated SVD
Input: Matrix A E Raxd rank parameter k:
Output: Top & right singular vectors of A
1: Let r be the rank of A
2: Let U E _ Σ E Rrxr, V Rexd be the singular value decomposition of A UΣV
3: Return the first min k) rows V
Our algorithm performs casework the contribution of the bottom vk singular values of the top k. the contribution small, the corresponding singular vectors can be replaced without substantially increasing the erro. Thus, each time vectors with the new row. On the other hand, if the contribution is large, it means that the optimal solution cannot be projected away too much from these directions, or else the optimal low-rank approximation cost will also significantly increase. Thus we can simply choose the optimal set of top right & singular vectors each time, because there will be substantial overlap between the new subspace and the old subspace. We give our algorithm in full in Algorithm 2.
arrives, simply replace one of the bottom singular
Algorithm Relative-error algorithm for low-rank approximation with low recourse
Input: Rows ..,...;; a, of input matrix A E Raxd with integer entries bounded in magnitude by M
Output: (1 + appprooximmtionnn the cost of the optimal low-rank approximation all times
1: for each row a, do
2:
OPT + Σd 1 (Ai)
3: HEAVY - TRUE, C 0
4: if OPT 2 (1 + 9) or (c VI: and HEAVY = FALSE) or (c k and HEAVY TRUE)
then
5:
C + OPT,ct=
6:
V - RECLUSTER(A
7:
if Lizk- EK VE (A(A()) ()) )9)2 2 C' then
8:
HEAVY + TRUE
9:
else
10:
HEAVY + FALSE
end if
12:
else
HEAVY FALSE then Let v be the unit vector in V that minimizes (+) where was the most recent time RECLUSTER was called
14:
15:
Replace with Ta a, in V
plgnore all zero rows
16:
C- c ++++1 1 else if HEAVY TRUE then A (
17:
18:
if (1)
2 (1 {) OPT then
19:
V + RECLUSTER( A (0) A)
20:
e e c+1
21:
end
22:
end if
23:
end if
24:
Return V
25:
end for

---

Published as a conference paper at ICLR 2026
Correctness. For the purposes of discussion, say that an epoch is the set of times during which the optimal low-rank approximation cost has not increased by a multiplicative (1 + E) apprroxximtaoonn We first show the correctness of our algorithm across the times t during epochs in which HEAVY is set to FALSE. That is, we show that our algorithm maintains a (1 + =))mltipplicativee approximation to the optimal low-rank approximation cost across all times in an epoch where the bottom vh singular values of the top right singular values do not contribute significant mass.
Lemma 3.3. Consider a time during which e. is reset to O. Suppose HEAVY is set to FALSE at time and e is not reset to O within the next steps, for r S Vk. Let V be the output of V at time Then ( provides a (1 + 5) approximation to the cost of the optimal low-rank approximation of A (t) for all t E rr.
Next, we show the correctness of our algorithm across the times during epochs in which HEAVY is set to TRUE. That is, we show that our algorithm maintains a (1 + E) e)-muttiplicative approximation to the optimal low-rank approximation cost across all times t in an epoch where the bottom vk singular values of the top right singular values do contribute significant mass.
Lemma 3.4. Consider a time during which HEAVY is set to TRUE. Let V(O) be the oulput of V at time t. Then V provides a (1 + 5 -approximation to the cost of the optimal low-rank approximation of (
Correctness at all times now follows from Lemma 3.3 and Lemma 3.4:
Lemma 3.5. At all times t E [rl], Algorithm 2 provides (1 (1+} & aaproxxmmation to the cost of the optimal low-rank approximation of (t).
Recourse. We first bound the recourse if the bottom vie singular values of the top right singular values do not contribute significant mass. Lemma 3.6. Suppose HEAVY is set to FALSE at time s and e is reset to 0 at time s. If not reset to within the next steps. for S Vkc then Dith+1 Recourse (V(s), V(s-1)) Sr.
At this point, we remark subtlety in the analysis that is easily overlooked. Our general strategy to show that each time the cost of the optimal low-rank approximation doubles, we should incur recourse O (K.15). One might then expect that because the matrix contains integer entries bounded by poly(n), then the cost of the optimal low-rank approximation can only double O (log n) times, since it can be at most poly (n)).
Unfortunately, there exist constructions of anti-Hadamard integer matrices with dimension n x d but optimal low-rank cost as small as ())))))())). Hence, the optimal cost can double (k) times, thereby incurring total recourse O (k2.), which is undesirably large. Instead, we show that when the optimal low-rank cost is exponentially small, then the rank of the matrix must also be quite small, meaning that the recourse of our algorithm cannot be as large as in the full-rank case. To that end, we require a structural property, c.f., Lemma F.2 that describes the cost of the optimal low-rank approximation, and parameterized handle general matrices with rank r > k. This is to handle the case where the cost of the optimal low-rank approximation may be exponentially small in k. As a result, we have the following upper bound on the total recourse across all epochs when the bottom VTe singular values of the top & do not contribute significant mass.
Lemma 3.7. Suppose HEAVY is set to TRUE time and e is not reset to 0 within the next steps, for S k. Then Dist+1 (ecourse(VV()) v(t-l))<r
tt
We analyze the total recourse during times when we reset the counter e because the cost of the optimal low-rank approximation has doubled. Finally, it remains to bound the total recourse at times when we transition from one epoch to another. Specifically, we bound the recourse at times t where the optimal low-rank approximation cost has increased by multiplicative (1 + -)-appooxinttion since the beginning of the previous epoch.
Lemma 3.8. Let T be the set of times at which e is set to O. Then Ever Recourse (VO), v(t-1)) <
O (nvk l + à log? (ndM).
Using Lemma 3.6, Lemma 3.7, and Lemma 3.8, we then bound the total recourse of our algorithm.
8

---

Published as a conference paper at ICLR 2026
Lemma 3.9.
The total recourse of Algorithm 2 input matrix A Raxd with integer entries bounded in magnitude by M is O nvk + f log" (ndM))
Using Lemma 3.5 and Lemma 3.9, we can provide the formal guarantees of our subroutine.
Lemma 3.10. Given an input matrix A TRaxd with integer entries bounded in magnitude by M, Algorithm achieves a (1 5) aaprrxximation to the cost of the optimal low-rank approximation and achieves recourse O (nvk + _ loooo (ndM))
k3/2
Algorithm 3 Relative-error algorithm for low-rank approximation with recourse polylog(ndM)
Input: Rows a1...... a, of input matrix A Raxd d with integer entries magnitude at most M Output: (1 approximmaioo to the cost of the optimal low-rank approximation at all times for each row a, do
2: Sample a, with online ridge leverage score
D Theorem 2.4
3: Run Algorithm the stream induced by the sampled rows
4:
end for
To reduce the number of rows in the input, we again apply Theorem 2.4, which, combined with Lemma 3.10, gives our main result Theorem 1.3 for Algorithm Finally, we remark that since input sparsity algorithms for approx- imations of the sampling probabilities (Cohen et al., 2017), then Algorithm 3 can be implemented used kd polylog(nd.)) bits of space and d poly (k: 1, log(ndM) polgdd.
Theorem 2.4 samples O (+x log log" x) rows and there
amortized update time.
EMPIRICAL EVALUATIONS
We describe empirical evaluations large-scale real-world dataset, comparing the quality of the solution of our algorithm to the quality of the optimal low-rank approximation solution. We dis- cuss number of additional experiments both synthetic and real-world datasets in Appendix G. All experiments were conducted utilizing Python version 3.10.4 on 64-bit operating system run- ning on an AMD Ryzen 5700U CPU. The system was equipped with 8GB of RAM and featured 8 cores, each operating at a base clock speed of 1.80 GHz. The code is publicly accessible at https: / / thub. c samsonzhous cons stent- LRA.
h
(1
E)
Median
Std. Dev.
Mean
1.1
1.000
0.0000
1.0000
1.000
0.0000
1.0000
25
1.0000
0.0367
1.0016
10
1.0000
2.4463
1.598
100
1.1907
51.9353
7.8882
Table 1: Median, standard deviation, and mean for ratios of cost across various values of accuracy parameters for landmark dataset, between 150 and 5000 updates
Experimental setup. In this section, focus on our evaluations Algorithm 4 the Landmark dataset from the SuiteSparse Matrix Collection (Davis & Hu, 2011), which is commonly used in benchmark comparison for low-rank approximation, e.g., (Ban et al., 2019). The dataset consists of a total of 71952 rows with d = 2704 features. As our theoretical results prove that our algorithm has a small amount of recourse, we first compare the cost of the solution output by Algorithm with the cost of the optimal low-rank approximation. However, determining the optimal cost over each time computationally expensive and serves as the main bottleneck. Specifically, for a stream of length n, the baseline requires n O (n²)) Q(n²) runtime for RS d, where w ~ 2.37 is the exponent for matrix multiplication (Alman et al., 2025). Thus we consider the first n = 5000 rows for our every single prefix matrix of size x d with < n. In particular, we computed in the runtimes and ratios of the two costs for (1 8) (1.1, 2.5, 5, 10, 100) in Figure 2 with central statistics in Table 1,
data stream, the goal to perform low-rank approximation
k 25 across

---

Published as a conference paper at ICLR 2026
Total recourse landanakkk daraset
Total recolise for landmark dataset
1752
30
1300
C-10
C-100
3023 0001100011
10
300
100
1200
2020
3020
4000
3020
600
000
1200
Number of rowe
Rumber ofrows
Recourse comparisons
Recourse comparisons
Fig. 1: Recourse comparisons for k: = c= (1 (1 + E {1.1, 2.5,5, 10, 100]
though Algorithm 4 only guarantees additive error, rather than multiplicative error. Finally, compared the recourse of our algorithms in Figure I, along with FREQUENTDIRECTION, labeled FD, standard algorithm for online low-rank approximation (Ghashami et al., 2016).
Results and discussion. Our results show a strong separation in the quality of online low-rank approximations such Frequent Directions and algorithms, which were specifically designed to achieve low recourse. Namely, for n = 5000, Frequent Directions has achieved recourse 121904 while our algorithms range from results show that the approximation guarantees of our algorithms are actually quite good in practice, especially the number of rows increases; we believe the large variance in Figure 2b due the optimal low-rank approximation cost being quite small compared to the additive Frobenius error Thus it seems our empirical evaluations provide compelling evidence that our algorithms achieve significantly better recourse than existing algorithms for online low-rank approximation; we provide a number of additional experiments in Appendix G.
100 to 300, more than factor of 400X. Moreover, our
Total untinre kedroat Adtest
Instrencdrtteet
2009
000
(a) Runtime comparisons
(b) Approximation comparisons
(c) Approximations comparisons
Fig. 2: Runtime and approximations landmark dataset, for k 25, +1+ 2..1,25, 5, 10, 100}
ACKNOWLEDGMENTS
David P. Woodruff is supported in part Office Naval Research award number N000142112647, and Simons Investigator Award. Samson Zhou is supported in part by NSF CCF-2335411. Samson Zhou gratefully acknowledges funding provided by the Oak Ridge Associated Universities (ORAU) Ralph E. Powe Junior Faculty Enhancement Award.
REFERENCES
Charu C Aggarwal and Charu C Aggarwal. Mining text data. Springer, 2015. 2
10

---

Published as a conference paper at ICLR 2026
Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. More asymmetry yields faster matrix multiplication. In Proceedings of the 2025 Annual ACM- SIAM Symposium on Discrete Algorithms, SODA, pp.
2025. 9
Ainesh Bakshi and David P. Woodruff. Sublinear time low-rank approximation of distance matri- ces. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems, NeurIPS, 2018.
Frank Ban, David P. Woodruff, and Qiuyi (Richard) Zhang. Regularized weighted low rank ap- proximation. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS, pp. 4061-4071, 2019.
Nikhil Bansal, Niv Buchbinder, Aleksander Madry, and Joseph Naor. A palylogaithmiic-compttiiie algorithm for the k-server problem. J. ACM, 62(5):40:1-44:44, 2015,. 2
Rajen Bhatt and Abhinav Dhall. Skin Segmentation. UCI Machine Learning Repository, 2012.
DOI: https:///bi.orr//1.2444////////
26
Sayan Bhattacharya, Niv Buchbinder, Roie Levin, and Thatchaphol Saranurak. Chasing positive bodies. In 64th IEEE Anmual Symposium on Foundations of Computer Science, FOCS, pp. 1694 1714, 2023. 2
Sayan Bhattacharya, Martín Costa, Naveen Garg, Silvio Lattanzi, and Nikos Parotsidis. Fully dy- namic k-clustering with fast update time and small recourse. In 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 216-227, 2024. 18
Jeremiah Blocki, Seunghoon Lee, Tamalika Mukherjee, and Samson Zhou. Differentially private 1z- heavy hitters in the sliding window model. In The Eleventh International Conference on Learning Representations, ICLR, 2023. 4
Michele Borassi, Alessandro Epasto, Silvio Lattanzi, Sergei Vassilvitskii, and Morteza Zadimoghad- dam. Sliding window algorithms for k-clustering problems. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurIPS, 2020. 4, 26
Matthew Brand. Fast low-rank modifications of the thin singular value decomposition. Linear algebra and its applications, 415(1):20-33) 2006. 21
Vladimir Braverman, Elena Grigorescu, Harry Lang. David P. Woodruff, and Samson Zhou. Nearly optimal distinct elements and heavy hitters on sliding windows. In Approximation, Random- ization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM pp- 7:1-7:22, 2018. 4
Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P. Woodruff, and Samson Zhou. Near optimal linear algebra in the online and sliding window models. In 61st IEEE Annual Symposium Foundations of Computer Science, FOCS, pp. 517-528, 2020. 4, 5, 6,
Vladimir Braverman, Avinatan Hassidim, Yossi Matias, Mariano Schain, Sandeep Silwal, and Sam- son Zhou. Adversarial robustness of streaming algorithms through importance sampling. In Ad- vances Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems, NeurIPS, 2021a.
Vladimir Braverman, Viska Wei, and Samson Zhou. Symmetric norm estimation and regression sliding windows. In Computing and Combinatorics 27th International Conference, COCOON, Proceedings, 2021b. 4
Vladimir Braverman, Sumegha Garg, Chen Wang. David P. Woodruff, and Samson Zhou. Online learning with limited information in the sliding window model. In Proceedings of the ACM-SIAM Symposium Discrete Algorithmss, SODA, 2026. 4
Sébastien Bubeck, Christian Coester, and Yuval Rabani. The randomized k-server conjecture is false! In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC, pp- 581-594 2023. 2
11

---

Published as a conference paper at ICLR 2026
T.-H. Hubert Chan, Shaofeng H.-C. Jiang, Tianyi Wu, and Mengshi Zhao. Online clustering with nearly optimal consistency. In The Thirteenth International Conference on Learning Representa- tions, ICLR, 2025. 18
Flavio Chierichetti, Sreenivas Gollapudi, Ravi Kumar, Silvio Lattanzi, Rina Panigrahy, and David P. Woodruff. Algorithms for Ep low-rank approximation. In Proceedings of the 34th International Conference on Machine Learning, ICML, pp. 806-814, 2017.
Kenneth L. Clarkson and David P. Woodruff. Numerical linear algebra in the streaming model. In Proceedings of the 41st Anmual ACM Symposium on Theory of Computing, STOC, pp. 205-214, 2009. 17
Kenneth Clarkson and David Woodruff. Low-rank PSD) approximation in input-sparsity time. In Proceedings of the Twenty-Eighth Anmual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 2061-2072 2017.
Michael B. Cohen, Cameron Musco, and Christopher Musco. Input sparsity time low-rank ap- proximation via ridge leverage score sampling. In Proceedings of the Eivent-EEgghtt Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 1758-1777, 2017. 5,5,9
Vincent Cohen-Addad, Niklas Hjuler, Nikos Parotsidis, David Saulpic, and Chris Schwiegelshohn. Fully dynamic consistent facility location. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems, NeurlPS, pp- 3250-3260, 2019. 2
Vincent Cohen-Addad, Silvio Lattanzi, Andreas Maggiori, and Nikos Parotsidis. Online and consis- tent correlation clustering. In International Conference on Machine Learning, ICMI, pp. 4157- 4179, 2022. 18
Vincent Cohen-Addate Shaofeng H.-C. Jiang, Qiaoyuan Yang, Yubo Zhang, and Samson Zhou. Fair clustering in the sliding window model. In The Thirteenth International Conference on Learning Representations, ICLR, 2025.
Michael Crouch, Andrew McGregor, and Daniel M. Stubbs. Dynamic graphs in the sliding- window model. In Algorithms- ESA 21st Annual European Symposium. Proceedings, pp. 337- 348, 2013.
Mayur Datar, Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Maintaining stream statistics over sliding windows. SIAM J. Comput,, 31(6):1794-188) 1813, 2002. 4
Timothy A Davis and Yifan Hu. The university of florida sparse matrix collection. ACM Transac- fions on Mathematical Software (TOMS), 38(1):1-25, 2011.
Paul Duetting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, and Morteza Zadimoghad- dam. Consistent submodular maximization. In Forty-first International Conference on Machine
Learning, ICML.. OpenReview.net, 2024. 18
Paul Dütting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, Ola Svensson, and Morteza Zadimoghaddam. The cost of consistency: Submodular maximization with constant recourse. CoRR, abs/2412.02492,, 2024. 18
Carl Eckart and Gale Young. The approximation of one matrix by another of lower rank. Psychome- trika, 1(3):211-22 11881,, 1936.
Alessandro Epasto, Mohammad Mahdian, Vahab S. Mirrokni, and Peilin Zhong. Improved sliding window algorithms for clustering and coverage via bucketing-based sketches. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 3005-3042, 2022.
Alessandro Epasto. Vahab Mirrokni, Shyam Narayanan, and Peilin Zhong. k-means clustering with distance-based privacy. In Advances in Neural Information Processing Systems 36: Annual Con- ference on Neural Information Processing Systems, NeurIPS, 2023. 26
Amos Fiat, Richard M. Karp, Michael Luby, Lyle A. McGeoch, Daniel Dominic Sleator, and Neal E. Young. Competitive paging algorithms. J. Algorithmss 12(4))685-69) 1991. 2
12

---

Published as a conference paper at ICLR 2026
Hendrik Fichtenberger, Silvio Lattanzi, Ashkan Norouzi-Fant Fard, and Ola Svensson. Consistent k- clustering for general metrics. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 2660-2678, 2021. 2, 17, 18
Steve Fisk. A very short proof of cauchy's interlace theorem for eigenvalues of hermitian matrices. arXiv preprint math/05024008, 2005. 15
Sebastian Forster and Antonis Skarlatos. Dynamic consistent k-center clustering with optimal re- course. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 212-254, 2025. 18
Mina Ghashami, Edo Liberty, Jeff M. Phillips, and David P. Woodruff. Frequent directions: Simple and deterministic matrix sketching, SIAM J. Comput., 45(5):1762-1792, 2016. 4, 5, 10
Albert Gu, Anupam Gupta, and Amit Kumar. The power of deferral: Maintaining constant- competitive steiner tree online. SIAM Comput., 45(1):1-28, 2016.
Xiangyu Guo, Janardhan Kulkarni, Shi Li, and Jiayi Xian. Consistent k-median: Simpler, better and robust. In The 24th International Conference Artificial Intelligence and Statistics, AISTATS, pp. 1135-1143, 2021. 18
Anupam Gupta and Amit Kumar. Online steiner tree with deletions. In Proceedings of the Twenty- Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 455-467, 2014. 2
Anupam Gupta and Roie Levin. Fully-dynamic submodular cover with bounded recourse. In 61 IEEE Annual Symposium Foundations of Computer Science, FOCS, pp. 1147-1157, 2020., 2
Anupam Gupta, Amit Kumar, and Cliff Stein. Maintaining assignments online: Matching, schedul- ing, and flows. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 468-479, 2014. 2
Hwang. Cauchy's interlace theorem for eigenvalues of hermitian matrices. The American mathematical monthly, 11 111(2):157-159, 2004. 15
Sandy Irani. Competitive analysis of paging. In Online Algorithms. The State of the Art, volume 1442 of Lecture Notes in Computer Science, pp. 52-73. Springer, 1996.
Mohammad Reza Karimi Jaghargh, Andreas Krause, Silvio Lattanzi, and Sergei Vassilvitskii. Con- sistent online optimization: Convex and submodular. In The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS, pp. 2241-2250, 2019. 18
Anil K Jain, Arun Ross, and Salil Prabhakar. An introduction to biometric recognition. IEEE Transactions on circuits and systems for video technology, 14(1):4-20, 2004. 2
Rajesh Jayaram, David P. Woodruff, and Samson Zhou Truly perfect samplers for data streams and sliding windows. In PODS '22 International Conference Management of Data, pp. 29 29-40, 2022. 4
Michael Kapralov, Cameron Musco, and Kshiteej Sheth. Sublinear time low-rank approximation of hankel matrices. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algo- rithms, SODA, pp. 3201-3248, 2026.
Jakub Lacki, Jakub Ocwieja, Marcin Pilipczuk, Piotr Sankowski, and Anna Zych. The power of dynamic distance oracles: Efficient dynamic algorithms for the steiner tree. Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing. STOC, pp. 11-20, 2015. 2
Jakub Lacki ①. Bernhard Haeupler ④. Christoph Grunau C. Václav Rozhon ①. and Rajesh Ja- yaram D. Fully dynamic consistent k-center clustering, 2023. 2, 18
Silvio Lattanzi and Sergei Vassilvitskii. Consistent k-clustering. In Proceedings of the 34th Inter- national Conference on Machine Learning, ICML, pp. 1975-1984, 2017. 2, 17
Mark S. Manasse, Lyle A. McGeoch, and Daniel Dominic Sleator. Competitive algorithms for server problems. J. Algorithms, 11(2):208-23) 1990.
13

---

Published as a conference paper at ICLR 2026
Kolby Nottingham Markelle Kelly, Rachel Longjohn. The uci machine learning repository, 1987.
URL https: /aaei///rrrhc /aacciiieeeeeeeeeeeeeaaaaaaeaaee ics uci edu. 26, 27
Nicole Megow, Martin Skutella, José Verschac, and Andreas Wiese. The power of recourse for online MST and TSP. SIAM J. Comput., 45(3):859-88) 2016.
Leon Mirsky. Symmetric gauge functions and unitarily invariant norms. The quarterly journal of mathematics, 11(1):50-50 1960.
Cameron Musco and Kshiteej Sheth. Sublinear time low-rank approximation of toeplitz matrices. In Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 5084-5117, 2024.
Cameron Musco and David P. Woodruff. Is input sparsity time possible for kernel low-rank ap- proximation? In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems, 2017a.
Cameron Musco and David P. Woodruff. Sublinear time low-rank approximation of positive semidefinite matrices. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 672-683, 2017b.
Soham Nagawanshi, Shalini Panthangi, Chen Wang, David P. Woodruff, and Samson Zhou. Learning- Learning-augmente augmented moment estimation on time-decay models. In The Fourteenth International Conference on Learning Representations, ICLR, 2026. 4
Mark Nixon and Alberto Aguado. Feature extraction & image processing for computer vision.
Academic press, 2012. 2
John Proakis. Digital signal processing: principles, algorithms, and applications, 4/E. Pearson Education India, 2007. 2
Rice. Rice (Cammeo and Osmancik). UCI Machine Learning Repository, 2019. DOI: http:://do..rr/11.2444422
27,28
Hinrich Schütze, Christopher D Manning, and Prabhakar Raghavan. Introduction to information retrieval, volume 39. Cambridge University Press Cambridge, 2008. 2
Zhao Song, Ali Vakilian, David P. Woodruff, and Samson Zhou. On socially fair low-rank approxi- mation and column subset selection. In Advances in Neural Information Processing Systems 38: Anmual Conference on Neural Information Processing Systems, NeurlPS, 2024.
Ameya Velingker, Maximilian Vötsch, David P. Woodruff, and Samson Zhou. Fast (1 + c)- approximation algorithms for binary matrix factorization. International Conference on Ma- chine Learning, ICML, pp. 34952-34977, 2023.
Ian H Witten and Fibe Frank. Data mining: practical machine learning tools and techniques with java implementations. Acm Sigmod Record, 31(1):76-77, 2002. 2
David P. Woodruff and Taisuke Yasuda. Online lewis weight sampling. In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 4622-4666, 2023.
David P. Woodruff and Samson Zhou. Tight bounds for adversarially robust streams and sliding windows via difference estimators, In 62nd IEEE Annual Symposium Foundations of Computer Science, FOCS 2021, pp. 1183-1196, 2021. 4
David P. Woodruff, Peilin Zhong, and Samson Zhou Near-optimal k-clustering in the sliding win- dow model. In Advances in Neural Information Processing Systems 36: Anmual Conference on Neural Information Processing Systems, NeurlPS, 2023. 4, 26
14

---

Published as a conference paper at ICLR 2026
A PRELIMINARIES
We use [n] to denote the set [1....,m}. We use poly(n) to denote a fixed polynomial in n. which can be adjusted using constants the parameter settings. We use polylog(n) to denote poly (log n).
n).
We denote the vertical concatentation of rows a1, a2 R. that a a2
a1
We say
an event & occurs with high probability if Pr [8] polyín) Recall that the Frobenius norm of
matrix A E Rn is defined by || EE Ej= A2. 1/2
The singular value decomposition of matrix A E R with rank is the decomposition A UEV for U RRxr, E IRrxr, V E Rrxd, where the columns of U are orthonormal, the rows of V are orthonormal, and E is diagonal matrix whose entries correspond to the singular values of A.
Lemma A.1. For subspaces R and T of rank k, let their corresponding orthogonal projection matrices be P and Q Then there exist constants C₁ C2 0 such that Ci( PQ (R,T)
QPI) I Recourse(R, T) S C2( P + Q (.
PP I By the triangle inequality, have 1| because the QP), Q for projection matrices Q and P. By the cyclic property of trace, the trace of Q (Q - QP) thus equals the trace (Q QP)(Q -PQ). which by the same argument, is the trace of the right-hand side. Hence it follows that IQ QPI 1 =|Q PQ / as
Proof. By definition, have Recourse R. T)
[P-QQI - | P |F PQQ + p. Observe that Q - QPI2 = I PQQPQQQ
left-hand side is the trace of - (Q-QP) Q which equals the trace of (Q-PQ)
since PT P and Q
desired. Thus, we have P Q F <
P PQ]| F + QQQ - Q]
Next, observe that
PQ P PQ Q1E Trace (P) Trace(Q)) Trace(PQ))
= 2k Trace(PQ),
since p2 P, Q² Q symmetric idempotents, and Trace P) Trace Q) k. Similarly,
2k + 2/ QPI Traco(PQ)) = 2k + Trace PQP) 4 Trace(PQ)
2 2 Trace PQQ).
using ||Q1? = Trace (race(QQP)) = Trace(PQ) Thus, we have |P PQ 1 + |PQ - Q1
2k + |P |3 - 4 Trace P Q). The latter quantity is at most 4k 4 Traco P (Q) = 2(2h
2 Trace(P Q)), which is just P| Q
Thus, it suffices to work with the less natural but perhaps more mathematically accessible definition TRRR|/ R i.c., the symmetric difference of the mass of the two subspaces,
of I/T ME--RRIE notion of recourse.
Theorem A.2 (Min-max theorem). Let A paxd be matrix with singular values o (1 A.
(A) 2...? 2 (a(A) and let (A) od (A) for all j E [d], so that &1 (A) S... S (a(A) is the reverse spectrum of A. Then for any subspace V of A with dimension k there exist unit vectors x,y E V such that
|V - (A).
Vyyll 2 (A))
Theorem A.3 (Cauchy interlacing theorem). (Hwang, 2004; Fisk, 2005) Let A E Rxxd be matrix
with singular values 0n (A) Z d2((A (A) 2 2 (A). Let v E Rdd and B = A ov E R(++1)xd
with singular values a (B) Z (B 2 (B)... Then (B) (A) for all i [d].
B TECHNICAL OVERVIEW
In this section, we provide intuition for our main results, summarizing our algorithms, various chal- lenges, well natural other approaches and why they do not work.
15

---

Published as a conference paper at ICLR 2026
Warm-up: additive error algorithm. As simple warm-up, we first describe our algorithm that achieves additive error at most e ||A00]] 1 across all times E [nl, while only incurring recourse O ( log(ndM)), corresponding to Theorem 1.1. This algorithm is quite simple. We maintain the squared Frobenius norm of the matrix A (1) across all times [n]]. We also maintain the same set of factors provided the squared Frobenius norm has not increased by a factor of (1 - =) since the previous time we changed the set of factors. When the squared Frobenius norm has increased by a factor of (1 e) at time t since the previous time we changed the set of factors, then we simply use the singular value decomposition of A (4) to set V to be the top k right singular vectors of A (*), Since we change the entire set of factors, this process can incur recourse cost at most k.
The correctness follows from the observation that each time we reset V(O, we find the optimal solution at time t. Now, over the next few times after f, our solution can only degrade by the squared Frobenius norm of the submatrix formed by the incoming rows, which is less than an e-fraction of the squared Frobenius norm of the entire matrix, due to the requirement that we recompute V(O) each time the squared Frobenius norm has increased by a (1 + é) factor. Since the Frobenius norm can only increase by a multiplicative (1 ++)) factor a total of at most O ( log(ndM)) times and we incur recourse cost k each time, then the resulting recourse is at most the desired O (a log(ndM)).
Stream reduction for relative error algorithm. We now discuss the goal of achieving 1:22 polylog(nd.)) recourse while maintaining a relative (1 + m)multiiplccative approximation to the optimal low-rank approximation cost at all times, i.e., Theorem 1.3. We first utilize online ridge- leverage score sampling (Braverman et al., 2020) to sample & polylog(ndl)) rows of the stream S of rows ai...., an on-the-fly, -ly, to form a stream S' consisting of reweighted rows bj...., . bm of A with = _ pooyyog(nddM)) ). By the guarantees of online ridge-leverage score sampling, to achieve a (1 + =ap--pppxiiiittionn to the matrix A (1) consisting of the rows , a,, it suffices to achieve a (1 + O (s)) -aproxxmaaannn to the matrix ((") consisting of the rows bj..... by that have arrived by time f. Note that since B is submatrix of A, we have t' t. Moreover, the rows of A that are sampled into B are only increased by at most a poly(n) factor, so we can assume that the magnitude of the entries is still bounded polynomially by n. Thus it suffices to perform consistent low-rank approximation on the matrix B instead. Hence for the remainder of the discussion, we assume that the stream length is polylog(ndM) rather than n.
Relative error algorithm on reduced stream. We now describe our algorithm for (1 + e)- multiplicative relative error at all times of the stream of length & poolyog(ndM).. At some time in the stream, we use the singular value decomposition of A (s) to compute the top & right singular val- ues of A (s), which we then set to be our factor V(+), We can do this each time the optimal low-rank approximation cost has increased by a multiplicative (1 + O (+))-factor since the previous time we set our factor to be V(+) We first discuss how maintain (1 aaaprooximation with the desired recourse in between the times at which the optimal low-rank approximation cost has increased by a (1 + multipliicetee factor.
Towards this goal, we perform casework on the contribution of the bottom Vk singular values within the top & right singular values of V(+), Namely, if Σi= oi (A is "small", then intuitively, the corresponding singular vectors can be replaced without substantially increasing the error. Hence in this case, we can replace one of the bottom Vk singular vectors with the new row each time new incoming row arrives. This procedure will incur Vie total recourse over the next vix updates, after which at time i we reset the factor to be the top k right singular vectors of the matrix A (!). Therefore, we incur recourse O (k) across Vk time steps.
On the other hand, if E Di=k-v of (A(AA())) (+) is "large", then the optimal low-rank approximation fac- tors cannot be projected away too much from these directions, since otherwise the optimal low-rank approximation cost would significantly increase. Thus, we can simply choose the optimal set of top right ie singular vectors at each time, because there will be substantial overlap between the new subspace and the old subspace. In particular, if we choose our threshold to be Σー=-VE of (A(s)) to be an O (E)-factor of the optimal cost, then we show that incurring Vk recourse will increase the low-rank approximation cost by (1 + e), which violates the assumption that we consider times
16

---

Published as a conference paper at ICLR 2026
during which the optimal low-rank approximation cost has not increased by (1 + (1+ multiplicative factor. Therefore, the recourse is most VI: across each time.
In summary, between the times at which the optimal low-rank approximation cost has increased by a (1 + --uultiplliiaaeiiv factor, we incur at most vk recourse for each time. Since the stream length is polylog(ndM)), we then incur kt.S -polyoog(dd)) total recourse across these times, which is our desired bound. remains to bound the total recourse at times s when the optimal low-rank approximation cost has increased by (1+E) multiplicative factor, as we reset solution to be the top k right singular values, incurring recourse lt at each of these times. Because the Frobenius norm most poly poly(ndM) (ndM), natural conclusion would be that the optimal low-rank approximation cost can increase by a (1 + E) multiplicative factor most O log(ndM)) times. Unfortunately, this is not the case.
Anti-Hadamard matrices. Problematically, there exist constructions of anti-Hadamard integer matrices, which have dimension n x d but optimal low-rank cost as small as cxp(-O (k)). Hence, the optimal cost can double O (k:) times, thereby incurring total recourse (k...). which is unde- sirably large. Instead, we show that when the optimal low-rank cost is exponentially small, then the rank of the matrix must also be quite small, meaning that the recourse of our algorithm cannot be as large as in the full-rank case. Namely, we generalize a result by Clarkson & Woodruff (2009) to show that an integer matrix A E Znxd has rank r > k and entries bounded in magnitude by M, then its optimal low-rank approximation cost is at least (ndM2) F-R, Hence, we only need to consider nadi-Hadamard matrices when the rank is less than 2k.
Fortunately, when the rank is at most < 2k, we can apply more fine- fine-grained analysis for the above cases, since there are only r vectors spanning the row span, so the recourse in many of the be at most entire row span. We then argue that if the rank r of the matrix is between it + 2' and + 2 then there can be at most O ( epochs before the cost of the optimal low-rank approximation is at least (ndM2)-100 Moreover, the recourse incurred by recomputing the top eigenspace is at most r- k < 2 so that the total recourse for the times where the rank of the matrix is between k + 2' and k + 2++1 is most O ( log log(ndM)).
previous operations
k. In particular, for
k, can simply maintain the
. It then follows that the total recourse across all times before the rank becomes at least 2k is at most O & (ndM)).
A keen reader might ask whether 3/3/2 is best possible recourse for our algorithmic approach. To that end, observe that if we change a large number of factors per update, then the total recourse will increase. Let us suppose that there are roughly k updates, which is the size of the online projection- cost preserving coreset. Now if we change r factors per update, then the total recourse will be at least kr. On the other hand, if we change a smaller number of factors per update, then we will need to recompute every steps. Each recompute takes ic recourse, for a total of k² overall recourse. Hence, the maximum of the quantities kr and k2 is minimized at Vi, giving recourse kr k² 1-3/2
Recourse lower bound. Our lower bound construction that shows recourse 9 ( log /3 is neces- sary, corresponding to Theorem 1.4, is simple. We divide the stream into θ 1 log )) phases where the optimal low-rank approximation cost increases by multiplicative (1 + O (e)) factor between each phase. Moreover, the optimal solution to the i-th phase is orthogonal to the optimal solution the (i - 1h phase, so that depending on the parity of the phase the optimal solution is either the first & elementary vectors, or the elementary vectors i + 1 through 2k. Therefore, a multiplica- tive (1 + ->-approximation at all times requires incurring (2k)) recourse between each phase, which shows the desired 9 log }) lower bound.
C ADDITIONAL RELATED WORK
We remark that there has been a flurry of recent work studying consistency for various problems. The problem of consistent clustering initialized by Lattanzi & Vassilvitskii (2017), who gave an algorithm with recourse k²2,, polylog(n) for k-clustering on insertion-only streams, i.c. the incre- mental setting. This recourse bound was subsequently improved to k polylog(n) by Fichtenberger
17

---

Published as a conference paper at ICLR 2026
et al. (2021), while version robust to outliers presented by Guo al. (2021). The approxima- tion guarantee was also recently improved to (1 + E) by Chan et al. (2025). A line of recent work has studied k-clustering in the dynamic setting Lacki ① al. (2023); Bhattacharya et al. (2024); Forster & Skarlatos (2025), where points may be inserted and deleted. Rather than k-clustering, Cohen-Addad al. (2022) studied consistency for correlation clustering, where edges are positively or negatively labeled, and the goal is to form as many clusters as necessary to minimize the number of negatively labeled edges within a cluster and the number of positively labeled edges between two different clusters. For problems beyond clustering, a line of work has also focused on submodular maximization (Jaghargh al., 2019; Duetting al., 2024; Dütting et al., 2024).
Consistent clustering. Another approach might be to adapt ideas from the consistent clustering literature. In this setting, a sequence of points in R arrive one-by-one, and the goal is to maintain a constant-factor approximation
the (k, =-ccussteiing cost, while minimizing the total recourse. Here, the recourse incurred at a time t is the size of the symmetric difference between the clustering centers selected time t and at time The only algorithm to achieve recourse subquadratic is the algorithm by Fichtenberger et al. (2021), which attempts to create robust clusters at each time by looking at geometric balls with increasing radius around each existing point to pick centers that are less sensitive to possible future points. Unfortunately, such a technique utilizes the geometric properties implicit in the objective of k-clustering and it is not obvious what the corresponding analogues should be for low-rank approximation.
D RECOURSE LOWER BOUND
In this section, we prove our recourse lower bound. The main idea is to simply partition the data stream into θ _ log }) phases, so that the optimal low-rank approximation cost increases by a multiplicatiie (1 + O (=)) -factto between each phase. We also design the input matrix so that the optimal solution to the i-th phase is orthogonal to the optimal solution to the (i- 1-th phase. Hence, depending on the parity of the phase i, the optimal solution either the first elementary vectors, or the elementary vectors k + 1 through 2k and thus (1 + -aappooximationn at all times requires incurring (kk) recourse between each phase, which shows the desired Ω ( log +) lower bound.
log there exists a sequence of rows XI,...,Xn E Rd such that any algorithm that produces a +1++) appproxximmtoonn to the cost of the optimal low-rank approximation at all times must have consistency cost 12 ( log )
Theorem 1.4. For any parameter
Proof. We divide the stream into θ ( log }) phases. Let C 2 be some parameter that we shall set. If is odd, then in the i-th phase, we add (1 (1+')' copies of the elementary vectors e1...., eg. If i is even, then in the i-th phase, we add (1 CC)' copies of the elementary vectors Ck+1..... C2k- Note that since there are θ L log )) phases and each phase inserts (1 + Ce)y copies of rows, then the total number of copies of cach row inserted is at most O (n) 2k for the correct fixing of the constant in the ((-) notation, and thus there are at most rows overall.
We remark that by construction, after the i-th phase, the optimal rank-k approxi- mation is the elementary vectors cI,..., eg if i is odd and the elementary vectors ex+ly.... e2x if i is even. In particular, by the Bccart-Young-Nor orem 3.1, after the i-th phase, the optimal rank-k approximation to the underlying ma- trix induces cost k ((1+ + + + +1 (E)+-) if is odd and k ((1 + Cs) + (1 C5)3 +... + (1 + Ce) if i is even. Note that both of these quantities are at most 2k(1 + Cz)i-1, Thus for the time t after odd phase i, matrix M of rank-k factors must satisfy
theorem, i.e., The-
X - x (2) MLM < 2ck(1 + +C)
in order to be a (1 +
5) approximation to the optimal low-rank cost.
Let E(1) = e o e₁ and 222) = ex+1 .... 62k- For any constant C > 100, it follows that M must have squared mass at least ks(1 - 2e) onto E()) to be a (1 appproxximtii to the cost of the optimal low-rank approximation to ((), i.c., [ 2 k(1 - -22) for the time t immediately following odd phase i. By similar reasoning, M must have squared mass least
18

---

Published as a conference paper at ICLR 2026
k(1 - (2a) onto E to be a (1 -aprrxxmaioiiinoonion to the cost of the optimal low-rank approximation to x(() for the time t immediately following odd phase However, because E(1) and E(2) are disjoint, then it follows that M must have recourse (2(k)) between each phase. Since there are ( log ) phases, then the total recourse must be S2 log t).
E MISSING PROOFS FROM SECTION 2
Algorithm 4 Additive error algorithm for low-rank approximation with low recourse
Input: Rows a An of input matrix E R with integer entries bounded magnitude by M, error parameter 0
Output: Additive
|| (t) | enror to the cost of the optimal low-rank approximation at all times
1:
C <-0 O
2: for each a, do
3: if (IAA01) (4) 11 2 (1 s) C then
4:
V - RECLUSTER
5: C+ A
6: end if
7: Return V
8: end for
We show correctness of Algorithm 4 all times:
Lemma E.1. Let ( be the first rows of A and let V(t) be the output of Algorithm ar time t. Let OPT, be the cost of the optimal low-rank approximation at time t. Then A A (V(O) v(0 1 < OPT, + | 1
then remains to bound the recourse of Algorithm 4: Lemma E.2. The recourse of Algorithm is at most O ( log(ndM)).
Theorem 1.1 then follows from Lemma E.1 and Lemma E.2.
Lemma E.1. Let (1) be the first rows of A and let V(A) be the oulput of Algorithm 4 time I. Let OPT, be the cost of the optimal low-rank approximation at time L. Then A A (1) (V(O) T < OPT, + || ||
Proof. Let be the time at which (t-1) was first set, that (t-1)) v(s) are the top k right singular vectors of A (*), Therefore, || (+) A (V()) OPT Hence,
(+) (4) A (V()) (A A (z) T
Σ ||a a:(V(t)) 1 T
= 1 (V(e)) [ +
Σ |la, (v(()))TV(
#
OPT. + Σ la -a:-an (V(( T
1=++1
Note that since (V()) (v))) TV()) is projection operator, then the length of a; cannot increase after being projected onto the row span of (t),, so that Ja, a a((it)) (() < | Therefore,
| (V() OPT, +
|a,
TV
i=st1
S OPT, +
Σ ||al1
i=++1
19

---

Published as a conference paper at ICLR 2026
I OPT, + |2
where the last incquality due to Line 3 of Algorithm 4. Finally, by the monotonicity of the optimal low-rank approximation cost with additional rows, we have that OPT, OPT, and thus,
| (1) A (V(")) TV OPT, t (
as desired.
Lemma E.2. The recourse of Algorithm 4 is at most ( log(ndM)).
Proof. Since each entry of A is integer bounded in magnitude by at most M, then the squared Frobenius norm of is at most (nd) Moreover, each entry of is an integer bounded, the first time it is nonzero, the squared Frobenius norm must be at least 1. Hence, the squared Frobneius norm of A can increase by a factor of (1 + E) at most (og (nd) M = O ( log(ndM)) from the first time it is nonzero. Each time it does so, we recompute the right singular values of A to be the set of factors ((t,, Thus the recourse incurred these times is at most O ( log(ndM)). For all other times, we retain the same choice of the factors. Hence the desired claim follows.
We now show that the optimal rank & subspace incurs at most constant recourse under rank one perturbations.
Lemma 2.1. Let (t-1) E (t-t-)xxd and A RAx such that A is (t-1) with the row A appended. Let Vē-1 and Vē be the optimal rank-k subspaces (the span of the top k right singular vectors) of A (t-1) and A0),, respectively. Then Recourse (V; V2) <
Proof. The recourse between two subspaces is defined as the squared Frobenius norm of the dif- ference between their corresponding orthogonal projection matrices. We first consider the co- variance matrices induced by the optimal rank-k subspaces. Namely, consider the covariance matrices B,
(A) A((r1) and B, (A) A Then we have the relationship B, = B A,A, i.e., B, is obtained from B,-1 by rank-1 positive semi-definite (PSD) update. By the Eckart- Eckart-Young theorem, c.f., Theorem 3.1, the subspace V; is the span the top eigenvectors of B,, and similarly for V;-1 and B,-1.
We next consider the intersection of the eigenspaces of B, and B,-1. We first aim to show that the dimension of the intersection of the two subspaces is at least h i.e. dim( n nV;) 2 k 1. Let S, be the subspace orthogonal A,, that S. {v E Rd A.v 0} and dim(S.) Consider the intersection W V S., By the properties of subspace dimensions:
1.
dim W) dim (V 1)+ dim(Sa) - dim dim
Since dim(bV dim(S.)
1, and dim(VV ( S.) S d, we have:
dim (W) 2 h + (d - 1) - d= --1 Now we analyze the properties of vectors W. Let W. Since w Sa. we have A,w 0.
Observe that
B.w (B.-1 + A, = Bi-I A. + A. (A(ww) = B,-IW.
Hence, W is subspace contained in both B;-1 and B,
Let A 2 ... 2 Xa be the eigenvalues of B,-1, and μ1 2 ... 2 pa be the eigenvalues of B, Since B, is rank-1 PSD update of B,-1, the eigenvalues interlace by Theorem A.3:
#1 2 \ 2 P2 2 Ag 2 ... 2 μ 2 A 2 Mk+1 2 ARt1....
the subspace W is spanned by eigenvectors of B,-1 corresponding to eigen- values A Au. Because B,w = B, for w W, these are also eigenvectors B, with the same eigenvalues. Since D M4+1. the eigenvalues associated with the subspace W are greater than or equal to the (k + 1)-th eigenvalue of B, Thus, W must be a subspace of the top-(N (I + 1) eigenspace of B,. Therefore, W S V n (V; U {u}), where is the eigenvec- tor B, corresponding to eigenvalue 4441 dim V (i-inn1 V;) k- 2.
Since W V V -
Since dim W) > 1, we have established that
20

---

Published as a conference paper at ICLR 2026
Now, let Pt-1 and P, be the orthogonal projection matrices onto Vi-1 and Vi, respectively. Let
Wint = V O V2 and Psaared the projection onto Wint If dim W im) = k. then V 1 V
and so the recourse is || - p 0.
Otherwise, if dim W knt) 1,
decompose the orthogonal projection matrices as:
P P shared
P* =
shared 11211
where U1 U2 are unit vectors orthogonal to Wint The recourse is
- | 11- Thus, we have
P. P (P shared u2ug) (P shared + (nuu)) u22ug -ujuj
so that by generalized triangle inequality,
Recourse(Pr; P.-1) S 2| m T| + 2 11
Since ı and u2 are unit vectors, then we have Recourse Pr. Pt- 1) S 4. The same proof with four unit vectors shows that if dim(W (Wia)) = 2, then Recourse P,. P.-1) 8.
Finally, we remark that due to the simplicity of rank-one perturbations, any algorithm that maintains the SVD only needs to perform a rank-one update to the SVD, which takes time O ((n + d)k + 13)) for matrix with dimensions at most n x d Brand (2006).
F MISSING PROOFS FROM SECTION 3
Lemma 3.3. Consider a time during which e is reset to 0. Suppose HEAVY is set to FALSE at time and is not reset to O within the next steps, for r S Vk. Let ( be the output of V at time Then (tt) provides (1 + 2 aaproximmation to the cost of the optimal low-rank approximation
of (t) for all t E [s.s +.strl.
Proof. Consider || - (V()) Let v(t) be the matrix (+)) with the / - vectors corresponding to the smallest t singular values of (*)) instead being replaced with the rows a,tl...., ag. By optimality of v, we have
A A (4) (V()) T < | A (0) (V(()))TV()))))
Since a, ((') for all [s, + v k). then we have
A (2) A (0) (v(()) T v = ||A A (0) (v()) TV
In other words, the rows a,+l, ...., . a cannot contribute the low-rank approximation cost of v(t)) because they are contained within the span of v(t), It remains to upper bound A
A (V(() v(())
We have
d C
Σ (A,)) *=
A (4) A (VV()))T(()))))
and Σ Di=kv (A.)) < 3 C since HEAVY is set to FALSE. Note that since E [s, + Vk), then
A (t') contains the top k Vk singular vectors of A (s) Therefore, it follows that
A (+) - A (6) (V(t)) ( < (
A (V TV
8 C. Σ of(A.) S ( i=k-V
Since the cost of the optimal low-rank approximation of (1) is at least the cost of the optimal low- rank approximation of A (+) for t > then (() provides (1 + $) -approximation to the cost of the optimal low-rank approximation of A (t) for all [s, + vk).
Lemma 3.6. Suppose HEAVY is FALSE time and is reset to 0 at time If c not reset within the next steps, for Vk, then Dis+1 Recourse ((a), ((+11)) < r.
21

---

Published as a conference paper at ICLR 2026
Proof. Let s be time during which is reset to 0 and HEAVY is set FALSE. Then for the next r steps, each time a new row is received, then Algorithm 2 replaces a row of V with the new row. Thus, the recourse is at most r.
M
Lemma 3.4. Consider a time t during which HEAVY is set to TRUE. Let V(O be the outpu of V at time t. Then Vlt) provides a (1 + +) approximmaai to the cost of the optimal low-rank approximation of A
Proof. Let OPT Σ 2i= o (Ar). We have two cases.
||A(1) Either
A
().5))PPPPPPP OPT or ||A - A (0) (V(-))) (V (1 + 2 OPTT.
In the former case, V(t-1) is already a (1 + 5) -approximation to the cost of the optimal low-rank approximation of (()) and the algorithm sets V(1) v(t-1), so that (+) is also (1 + 5
approximation to the cost of the optimal low-rank approximation of (*).
(A In the latter case, the algorithm sets V(1) be the output of RECLUSTER (4) k). i.e., the top k
eigenvectors of ( in which case A A A (V(9) V [| OPT. Thus in both cases, V(t)
provides a (1 5) appprooxxiitooon to the cost of the optimal low-rank approximation of A (t). O
Lemma 3.5. At all times t E [n]. Algorithm provides a (1 + _ approximation to the cost of the optimal low-rank approximation of (!).
Proof. Let (+) be the output of V at time t. We first consider the times where c css not reset to zero
and HEAVY is set to FALSE. By Lemma 3.3, the output ( is provides (1 + 5) approoxmmatio
to the cost of the optimal low-rank approximation of A (4) at these times.
We next consider the times & where cis not reset zero and HEAVY is set TRUE. By Lemma 3.4,
the output ( is provides (1 appprooxxinnoo to the cost of the optimal low-rank approxima- tion of A (t) at these times.
Finally, we consider the times t where e is reset to zero At these times, the algorithm sets V(t) to be the output of RECLUSTER(A A (0), ke), i.e. the top k eigenvectors of A, in which case || (1)
A (t) (V(9) TV("))(( I| = OPT. Therefore, Algorithm 2 provides (1 + +)) appproximmttoon to the cost of the optimal low-rank approximation of A (f) at all times t [m].
We next bound the recourse between epochs when the bottom Vhe singular values of the top is do not contribute significant mass.
Lemma F.1. Consider time i during which HEAVY is set to TRUE. Let ( be the output V V at time l. Suppose (i-11) fails to be a (1 + () approoximmaoo to the optimal low-rank approximation cost. Then Recourse (V)), V(t- S VT.
Proof. Let s be the most recent time at which HEAVY was set to TRUE, that s S t t-11 1. Let (s) denote the top l right singular vectors of A (+) and note that by condition of HEAVY being set to TRUE,
k
(V(())
8 || - A (0) T. 3
p..
Now, let be the time which ((t-1) was first set, that ((l-)) are the top 1 right singular vectors of A (r), Since 2 s, then by the interlacing of singular values, i... Theorem A.3, we have that
((((()) (V(())))
for all i E [d]. Therefore,
h
Σ
of (((()))
> E | (6) - (V()) 3
VE
22

---

Published as a conference paper at ICLR 2026
since all singular values are by definition non-negative.
Suppose by way of contradiction that we have
Recourse ((O, v((-)) = Recourse (VO,, v()) >
Vk.
Then at least vk singular vectors for ((t have been displaced and thus by the min-max theorem, ie., Theorem A.2,
A A (V IA A (v())
E (f(()))
51 |A A (v(o))
1
Furthermore, because ( is the top k right singular vectors of A (0) then |A A (V(())TV(() is the cost of the optimal low-rank approximation at time t. In other words, the optimal low-rank approximation cost at time t would be larger than (1+ g) ||A
A (V(()) (
On the other hand, since and / are in the same epoch, then
| (+) A (v())) (+) P3 S |A 19 A (v()) v 1+ 4) |A - (v()))
which is contradiction. Hence, it follows that Recourse V(O V(t-1)) Vk.
Lemma F.2. Suppose A Zaxd an integer matrix with rank k and entries bounded in mag- nitude by M. Then the cost of the optimal low-rank approximation to A is at least (ndM2) -
Proof. Let A Zaxd be integer matrix with rank
and entries bounded in magnitude
by M. Suppose without loss of generality that n 2 d. Let 2 2 ad 2 0 be the singular values of A and let 2 ... >d 2 be the corresponding eigenvalues of A A. Let p(A) d -he (A X.). Note that since the entries of A are all integers, then the entries of A T are all integers and thus the coefficients of p()) are all integers. In particular, since the coefficient of d in p()) is the product of the nonzero eigenvalues of A, then I[= X 2 1. Since A = o²
A
and o; 2 0 for all E [d]. we also have I[ 04 2 1.
Moreover, the squared Frobenius norm satisfies
Σ
x of = -A < ndd?
1=1
Thus, A ndM2 for all [d]. Hence,
k
A
(ndM23e
(ndM2
Thus we have Ac+1 2 (2dM2) - It follows that the optimal low-rank approximation cost is
Σ d det1 (ndM²)-
*=
Lemma 3.7. Suppose HEAVY set to TRUE time and is not reset to 0 within the next steps, for < k. Then Ettr Recourse(Vil (t), vit-1)) S rv/k.
Proof. By Lemma F.I, we have Recourse (V(), v(t-1)) < VI for all i [t+ 1,1 r]. Thus the total recourse is at most VT..
23

---

Published as a conference paper at ICLR 2026
We analyze the total recourse during times when reset the counter because the cost of the optimal low-rank approximation has doubled.
Lemma F.3. Let be the set of times at which is set to 0 because Eisk+1 of(A)) 2 2C, Then
EieT Recourse (V(), v((-1)) < O ( log (ndd)))
Proof. We define times T1 < 72 and decompose T into the times before T1, the times between Ti and T2, and the times after 72. Formally, let be the first time at which the optimal low-rank approximation cost is nonzero, ie., the first time at which the input matrix has rank k + 1. Let To be the optimal low-rank approximation cost time to- Define each epoch be the times during which the cost of the optimal low-rank approximation at least (1 + =)* To and less than (1+ ()(+_ To.
T be the first time the input matrix has rank ++1 1. Observe that before time 7I, we can maintain the entire row span of the matrix by adding each new linearly independent row to the low-rank subspace, thus preserving the optimal low-rank approximation cost at all times. This process incurs recourse at most & in total before time π1.
Next, let 72 be the first time such that the input matrix has rank at most 2k. We analyze the course between times Ti and 72. By Lemma F.2, the cost of the optimal low-rank approximation to matrix with integer entries bounded by M and rank is at least (ndM²) - Thus if the rank r of the matrix is at least & + 2' and less than & + 2 then the cost of the optimal low-rank approximation is least (ndM2) 2" Thus there can be most O (2 % epochs before the cost of the optimal low-rank approximation is at least (ndM2)--100 Let j be the index of any epoch during which the cost of the optimal low-rank approximation exceeds (ndMM) T. Since the total dimension of the span of the rows of that have arrived by epoch j is then the recourse curred by recomputing the top eigenspace is at most O (r most O (2 & log(ndM)) epochs before the cost of the optimal low-rank approximation is at least (ndM2)-1
O (2)). Since there can be at
then the consistency cost for the times where the rank of the matrix is at least k 2 and less than k + 2 is at most O ( log(ndM)). Thus the total consistency cost between times and 72 is Ela0 k O ( log(ndM)) = O ( (ndd)).
Note that after time T2, the cost of the optimal low-rank approximation is at least (ndM²) 100 Since the squared Frobenius norm is at most ndM2 then the low-rank cost also at most ndM2 Thus there can be at most O ( log(ndd)) epochs after time 72. Each epoch incurs recourse O (k) due to recomputing the top eigenspace of the prefix of A that has arrived at that time. Thus the total recourse due to the set 7 of times after is O log(ndM)).
In summary, we can decompose T into the times before Fi. the times between Ti and 72, and the times after 72- The total recourse at times / E T before is at most O (k). The total recourse at times &. E T between times Tı and 72 is at most O ( log (ndM)). The total recourse at times t E T after time is at most O (k log(ndM)). Hence, the total recourse of times t E T is at most O ( log (ndM)).
Lemma 3.8. Let T be the set of times at which is set to 0. Then Eier Recourse V(, v(t-1)) s O (nVT++ & logg (nd))
Proof. Note that can only be reset for one of the three different following reasons:
(1) HEAVY TRUE and k
(2) HEAVY FALSE and Vk
(3) Ed Disti (AA.) 2C
24

---

Published as a conference paper at ICLR 2026
In all three cases, the algorithm calls RECLUSTER(A, A, k), incurring recourse k. Observe that for matrix A with rows, the counter exceed vk most vE times. Thus the first two cases can occur most 2 times, so the total recourse contributed by the first two cases is at most nvk. Vk
remains to consider the total recourse incurred over the steps where the cost of the optimal low-rank approximation has at least doubled from the previous time C' was set. By Lemma R3, the recourse from such times is at most O ( k log2 (ndM() Hence, the total recourse is at most O (nVk # log (ndM)).
Lemma 3.9. The total recourse of Algorithm 2 on input matrix A E [Raxd with integer entries bounded in magnitude by M is nv + log (ndM)).
Proof. We first consider the times & where is not reset to zero and HEAVY is set to FALSE By Lemma 3.6, the recourse across any consecutive set of r of these steps is at most r. Thus over the stream of rows, the total recourse incurred across all steps where HEAVY is set to FALSE is at most n.
We next consider the times & where is not reset and HEAVY is set TRUE. By Lemma 3.7, the recourse across any uninterrupted sequence of these steps is at most rvk. Hence the stream of n rows, the total recourse incurred across all steps where HEAVY is set to TRUE is at most ny
Finally, consider the times where is reset to zero. By Lemma 3.8, the total recourse incurred across all steps is at most O (nvTk T +
k log"(ndM)) Therefore, the total recourse is
O (nVT: + log (wdM))
Lemma 3.10. Given an input matrix A E Baxd with integer entries bounded in magnitude by M, Algorithm achieves a (1 +1+3 -pprrxximation to the cost of the optimal low-rank approximation and achieves recourse O [nvk+ + logg(ndM)).
Proof. Note that correctness follows from Lemma 3.5 and the upper bound on recourse follows from Lemma 3.9.
Theorem 1.3. Suppose A E gndd is an integer matrix with entries bounded in magnitude by M. There exists an algorithm that achieves (1+ =)-ppproximmttion the cost of the optimal low-rank approximation A at all times and achieves recourse k3/2
g polylog(ndM)..
Proof. Let s E (0, d By Theorem 2.4, the optimal low-rank approximation to the rows of M that have been sampled by time achieves (1 1o -approximation to the cost of the optimal low-rank approximation of that have arrived at time t. Thus, it suffices to show that we provide (1 + {) >aapproximation to the cost of the optimal low-rank approximation to the matrix M at all times. Thus we instead consider new stream consisting of the rows of M Rmxd where m 2/2 (olylog(ndM) and the entries of M are integers bounded in magnitude by M (n).
Consider Algorithm on input M. Correctness follows from Lemma 3.10, so it remains repa- rameterize the settings in Lemma 3.10 to analyze the total recourse. By Lemma 3.9, the to- tal recourse on an input matrix A Inxdd with integer entries bounded in magnitude by M is O nvk + & log2 (ndM)). Thus for input matrix M with & polylog(nd.M) rows and integer entries bounded in magnitude by M (n)y(n), the total recourse is ga/2 द polylog(ndM).
G ADDITIONAL EXPERIMENTS
In this section, we describe number of additional empirical evaluations.
25

---

Published as a conference paper at ICLR 2026
G.1 RANDOM SYNTHETIC DATASET
We generate a random synthetic dataset with 3000 rows and 4 columns with integer entries between 0 and 100 and subsequently normalized by column. We again compared the cost of the solution output by Algorithm 4 with the cost of the optimal low-rank approximation for k = across c (1+ =) E {1.1,
10, 1003. We summarize our results in Figure 3, In particular, we first plot in Figure 3a the runtime of our algorithm. We then plot in Figure 3b the ratio of the cost of the solution output by Algorithm with the cost of the optimal low-rank approximation.
Similar to the skin segmentation and the rice datasets, our algorithm provides better approximation to the optimal solution as c = (1 +) decreases from 100 to I, with a number spikes a small number of rows likely due to the optimal low-rank approximation cost being quite small compared to the additive Frobenius error. Moreover, our results perform demonstrably better than the worst-case theoretical guarantee, giving roughly 2.5-approximation compared to the thcoretical guarantec of 100-approximation.
Accuracy random
2.4
2.2
mm
0-100
100
2.8
344
12
3.0
(a) Runtime on random dataset
(b) Approximations on random dataset
Fig. 3: Runtime and approximations on random dataset. Figure 3a considers 1, c 10, while
Figure 3b considers = 1, (1 +1++) (1.1,2.5, 5, 10, 100}
G.2 SKIN SEGMENTATION DATASET
Accuncy ler cateer
2.00
2800
(a) Runtime on SKIN dataset
(b) Approximations for
(c) Approximations for t =
Fig. Runtime and approximations on SKIN dataset. Figure 4a considers k 1 and 1.1, while Figure 4b considers & = 1, = (1 + =) (1.1,2.5,5 10, 100} and Figure 4c considers k 2,
c c= (1 + E 1.5 10)
We evaluate Algorithm 4 on the Skin Segmentation (SKIN) dataset (Bhatt & Dhall, 2012) from the UCI repository (Markelle Kelly, 1987), which is commonly used benchmark comparison for unsupervised learning tasks, e.g., (Borassi et al., 2020; Epasto et al., 2023; Woodruff et al., 2023). The dataset consists of total of 245057 face images encoded by B,G.R values, collected from the Color FERET Image Database and the PAL Face Database from Productive Aging Laboratory from the University of Texas at Dallas. The faces were collected from various age groups (young, middle, and old), race groups (white, black, and asian), and genders. Among the dataset, 50859 images
26

---

Published as a conference paper at ICLR 2026
skin samples, while the other 194198 images are non-skin samples, and the task is to classify which category each image falls under.
Experimental setup. For our experiments, only considered the first 3000 skin images and stripped the labels, so that the goal was to perform low-rank approximation on the B,G.R values of the remaining skin images. As theoretical guarantees ensure that the solution is changed a small number of times, we compared the cost of the solution output by Algorithm with the cost of the optimal low-rank approximation. In particular, we computed the ratios of the
costs for A across c = (1 + E) E {1.1, 2.5, 5, 10, } and for k = 2 across (1 + s) E {1.1, 2.5, 10), even though the formal guarantees of Algorithm 4 involve upper bounding the additive error.
Results and discussion. In Figure 4, we plot the ratio of the cost of the solution output by Algo- rithm 4 with the cost of the optimal low-rank approximation at each time over the duration of the data stream. We then provide the central statistics, i.e., the mean, standard deviation, and maximum for the ratio of across various values of and accuracy parameters for the SKIN dataset in Table 2.
Our results show that as expected, our algorithm provides better approximation to the optimal solu- tion as = (1 + E) decreases from 100 Once the optimal low-rank approximation cost became sufficiently large, our algorithm achieved a good multiplicative approximation. Thus we believe the main explanation for the spikes the heginning of Figure 4c due to the optimal low-rank approx- imation cost being quite small compared to the additive Frobenius error. It is somewhat surpris- ing that despite the worst-case theoretical guarantee that our algorithm should only provide a 100- approximation, it actually performs significantly better, i.e., it provides roughly 4-approximation. Thus it seems our empirical evaluations provide a simple proof-of- ofoo--of-concept demonstrating that our theoretical worst-case guarantees can be even stronger practice.
h
(1 + E)
Mean
Std. Dev.
Max
1.1
1 1.0006
0.0022
1. 1.0383
1.0088
0.0479
1.7870
5
1.0374
0.1341
2.6038
10
1.1324
0.4167
4.8201
100
3.2971
0.4532
4.8201
1.1
1.0016
0.0069
1.1521
1.5
1.0148
0.1327
5.1533
2
2.5
1.0371
0.2430
5,2778
1.3175
0.9238
6.8602
Table Average, standard deviation, and maximum for ratios of cost across various values of & and accuracy parameters for SKIN dataset.
G.3 RICE DATASET
Vtll hardine bo ditaer
Tatal racourae POC diseet
L
(a) Runtime on RICE
(b) Approximations on RICE
(c) Recourse on RICE
Fig. 5: Runtime and approximations RICE dataset. Figure 5a considers = 10, while
Figure 5b and Figure 5c consider à: = 1, c (1 + ++) E (1.1,2.5,55 5, 10, 1003
We next consider the RICE dataset (Rice) from the UCI repository (Markelle Kelly, 1987). where the goal is to classify between types of rice grown in Turkey. The first type of rice is the Osmancik species, which has large planting area since 1997, while the second type of rice is the Cammeo
27

---

Published as a conference paper at ICLR 2026
species, which has been grown since 2014 (Rice). The dataset consists of a total of 3810 rice grain images taken for the two species, with morphological features were obtained for each grain of rice. Specifically, the features are the area, perimeter, major axis length, minor axis length, eccentricity, convex area, and the extent the rice grain.
Evaluation summary. For experiments, performed low-rank approximation the seven provided features of the RICE dataset. We compared the cost of the solution output by Algo- rithm with the cost of the optimal low-rank approximation for (1.1, 5, 10, 1003. We summarize our results in Figure 5, plotting the runtime of our algorithm in Figure 5a and the ratio of the cost of the solution output by Algorithm with the cost of the optimal low-rank approximation in Figure 5b.
1 across с (1 + s)
Our results show that similar the skin segmentation dataset, our algorithm provides better ap- proximation to the optimal solution as c (1 + e) decreases from 100 to 1. Figure 5b again has a number of spikes for a small number of rows likely due to the optimal low-rank approximation cost being quite small compared to the additive Frobenius error. Furthermore, exhibit the somewhat surprising result that our algorithm provides a relatively good approximation compared to the worst-case theoretical guarantee, i.e., our algorithm empirically provides roughly 2- 2-approximation despite the worst-case guarantees only providing a 100-approximation.
results again
Finally, note that, anticipated, the recourse of our algorithm decreases as the required accuracy of the factors decreases. This is because coarser factor representations require less frequent updates as the matrix evolves.
28


Reviews:
[{"review_id": "G9M6d2dYmo", "reviewer": "Reviewer_ex4U", "summary": "This paper studies the problem of low-rank approximation (LRA). Specifically given a matrix $A$, this work studies the problem of approximating $A$ with a matrix $AV^TV$, such that $||A-AV^TV||_F^2 \\leq (1+\\epsilon)||A-A_k||_F^2$ where $A_k$ is the best rank-$k$ approximation of $A$, and rows of $A$ arrive sequentially in time. This is a very widely studied problem. A primary contribution of the paper is the following problem: given rows of $A$ arrive sequentially over time, define measure called recourse computed as $||P_t - P_t-1||_F^2$ where $P_t$ is the orthogonal projection matrix corresponding to $V^TV$ at time $t$. This work studies LRA through the lens of recourse and demonstrates that -- 1) when the goal is to approximate $A$ with $\\epsilon$ additive error, an $O(k\\log(nd)/\\epsilon)$ recourse is feasible, 2) when the goal is to approximate $A$ with $1+\\epsilon$ multiplicative error, an $O(k^2\\text{poly}\\log(nd)/\\epsilon^2)$ recourse is feasible. This is further improved to $k^{3/2}\\text{poly}\\log(nd)/\\epsilon^2$ for matrices with integer entries that are bounded, and $k^{2}\\text{poly}\\log(nd)/\\epsilon^2$ when condition number is bounded. A lower bound of $\\Omega(k\\log(n/k)/\\epsilon)$ is also shown for $1+\\epsilon$ multiplicative approximation algorithms.", "questions": "Please check the weaknesses section.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The problem setting is interesting, i.e., studying of the subspace corresponding to streaming updates and understand how subspace can differ for different algorithms is an interesting idea. Mostly because one can imagine having to reconstruct the approximation matrix again and again if the subspace is changing significantly (e.g., as stated for the Frequent directions method). \n\n- I have only glossed over the proofs, which are pretty simple, and believe they are correct. Given the authors present a lower bound to the problem, it helps us ground the theoretical upper bounds presented in this work. \n\n- I really appreciate the simple algorithms which helps maintain the approximation at time $t$. The algorithm basically checks importance of an incoming row by first identifying the bottom $\\sqrt{k}$ singular values among the top $k$ singular vectors. If these vectors have very low spectral contribution, they are \"disposable\" and so can be replaced by any incoming vector. \n\n- Good empirical evaluations help us understand how the algorithms presented here work in practice.", "weaknesses": "- There is a significant body of work on rank-$k$ approximation algorithms. However, only frequent directions has been empirically compared against. I am surprised as why this is the case.\n\n- Most of the theoretical contributions are really derivative of prior work. While I really appreciate the problem setting, the contributions are really understanding how the subspace are drifting with time given the subspace approximation algorithm. \n\n- Algorithm 2 requires computing SVD at each round in the worst case. So while one may be easily able to reduce recourse, the run time of the algorithms grows with $tk^3$, which seems expensive!\n\n- For distributional shifts, just checking the bottom $\\sqrt{k}$ may not be enough, e.g., for windowed algorithms due to Braverman et. al. 2020, or the works of Musco-Musco, or Cohen et. al. on online leverage score sampling, one might need to re-evaluate samples which was heavy at some point and might become of low importance in future. What do we do then?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Yx0pNuAbRL", "reviewer": "Reviewer_odAo", "summary": "This paper studies the online low rank approximation problem. In this problem one is given a matrix $A\\in \\mathbb{R}^{n\\times d}$ with integer entries bounded by $M$ and whose rows $a_1,\\ldots, a_n$ arrive one by one. Let $A^{t}$ denote the matrix of the first $t$ rows at time $t\\in [n]$, the goal is to output a matrix $V^{t}\\in \\mathbb{R}^{k\\times n}$ such that $A^{t}(V^{t})^T V^{t}$ is a $1+\\epsilon$ approximation rank $k$ approximation to $A^{t}$ at every time $t\\in [n]$. In particular the paper studies \\emph{consistent} algorithms for online low rank approximation. More precisely the goal is to minimize the recourse of the algorithm measured as \n\n$$\\sum_{t=1}^n \\|P_A-P_B\\|_F^2$$\n\nfor $A = V_t$ and $B = V_{t-1}$ where $P_{V}$ is the orthogonal projection matrix of the subspace spanned by $V$. Thus a low recourse algorithm ensures that the subspace of low rank approximation does not change drastically on average over the stream. Note that recourse of $nk$ can be achieved trivially by computing the best rank $k$ approximation at each step from scratch.\n\nThe first result shown in the paper is an algorithm that achieves a recourse of $O((k/\\epsilon)\\log(ndM))$ but incurs an additional additive error $\\epsilon \\|A^{t}\\|_F^2$ at each step $t\\in [n]$. Furthermore they show that a recourse of $O((k/\\epsilon^2)\\log^2 n)$ assuming an online condition number of poly$(n)$ and no additive error. Finally for matrices with integer entries they also obtain improved bounds. On the negative side they prove a lower bound on the recourse of $\\Omega(n/\\epsilon \\log(n/k))$ for obtaining a $1+\\epsilon$ approximation at every time step by constructing a hard sequence of rows.", "questions": "Although the authors very briefly discuss potential applications in feature engineering, it would be interesting to see if there are any concrete applications of low recourse algorithms for low rank approximation.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper introduces a novel model for studying low rank approximation of consistency. Consistent and low recourse algorithms have been studied for other problems in data science thus making low rank approximation a natural problem to study from a theoretical perspective. Moreover the authors show good upper and lower bounds for low rank approximation in this model.", "weaknesses": "The paper does not have many weaknesses but one is that although the problem has a natural theoretical motivation, it would be interesting for the authors to discuss more concrete practical motivations for studying low recourse algorithms for low rank approximation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SiSxXPBsD0", "reviewer": "Reviewer_vaVm", "summary": "This paper studies low rank approximation in a streaming model, where in addition to standard goals of small space and update time, they also do not want the provided solution to change too much across the lifetime of the stream.  This is modeled as \"recourse\" which is the sum of squared distances between subspaces at each step.", "questions": "None.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Standard streaming subspace approximation algorithms like FrequentDirections and Ridge Leverage Score Sampling can have very large recourse as shown theoretically, and empirically on real data.  That means they can bounce between solutions.  \n\nThe algorithm is subtle yet simple.  It is careful about when to update the estimate with extra care to not to change the subspace too much if it does not have to.  It reminds me of distributed streaming algorithms (e.g., https://arxiv.org/abs/1404.7571) that try to minimize total communication of updates, but with focus on ensuring a stable answer.  \n\nI think the recourse setting is natural and useful.  It is a nice way to quantify stability of the sketch.  \n\nA strength is that feels like a complete paper on this topic.  It has a variety of upper bounds for additive and relative error, and shows lower bounds on recourse that asymptotically match the upper bounds.  There are basic experiments that show that the algorithm is not just theoretical, but works in practice -- whereas baselines like FrequentDirections does not.", "weaknesses": "Nothing to note.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)