pith. sign in

arxiv: 2204.05398 · v3 · submitted 2022-04-11 · 🧮 math.NA · cs.NA

An Improved Incremental Singular Value Decomposition and New Error Bounds

Yangwen Zhang This is my paper

Pith reviewed 2026-05-24 12:41 UTC · model grok-4.3

classification 🧮 math.NA cs.NA
keywords incremental SVDsingular value decompositionerror boundsorthogonalityfloating-point arithmetictruncation errornumerical rankstreaming data
0
0 comments X

The pith

Restructured incremental SVD preserves exact-arithmetic output while sharpening the operator-norm truncation bound to sqrt(n) tol and making orthogonality loss independent of stream length n under a probabilistic rounding model.

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

The paper restructures the incremental SVD so that rank-preserving updates are accumulated implicitly and applied in batches. This reduces the number of large orthogonal multiplications from the full stream length n to the numerical rank r. The change is proved to match the original algorithm's exact-arithmetic result. It yields a sharpened truncation bound of sqrt(n) tol in the operator norm, attained on an example, and shows that orthogonality loss in the left factor stays independent of n, depending on column length m only via a single sqrt(m) factor. Experiments confirm the bounds and report speedups of 4.5x to 34x over prior methods.

Core claim

By accumulating rank-preserving orthogonal factors implicitly and applying them only in batches of size equal to the numerical rank, the restructured incremental SVD produces the same exact-arithmetic output as the standard algorithm while allowing a forward-error analysis that replaces the previous n tol operator-norm truncation bound with sqrt(n) tol and renders the loss of orthogonality in the left singular basis independent of the total number of updates n under the standard probabilistic model of rounding errors.

What carries the argument

Implicit accumulation of rank-preserving updates followed by batch application of the resulting orthogonal factors, which replaces per-column large-matrix multiplications with r such multiplications where r is the numerical rank.

If this is right

  • Truncation error in the operator norm is bounded by sqrt(n) tol instead of n tol.
  • Orthogonality of the left factor is preserved up to a term independent of the number of incoming columns.
  • Reorthogonalization is required only r times rather than n times.
  • Run time improves by factors between 4.5 and 34 relative to earlier incremental SVD implementations.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The batching technique could be applied to other streaming matrix factorizations such as incremental QR or eigenvalue updates.
  • In applications with very long data streams the method would allow the basis to be maintained for larger n without periodic full reorthogonalization.
  • The constructive example attaining the sqrt(n) bound suggests that further sharpening may require additional assumptions on the incoming data.
  • Hardware-specific rounding behavior outside the probabilistic model could be checked by repeating the orthogonality measurements on fixed-point or low-precision arithmetic.

Load-bearing premise

The claimed independence of orthogonality loss from stream length n rests on the assumption that floating-point rounding errors follow the standard probabilistic model.

What would settle it

A long-stream experiment in which the measured loss of orthogonality in the computed left factor grows linearly with n rather than remaining bounded independently of n.

Figures

Figures reproduced from arXiv: 2204.05398 by Yangwen Zhang.

Figure 1
Figure 1. Figure 1: Example 1: Left: W = I. Right: W = M. The whole simulations take about 154 and 4000 seconds for W = I and W = M, respectively. Next, we show the CPU1 time (seconds) of the main part of the Algorithm 4 in [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Singular values of B: Left: Algorithm 6. Right: MATLAB built-in function svd(). Next, we add reorthogonalizations (details will be given in the next section) to Algorithm 6 and plot the errors (left in [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Example 2: Left: the errors of the first 34 singular values of [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Example 3: Top: the orthogonality of Qe and Q with W = I. Bottom: the orthogonality of Qe and Q with W = M. Next, we show the CPU time (seconds) of the main part of the Algorithm 7 in [PITH_FULL_IMAGE:figures/full_fig_p019_4.png] view at source ↗
read the original abstract

The incremental singular value decomposition (SVD) updates a truncated SVD as new columns arrive, replacing a single large SVD with a sequence of small ones. In floating-point arithmetic, each update multiplies the running singular basis by a small orthogonal factor, and the accumulated product loses orthogonality unless the basis is reorthogonalized periodically. How often this reorthogonalization is needed has been an open question; we answer it by restructuring the algorithm so that rank-preserving updates are accumulated implicitly and applied in batches, reducing the number of large orthogonal multiplications from $n$, the stream length, to $r$, the numerical rank. We prove that this restructuring preserves the exact-arithmetic output of the original algorithm and establish two forward-error bounds. First, we sharpen the existing operator-norm truncation bound from $n\,\texttt{tol}$ to $\sqrt{n}\,\texttt{tol}$, and show the new rate is attained on a constructive example. Second, under a standard probabilistic rounding-error model, we prove that the loss of orthogonality of the computed left factor is independent of the stream length $n$ and depends on $m$, the length of each incoming column, only through a single $\sqrt{m}$ factor. Numerical experiments confirm both bounds and demonstrate that the proposed algorithm runs $4.5\times$ to $34\times$ faster than its closest competitors.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The manuscript presents a restructured incremental SVD algorithm that accumulates rank-preserving updates implicitly and applies them in batches, reducing the number of large orthogonal multiplications from the stream length n to the numerical rank r. It proves that the restructuring preserves the exact-arithmetic output of the original algorithm, sharpens the operator-norm truncation bound from n tol to sqrt(n) tol (attained on a constructive example), and under a standard probabilistic rounding-error model proves that the loss of orthogonality of the computed left factor is independent of n (depending on column length m only through a sqrt(m) factor). Numerical experiments confirm the bounds and report speedups of 4.5x to 34x over competitors.

Significance. If the derivations hold, the work resolves an open question on reorthogonalization frequency for incremental SVD by delivering both a practical restructuring and sharpened theoretical guarantees, including a constructive example attaining the new truncation rate and an n-independent orthogonality bound. These results, together with the reported computational gains, would strengthen the theoretical and practical foundations of streaming SVD methods in numerical linear algebra.

major comments (1)
  1. [Forward-error analysis section (orthogonality bound)] Forward-error analysis section (orthogonality bound): The claimed independence of orthogonality loss from stream length n is derived entirely under a standard probabilistic rounding-error model applied to the batched orthogonal multiplications. The manuscript does not derive the required statistical independence of rounding errors for the specific sequence of rank-preserving updates or demonstrate applicability of the model beyond invocation; if the model fails to hold, the n-independence does not follow. This assumption is load-bearing for the central practical guarantee.
minor comments (2)
  1. [Truncation bound section] The constructive example attaining the sqrt(n) tol bound is referenced in the abstract but its explicit construction and verification would benefit from a dedicated subsection or appendix to allow direct reproduction.
  2. [Introduction] Notation for the numerical rank r and the tolerance tol should be defined at first use in the main text rather than only in the abstract.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading, the positive assessment of the work's significance, and the recommendation for major revision. We respond to the single major comment below.

read point-by-point responses

  1. Referee: Forward-error analysis section (orthogonality bound): The claimed independence of orthogonality loss from stream length n is derived entirely under a standard probabilistic rounding-error model applied to the batched orthogonal multiplications. The manuscript does not derive the required statistical independence of rounding errors for the specific sequence of rank-preserving updates or demonstrate applicability of the model beyond invocation; if the model fails to hold, the n-independence does not follow. This assumption is load-bearing for the central practical guarantee.

    Authors: We agree that the manuscript invokes the standard probabilistic rounding-error model for the batched orthogonal multiplications without deriving statistical independence of the rounding errors specifically for the sequence of rank-preserving updates. This model is a standard assumption in the literature on rounding-error analysis of orthogonal transformations (as used, for example, in analyses of Householder QR and related SVD methods), and the batched updates consist of the same class of operations. Nevertheless, the referee is correct that the manuscript does not explicitly demonstrate applicability to this particular sequence. To address the concern, we will revise the forward-error analysis section to include a short paragraph clarifying the applicability of the model, with citations to the relevant literature on the probabilistic model. This is a clarification rather than a new derivation. revision: partial

Circularity Check

0 steps flagged

No circularity; derivations are independent of inputs

full rationale

The paper restructures the incremental SVD algorithm, proves exact-arithmetic equivalence by direct construction, and derives sharpened truncation and orthogonality bounds from the restructured operations plus a standard external probabilistic rounding-error model. No load-bearing step reduces by definition, fitted-parameter renaming, or self-citation chain to the paper's own inputs or outputs; the n-independence claim is conditional on the model rather than tautological. The analysis is self-contained against external benchmarks and exhibits none of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard properties of the SVD and a probabilistic model of floating-point rounding; no new free parameters or postulated entities are introduced.

axioms (1)
  • domain assumption Standard probabilistic model for rounding errors in floating-point arithmetic
    Invoked to establish that orthogonality loss is independent of stream length n.

pith-pipeline@v0.9.0 · 5802 in / 1320 out tokens · 32233 ms · 2026-05-24T12:41:24.503955+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. An efficient and memory free algorithm for subdiffusion equation using incremental singular value decomposition

    math.NA 2022-11 unverdicted novelty 6.0

    Presents an ISVD-based memory-efficient solver for subdiffusion equations with error analysis and numerical validation against direct and fast methods.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages · cited by 1 Pith paper

  1. [1]

    C. Bach, D. Ceglia, L. Song, and F. Duddeck , Randomized low-rank approximation methods for projection-based model order reduction of large nonlinear dynamical problems , Internat. J. Numer. Methods Engrg., 118 (2019), pp. 209–241, https://doi.org/10.1002/ nme.6009

    work page 2019

  2. [2]

    M. W. Berry , Large-scale sparse singular value computations , The International Journal of Supercomputing Applications, 6 (1992), pp. 13–49. 22 An answer to an open question in the incremental SVD

    work page 1992

  3. [3]

    Brand , Incremental singular value decomposition of uncertain data with missing values , in European Conference on Computer Vision, Springer, 2002, pp

    M. Brand , Incremental singular value decomposition of uncertain data with missing values , in European Conference on Computer Vision, Springer, 2002, pp. 707–720

    work page 2002

  4. [4]

    Brand , Fast low-rank modifications of the thin singular value decomposition , Linear Al- gebra Appl., 415 (2006), pp

    M. Brand , Fast low-rank modifications of the thin singular value decomposition , Linear Al- gebra Appl., 415 (2006), pp. 20–30, https://doi.org/10.1016/j.laa.2005.07.021

    work page doi:10.1016/j.laa.2005.07.021 2006

  5. [5]

    F areed and J

    H. F areed and J. R. Singler , A note on incremental POD algorithms for continuous time data, Appl. Numer. Math., 144 (2019), pp. 223–233, https://doi.org/10.1016/j.apnum. 2019.04.020

    work page doi:10.1016/j.apnum 2019

  6. [6]

    F areed and J

    H. F areed and J. R. Singler , Error analysis of an incremental proper orthogonal decom- position algorithm for PDE simulation data , J. Comput. Appl. Math., 368 (2020), pp. 112525, 14, https://doi.org/10.1016/j.cam.2019.112525

    work page doi:10.1016/j.cam.2019.112525 2020

  7. [7]

    F areed, J

    H. F areed, J. R. Singler, Y. Zhang, and J. Shen , Incremental proper orthogonal decomposition for PDE simulation data , Comput. Math. Appl., 75 (2018), pp. 1942–1960, https://doi.org/10.1016/j.camwa.2017.09.012

    work page doi:10.1016/j.camwa.2017.09.012 2018

  8. [8]

    Ghashami, E

    M. Ghashami, E. Liberty, J. M. Phillips, and D. P. Woodruff , Frequent direc- tions: simple and deterministic matrix sketching , SIAM J. Comput., 45 (2016), pp. 1762–1792, https://doi.org/10.1137/15M1009718

    work page doi:10.1137/15m1009718 2016

  9. [9]

    Hwang, Cauchy’s interlace theorem for eigenvalues of Hermitian matrices, Amer

    S.-G. Hwang, Cauchy’s interlace theorem for eigenvalues of Hermitian matrices, Amer. Math. Monthly, 111 (2004), pp. 157–159, https://doi.org/10.2307/4145217

    work page doi:10.2307/4145217 2004

  10. [10]

    M. A. Iwen and B. W. Ong , A distributed and incremental SVD algorithm for agglomerative data analysis on large networks , SIAM J. Matrix Anal. Appl., 37 (2016), pp. 1699–1718, https://doi.org/10.1137/16M1058467

    work page doi:10.1137/16m1058467 2016

  11. [11]

    Lin and Y

    L. Lin and Y. Tong , Low-rank representation of tensor network operators with long-range pairwise interactions, SIAM J. Sci. Comput., 43 (2021), pp. A164–A192, https://doi.org/ 10.1137/19M1287067

    work page doi:10.1137/19m1287067 2021

  12. [12]

    Mastronardi, E

    N. Mastronardi, E. E. Tyrtyshnikov, and P. V an Dooren , A fast algorithm for updat- ing and downsizing the dominant kernel principal components , SIAM J. Matrix Anal. Appl., 31 (2010), pp. 2376–2399, https://doi.org/10.1137/090774422

    work page doi:10.1137/090774422 2010

  13. [13]

    G. M. Oxberry, T. Kostova-V assilevska, W. Arrighi, and K. Chand , Limited- memory adaptive snapshot selection for proper orthogonal decomposition , Internat. J. Numer. Methods Engrg., 109 (2017), pp. 198–217, https://doi.org/10.1002/nme.5283. 23

    work page doi:10.1002/nme.5283 2017