Pith. sign in

REVIEW 4 major objections 4 minor 40 references

Fast and Accurate SVD-Type Updating in Streaming Data

T0 review · 4 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Bidiagonal factorizations can be updated in quadratic time after low-rank data changes, matching SVD accuracy in streaming applications.

desk verdict Theorem 3.1 is real, BGU is a sketch: the paper deserves a referee but needs major revision before it can be accepted. read the letter →

arxiv 2509.02840 v1 pith:S3M4TPRL submitted 2025-09-02 math.NA cs.LGcs.MScs.NA

Johannes J. Brust , Michael A. Saunders This is my paper · ORCID
classification math.NAcs.LGcs.MScs.NA MSC 65F5568T0965Y20
keywords streamingdatabidiagonalfactorizationlow-rankupdatesGivensrotationsHouseholdercompactWYsubspacetrackingincrementalSVDtruncated
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper claims that a bidiagonal factorization, the expensive first step of the SVD, can be maintained cheaply when a data matrix changes by a low-rank addition, instead of being recomputed from scratch. Two update algorithms are proposed. The first, a compact Householder method, keeps the sparse bidiagonal part and the added low-rank part decoupled, needing about half the memory of standard bidiagonalization. The second, a Givens-rotation method, performs each rotation in about 10 multiplications and updates the factorization in O(n^2) time for an n-dimensional problem, compared with the usual O(n^3). The authors argue that this makes accurate SVD-type subspace tracking practical for high-throughput streaming data such as recommendation systems and network link prediction.

What carries the argument

The central object is the bidiagonal-plus-rank-one matrix B + b+c+^T, obtained by projecting the update vectors into the existing factor spaces. The Givens method carries the reduction by rotations that each zero one entry of b+ or c+ and then chase the newly created bulge along the band, keeping the matrix within a four-diagonal pattern; because each rotation only multiplies about five elements, the per-rotation cost is constant. The Householder method instead uses the compact WY representation of products of Householder reflectors to write the partially transformed matrix as the original bidiagonal matrix plus an explicit low-rank correction, so the sparse and dense parts never mix.

What would settle it

Run the Givens algorithm on a random dense bidiagonal-plus-rank-one matrix and count the total number of rotations and the maximum bandwidth reached for n = 100, 200, 400, and so on: if the rotation count grows faster than quadratic in n, or if any band element outside the claimed four diagonals becomes nonzero and persists, the central complexity claim fails. A second check is termination: on any constructed instance, if the bulge-chasing phase ever cycles without reducing the number of nonzeros in the update vectors, the algorithm is not correct on that input.

Watch

Extended reading notes

Core claim

The central claim is that after a rank-one modification A+ = A + bc^T of a matrix whose bidiagonal factorization A = QBP^T is known, the new bidiagonal factorization can be obtained by reducing the small middle matrix B + (Q^Tb)(P^Tc)^T to bidiagonal form. This middle matrix has the special structure of a bidiagonal plus rank-one term, and the paper shows that the structure can be exploited in two ways. The Householder-based method stores reflectors through a compact WY representation that keeps the sparse bidiagonal part separated from a low-rank correction, avoiding fill-in and cutting memory roughly in half. The Givens-based method alternately eliminates entries of the two update vectors

Load-bearing premise

The Givens algorithm's quadratic complexity and correctness rest on the unproven assumption that each rotation touches only a constant-size window of the banded matrix and that every bulge can be chased off with at most O(n) rotations; the paper illustrates this pattern in a figure but gives no proof of termination or exact operation count.

Editorial extensions

If this is right

  • A stream of rank-one updates can be absorbed into a bidiagonal factorization without ever forming the updated dense matrix, so memory and flops per update stay tied to the factorization size rather than the full matrix.
  • Because bidiagonalization is the main phase of dense SVD algorithms, an efficient bidiagonal updater is a direct route to cheaper incremental SVD and partial eigenvalue updates.
  • The quadratic scaling of the Givens method makes large truncation ranks feasible at sub-second per-update costs, where refactorization would be cubic and prohibitive.
  • The Householder representation preserves sparsity and stores only the reflectors used so far, so stopping early gives a valid partial factorization whose memory grows only with the number of steps taken.
  • Error in the Frobenius norm of the updated bidiagonal factor remains near machine precision in the paper's experiments, matching the accuracy target set by SVD-based updates.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural test, not reported in the paper, is to instrument the Givens algorithm on random bidiagonal-plus-rank-one matrices and count rotations as n grows; if the number of bulge-chasing rotations scales linearly per elimination, the O(n^2) claim becomes a theorem rather than a heuristic.
  • The same bidiagonal-plus-rank-one reduction could be applied to symmetric matrices to produce a tridiagonal-plus-rank-one update, giving a quadratic-time path to eigenvalue tracking; the paper mentions symmetric adaptation only as future work.
  • If the Givens updater is combined with randomized sketching in the style of the paper's randomized bidiagonal decomposition, one could update approximate factorizations without exact orthogonality, trading a little accuracy for even higher throughput on very large streams.
  • The paper leaves open a formal convergence and termination proof for the bulge-chasing pattern; providing such a proof would convert the complexity claim from empirical to rigorous.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper proposes updating bidiagonal factorizations under low-rank (specifically rank-1) modifications for streaming data. Two algorithms are introduced: BHU, a compact Householder-based update that stores the transformation via a compact WY representation (Theorem 3.1, Algorithm 1), and BGU, a Givens-rotation-based update claimed to run in O(4n^2) flops with about 10 flops per rotation. The authors report experiments on link prediction, MovieLens, and SuiteSparse matrices, comparing BGU against randomized power iteration, Brand's incremental SVD, and LAPACK's zgebrd. The central claims are that BGU scales quadratically, maintains accuracy comparable to SVD-based methods, and is suitable for high-throughput streaming.

Significance. If fully established, a quadratic-cost update of a bidiagonal factorization after a rank-one modification would be a valuable contribution to streaming SVD-type computations. The compact WY representation in Theorem 3.1 is an elegant analytic result and provides a genuinely lower-memory route for sparse bidiagonalization. The authors have also released code and compare on real datasets. However, the headline BGU algorithm is not actually specified in the manuscript, the O(4n^2) complexity count is a heuristic, and the numerical accuracy evidence is too weak to support the accuracy claims. The paper's central contribution is therefore currently unverifiable, though the underlying ideas appear potentially salvageable.

major comments (4)
  1. [§3.4] Algorithm 2 (BGU), the paper's headline contribution, is not actually specified. The text gives a prose description of two phases and then a caption 'Algorithm 2: BGU (Bidiagonal Givens Update)' with no pseudocode, no rotation schedule, no data layout, and no termination criterion. The referenced Figure 3, which is essential to the claim that each rotation touches only O(1) entries, is missing (only the caption appears). A reader cannot reproduce or audit the algorithm, and the claimed O(4n^2) flop count cannot be verified. Please provide a complete algorithm specification and a formal statement of what it computes.
  2. [§3.4] The complexity estimate 'phase 1 requires O(2n^2) flops' is a heuristic count. It assumes that every nonzero in b+ and c+ creates a bulge that is chased off in at most n rotations, that each rotation updates a constant number of entries, and that phase 2 chases exactly 2n−3 bulges. None of these statements is proved. If bulges interact or if the shaded pattern in the missing Figure 3 is not constant-sized, the quadratic bound can fail. A rigorous rotation-count and per-rotation cost analysis is needed for the central scaling claim.
  3. [§4, Table 1, Eq. (4.8)] The accuracy evidence only reports |∥A+∥F − ∥B+∥F| (or sums of such quantities). This metric does not measure the quality of the computed factorization: a factorization with completely wrong Q and P can have the same Frobenius norm. The claim that BGU is 'similarly accurate as the SVD methods' requires a direct error measure, e.g., relative reconstruction error ∥A+ − Q+B+P+^T∥F/∥A+∥F, subspace distance between the computed and true dominant subspaces, or held-out prediction error in the streaming experiments. Please add such experiments.
  4. [§3.3, Algorithm 1] Algorithm 1 (BHU) is specified as pseudocode, but its correctness as a complete bidiagonalization is not stated as a theorem; the complexity analysis is a flop count rather than a proof. Since Theorem 3.1 provides the representation, a short induction would make the correctness argument rigorous. This is less severe than the BGU gaps, but it is still part of the paper's methodological claim.
minor comments (4)
  1. [§1.3] The citation 'Brandt [4, 3]' should be 'Brand [4, 3]' to match the reference list.
  2. [§3.3] The memory comparison claims the standard method requires 'more than twice' the storage, but the threshold on k is not stated. Clarify the regimes in which the compact representation is preferred.
  3. [§4.1] The comparison with RPI [12] uses the authors' repository but does not report the same prediction-oriented error metrics as [12]; this makes it hard to assess whether the subspace-tracking quality is comparable.
  4. [§3.4] The line 'Algorithm 2: BGU (Bidiagonal Givens Update)' appears more like a caption than an algorithm; if an algorithm environment was intended, it is missing from the manuscript.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the bidiagonal-update reductions are algebraic, the compact-WY theorem is proved from independent results, and the numerical comparisons use directly computed residuals.

full rationale

The derivation chain is self-contained and non-circular. Section 3.2 reduces an arbitrary rank-one update to the smaller problem of bidiagonal-plus-rank-one (Eq. (3.3)), which is a genuine algebraic transformation, not an assumption of the conclusion. Theorem 3.1 (Eq. (3.12)) is proved in the text using the compact WY representation of Walker [36] and Puglisi [29]; the proof is included and does not invoke the paper's own results. Algorithm 1 (BHU) is explicitly specified and its arithmetic cost is counted term-by-term, yielding Eq. (3.14); no fitted constants or target quantities are used as inputs. The Givens-based BGU is advertised as quadratic, but Section 3.4 does not actually specify the algorithm (it appears only as the caption 'Algorithm 2: BGU (Bidiagonal Givens Update)') and the O(4n^2) claim rests on the shaded-pattern count in Figure 3, which is not displayed. That is a serious specification/verification gap—a correctness or reproducibility risk—not a circularity: the complexity estimate is an asserted counting argument, not an output that was fed back in as input. The numerical experiments compare against LAPACK, Brand's incremental SVD, and RPI using directly computed Frobenius-norm residuals, so the accuracy claims are externally checkable rather than being renamed fits. Self-citations in the introduction (e.g., Brust [9], Brust and Gill [8]) are background and are not load-bearing; the central theorem is supported by independent references and a written proof. Missing '??' pointers to supplementary material are editorial gaps, not circular reasoning. No step in the paper derives a predicted quantity from a parameter fitted to that same quantity or invokes an author-supplied uniqueness theorem to force its choice. Overall circularity score: 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters are fit; BHU and BGU have no adjustable constants. The central derivation is self-contained, but the BGU algorithm's existence and cost depend on an unproven structural assumption about Givens rotation sequences.

assumptions (5)
  • standard math Every real matrix has a bidiagonal factorization A = QBP^T
    Used as the starting point in eq. (1.2) and throughout.
  • standard math Compact WY representation formulas in eq. (3.10) correctly represent products of Householder reflectors
    From Walker [36] and Puglisi [29], used in Theorem 3.1.
  • standard math Eckart-Young theorem for truncated SVD error
    Used in eq. (1.4) to motivate bidiagonal approximations.
  • ad hoc to paper The Givens rotation sequence in Section 3.4 reduces B + b+c+^T to bidiagonal with O(1) flops per rotation and O(n) rotations per nonzero element of b+, c+, preserving the quaddiagonal pattern
    This is the core algorithmic assumption behind BGU's O(4n^2) claim; it is not proven and the figure illustrating it is missing.
  • domain assumption In streaming experiments, periodic reorthogonalization keeps the updated factors sufficiently orthogonal
    Section 4.2 uses a heuristic check with no formal criterion or bound.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fast and Accurate SVD-Type Updating in Streaming Data." pith.science (2026). https://pith.science/paper/S3M4TPRL

@misc{pith2026250902840,
  author       = {Pith},
  title        = {Pith review of: Fast and Accurate SVD-Type Updating in Streaming Data},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/S3M4TPRL}},
  note         = {Machine review of arXiv:2509.02840}
}
read the original abstract

For a datastream, the change over a short interval is often of low rank. For high throughput information arranged in matrix format, recomputing an optimal SVD approximation after each step is typically prohibitive. Instead, incremental and truncated updating strategies are used, which may not scale for large truncation ranks. Therefore, we propose a set of efficient new algorithms that update a bidiagonal factorization, and which are similarly accurate as the SVD methods. In particular, we develop a compact Householder-type algorithm that decouples a sparse part from a low-rank update and has about half the memory requirements of standard bidiagonalization methods. A second algorithm based on Givens rotations has only about 10 flops per rotation and scales quadratically with the problem size, compared to a typical cubic scaling. The algorithm is therefore effective for processing high-throughput updates, as we demonstrate in tracking large subspaces of recommendation systems and networks, and when compared to well known software such as LAPACK or the incremental SVD.

Figures

Figures reproduced from arXiv: 2509.02840 by the authors.

Figure 1
Figure 1. Low-rank approximations of an image using truncated BD and truncated SVD. The [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Pattern of the middle matrix in Theorem 1, and the memory layout of the repre [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗
Figure 3
Figure 3. Phase 1 in a Givens bidiagonal updating algorithm. Shaded elements are accessed [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Comparison of algorithm BGU and randomized power iteration (RPI) [ [PITH_FULL_IMAGE:figures/full_fig_p017_4.png]
Figure 5
Figure 5. Figure 5: Algorithm BGU and the incremental SVD [4] for updating a rank-r = 2000 approx￾imation. The residuals remain small in both methods. Each BGU update costs about 0.25 seconds, while the incremental SVD takes about 0.5 secs (blue and red dots in the right axis). 4.3. Bench…
Figure 6
Figure 6. Figure 6: Algorithms BGU, BHU and lapack’s zgebrd on a set of 43 SuiteSparse problems. [PITH_FULL_IMAGE:figures/full_fig_p019_6.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

40 extracted references · 38 canonical work pages

  1. [1]

    Anderson, Z

    E. Anderson, Z. Bai, C. Bischof, L. S. Blackford, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, et al. , LAPACK users’ guide , SIAM, 1999

    work page 1999

  2. [2]

    Bischof and C

    C. Bischof and C. V an Loan, The WY representation for products of Householder matrices , SIAM J. Sci. and Statist. Comput., 8 (1987), pp. s2–s13

    work page 1987

  3. [3]

    M. Brand, Incremental singular value decomposition of uncertain data with missing values , in Computer Vision—ECCV 2002: 7th European Conference on Computer Vision Copenhagen, Denmark, May 28–31, 2002 Proceedings, Part I 7, Springer, 2002, pp. 707–720

    work page 2002

  4. [4]

    Brand, Fast low-rank modifications of the thin singular value decomposition , Linear Algebra and its Applications, 415 (2006), pp

    M. Brand, Fast low-rank modifications of the thin singular value decomposition , Linear Algebra and its Applications, 415 (2006), pp. 20–30

    work page 2006

  5. [5]

    Brust and J

    D. Brust and J. J. Brust , Effective matrix designs for COVID-19 group testing , BMC bioinformatics, 24 (2023), p. 26

    work page 2023

  6. [6]

    Brust, O

    J. Brust, O. Burdakov, J. Erway, and R. Marcia , Algorithm 1030: SC-SR1: MATLAB software for limited-memory SR1 trust-region methods , ACM Trans. Math. Softw., 48 (2022), pp. 1–33

    work page 2022

  7. [7]

    J. J. Brust, Code for Algorithms BGU and BHU and test programs . https://github.com/johannesbrust/ bdup, 2025

    work page 2025

  8. [8]

    J. J. Brust and P. E. Gill , A trust-region quasi-Newton method , SIAM J. Sci. Comput., 46 (2024), pp. A3330–A3351

    work page 2024

Show all 40 references
  1. [9]

    J. J. Brust, R. F. Marcia, C. G. Petra, and M. A. Saunders , Large-scale optimization with linear equality constraints using reduced compact representation , SIAM J. Sci. Comput., 44 (2022), pp. A103–A127

    2022

  2. [10]

    J. E. Cohen and V. Leplat , Efficient algorithms for regularized nonnegative scale-invariant low-rank approximation models, SIAM J. Math. Data Sci., 7 (2025), pp. 468–494

    2025

  3. [11]

    T. A. Davis, Y. Hu, and S. Kolodziej , The SuiteSparse matrix collection . https://sparse.tamu.edu/, 2015–present

    2015

  4. [12]

    H. Deng, Y. Yang, J. Li, C. Chen, W. Jiang, and S. Pu , Fast updating truncated SVD for representation learning with sparse matrices , in International Conference on Representa- tion Learning, B. Kim, Y. Yue, S. Chaudhuri, K. Fragkiadaki, M. Khan, and Y. Sun, eds., vol. 2024, ...

    2024

  5. [13]

    E. D. Dolan and J. J. Mor ´e, Benchmarking optimization software with performance profiles , Mathe- matical programming, 91 (2002), pp. 201–213

    2002

  6. [14]

    J. J. Dongarra, D. C. Sorensen, and S. J. Hammarling , Block reduction of matrices to condensed forms for eigenvalue computations , J. Comp. and Appl. Math., 27 (1989), pp. 215–227

    1989

  7. [15]

    Eckart and G

    C. Eckart and G. Young , The approximation of one matrix by another of lower rank , Psychometrika, 1 (1936), pp. 211–218

    1936

  8. [16]

    Golub and W

    G. Golub and W. Kahan , Calculating the singular values and pseudoinverse of a matrix , SIAM J. Numer. Anal., 2 (1965), pp. 205–224

    1965

  9. [17]

    G. H. Golub and C. Reinsch , Singular value decomposition and least squares solutions , Numer. Math., 14 (1970), pp. 403–420. Also in [ ?, pp. 134–151]

    1970

  10. [18]

    G. H. Golub and C. F. V an Loan, Matrix Computations , Johns Hopkins Studies in the Mathematical Sciences, The Johns Hopkins University Press, Baltimore, fourth ed., 2013

    2013

  11. [19]

    L. Han, Y. Li, H. Zhang, P. Milanfar, D. Metaxas, and F. Yang, SVDiff: Compact parameter space for diffusion fine-tuning , in Proceedings of the IEEE/CVF International Conference on Computer Vision, 2023, pp. 7323–7334

    2023

  12. [20]

    F. M. Harper and J. A. Konstan , The MovieLens datasets: History and context , ACM Transactions on Interactive Intelligent Systems (tiis), 5 (2015), pp. 1–19. 22 J. J. BRUST, AND M. A. SAUNDERS

    2015

  13. [21]

    A. S. Householder, Unitary triangularization of a nonsymmetric matrix , J. Association for Computing Machinery, 5 (1958), pp. 339–342

    1958

  14. [22]

    G. W. Howell, J. W. Demmel, C. T. Fulton, S. Hammarling, and K. Marmol , Cache efficient bidiagonalization using BLAS 2.5 operators , ACM Trans. Math. Softw., 34 (2008), pp. 1–33

    2008

  15. [23]

    Jeong, D

    H. Jeong, D. Needell, and E. Rebrova , Stochastic gradient descent for streaming linear and rectified linear systems with adversarial corruptions , SIAM J. on Mathematics of Data Science, 7 (2025), pp. 516–541

    2025

  16. [24]

    R. B. Lehoucq, D. C. Sorensen, and C. Yang , ARPACK users’ guide: Solution of large-scale eigen- value problems with implicitly restarted Arnoldi methods , SIAM, 1998

    1998

  17. [25]

    Leskovec, K

    J. Leskovec, K. J. Lang, A. Dasgupta, and M. W. Mahoney , Community structure in large net- works: Natural cluster sizes and the absence of large well-defined clusters , Internet Mathematics, 6 (2009), pp. 29–123

    2009

  18. [26]

    J. Lim, D. Ross, R.-S. Lin, and M.-H. Yang , Incremental learning for visual tracking , Advances in neural information processing systems, 17 (2004)

    2004

  19. [27]

    Moonen, P

    M. Moonen, P. V an Dooren, and J. V andewalle, A singular value decomposition updating algorithm for subspace tracking, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 1015–1038

    1992

  20. [28]

    Musco and C

    C. Musco and C. Musco, Randomized block Krylov methods for stronger and faster approximate singular value decomposition, Advances in Neural Information Processing Systems, 28 (2015)

    2015

  21. [29]

    Puglisi, Modification of the Householder method based on the compact WY representation , SIAM J

    C. Puglisi, Modification of the Householder method based on the compact WY representation , SIAM J. Sci. and Statist. Comput., 13 (1992), pp. 723–726

    1992

  22. [30]

    A. K. Saibaba and A. Mi ´edlar, Randomized low-rank approximations beyond Gaussian random ma- trices, SIAM Journal on Mathematics of Data Science, 7 (2025), pp. 136–162

    2025

  23. [31]

    Sarwar, G

    B. Sarwar, G. Karypis, J. Konstan, and J. Riedl , Incremental singular value decomposition algo- rithms for highly scalable recommender systems , in Fifth international conference on computer and information science, vol. 1, Citeseer, 2002, pp. 27–8

    2002

  24. [32]

    Schreiber and C

    R. Schreiber and C. V an Loan , A storage-efficient WY representation for products of Householder transformations, SIAM J. Sci. and Statist. Comput., 10 (1989), pp. 53–57

    1989

  25. [33]

    H. D. Simon and H. Zha , Low-rank matrix approximation using the Lanczos bidiagonalization process with applications, SIAM J. Sci. Comput., 21 (2000), pp. 2257–2274

    2000

  26. [34]

    Y. Sun, Y. Guo, C. Luo, J. Tropp, and M. Udell , Low-rank Tucker approximation of a tensor from streaming data , SIAM J. on Mathematics of Data Science, 2 (2020), pp. 1123–1150, https: //doi.org/10.1137/19M1257718

    2020 doi

  27. [35]

    Vecharynski and Y

    E. Vecharynski and Y. Saad, Fast updating algorithms for latent semantic indexing , SIAM Journal on Matrix Analysis and Applications, 35 (2014), pp. 1105–1131

    2014

  28. [36]

    H. F. W alker, Implementation of the GMRES method using Householder transformations , SIAM J. Sci. and Statist. Comput., 9 (1988), pp. 152–163

    1988

  29. [37]

    D. S. W atkins, Fundamentals of Matrix Computations , John Wiley & Sons, 2004

    2004

  30. [38]

    Yamazaki, J

    I. Yamazaki, J. Kurzak, P. Luszczek, and J. Dongarra , Randomized algorithms to update partial singular value decomposition on a hybrid CPU/GPU cluster , in Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, 2015, pp. 1–12

    2015

  31. [39]

    Zafarani and H

    R. Zafarani and H. Liu , Social computing data repository at ASU , 2009, http://socialcomputing.asu. edu

    2009

  32. [40]

    Zha and H

    H. Zha and H. D. Simon , On updating problems in latent semantic indexing , SIAM J. Sci. Comput., 21 (1999), pp. 782–791

    1999

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.