{"id":"4724a2a8-a1ef-463e-9c03-311ee2056367","arxiv_id":"2509.02840","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"BHU and BGU update bidiagonal factorizations under low-rank streaming changes, with BGU achieving quadratic-time updates claimed to match SVD accuracy.","lead":"This paper introduces two algorithms, BHU and BGU, for updating a matrix's bidiagonal factorization when a low-rank change is streamed in, avoiding a full refactorization. The Givens-based BGU is claimed to run in quadratic time, potentially speeding up large recommendation and network analyses.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section 3.4 names 'Algorithm 2' but provides no actual algorithm: no rotation schedule, banded storage layout, or termination proof, so the advertised O(4n^2) BGU complexity and all BGU timings rest on an unverifiable heuristic tied to the missing Figure 3.","rationale":"The reader's weakest assumption identifies exactly the load-bearing gap: BGU, the main advertised algorithm, is not specified. I checked the manuscript for an algorithm description in §3.4. It provides the goals of phase 1 and phase 2 and a heuristic complexity count, but no pseudocode, no rotation ordering, no proof that the quaddiagonal is reached or reduced, and no data-structure description that would make each rotation O(1). The missing Figure 3 is explicitly referenced for the nonzero patterns that justify the 10 flops per rotation, so the complexity claim cannot be verified from the text. The experiments in §4 and Table 1 do show BGU running fast and with small norm residuals, and the existence of a public repository is real independent evidence that some implementation exists; however, the manuscript itself does not enable replication or a mathematical check. The reader's REJECT verdict is therefore justified. My proposed concrete test—instrumenting the public code to count rotations and per-rotation work—would settle whether the missing algorithm actually achieves the claimed complexity. If the test confirms Θ(n^2) rotations with bounded per-rotation work, the central numerical claim is supported, though the manuscript would still need a proper algorithm specification. If it does not, the central claim fails. Since the concern aligns with the reader's weakest assumption and supports the same verdict, I recommend no change to the reader's decision.","tokens_in":18016,"tokens_out":4242,"duration_ms":52001,"concrete_test":"Obtain the public implementation from ref [7] and instrument BGU to count (a) the number of Givens rotations performed and (b) the number of nonzero matrix entries touched per rotation. Run it on random dense b+ and c+ for n = 64, 128, ..., 4096 and also on the SuiteSparse examples in Table 1. If the total rotation count scales as Θ(n^2) and per-rotation work stays bounded by a small constant on every successful run, the complexity claim is confirmed; if the count scales worse, or runs fail or require fill-in beyond the claimed pattern, the central quadratic-scaling claim is not supported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"BGU is the paper's advertised main contribution, but §3.4 does not define it. It states that phase 1 alternately eliminates elements of b+ and c+ while turning B into a quaddiagonal, and that phase 2 reduces the quaddiagonal to bidiagonal; 'Algorithm 2' is only a caption. There is no pseudocode, no statement of which rotations are chosen, no data layout, and no termination argument. The complexity estimate is a heuristic: 'there are up to n−1 elements in each of b+ and c+ that cause a bulge. A bulge in turn requires at most n rotations ... phase 1 requires O(2n^2) flops.' This assumes each bulge is chased in at most n rotations and each rotation touches only the shaded O(1) entries of the missing Figure 3. Both are unproved; if a bulge interacts with later bulges or requires more than O(1) entries to be updated, the total cost is no longer quadratic. The timing and accuracy experiments in §4 use an implementation, but the paper does not specify enough to reproduce or audit it. Because the core claim—'quadratic scaling with ~10 flops per rotation'—is precisely this algorithm's property, the absence of specification is a load-bearing gap. The BHU algorithm is specified and Theorem 3.1 gives it formal support, but BGU, not BHU, is the headline contribution.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":18444,"tokens_out":6577,"duration_ms":71374,"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":[{"comment":"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.","section":"§3.4"},{"comment":"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.","section":"§3.4"},{"comment":"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.","section":"§4, Table 1, Eq. (4.8)"},{"comment":"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.","section":"§3.3, Algorithm 1"}],"minor_comments":[{"comment":"The citation 'Brandt [4, 3]' should be 'Brand [4, 3]' to match the reference list.","section":"§1.3"},{"comment":"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.","section":"§3.3"},{"comment":"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.","section":"§4.1"},{"comment":"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.","section":"§3.4"}],"recommendation":"major_revision","confidential_remarks":"The decisive issue is that BGU, the advertised main contribution, is not described as an algorithm in the submitted text; the missing figure and missing pseudocode make the O(4n^2) claim impossible to audit. The BHU part is more solid, but the paper cannot be accepted until the BGU algorithm is fully specified and its complexity rigorously proved. I would not reject outright, because the authors may be able to supply the missing material and strengthen the experiments within the scope of a revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Let me give you the short version: this is a plausible paper with one solid result and one advertised result that isn't actually there. The solid piece is Theorem 3.1, a compact WY-type decomposition that decouples the sparse bidiagonal part from a rank-one update under Householder reflectors. It's clean, general, and supports the BHU algorithm, which is actually specified (Algorithm 1) and analyzed. That alone is a real contribution, and I'd cite it.\n\nThe advertised algorithm, BGU, is a different story. Section 3.4 describes it in prose: eliminate elements in b+ and c+, chase bulges, reduce a quaddiagonal to bidiagonal. But there is no pseudocode, no rotation schedule, no termination argument, and the complexity bound relies on unstated assumptions about how many rotations a bulge takes and which entries each rotation touches. 'Algorithm 2' is just a caption. The missing Figure 3 is supposed to carry the argument, and it's not there. So the headline claim—O(4n^2) with ~10 flops per rotation—is an assertion, not a result.\n\nThe experiments don't rescue it. The accuracy metric is |∥A∥_F − ∥B∥_F|, which only checks that the Frobenius norm is preserved; it says nothing about whether the updated factorization gives a good low-rank approximation or tracks the correct subspace. And the SuiteSparse benchmark compares BGU against zgebrd on a rank-one update, which looks like an apples-to-oranges comparison unless the initial bidiagonal factorization is free for BGU but not for zgebrd. The MovieLens comparison to Brand's incremental SVD is more relevant, but again the metric is too weak to support 'similarly accurate'.\n\nThe paper also has missing supplements and some sloppy references, but those are minor. The main issue is structural: the central algorithm is not specified. This is not a matter of polish; a referee cannot verify the complexity claim or reproduce the results from the paper alone.\n\nSo how would I handle it? I'd send it to review. Theorem 3.1 and BHU are worth refereeing, and the authors are credible enough that the BGU idea might be fixable. But I'd expect major revision: full specification of BGU, correctness proof, and a real evaluation of approximation quality, not just norm matching. If they can't provide that, the paper should not be accepted. As it stands, I'd call it a promising but incomplete manuscript.","headline":"Theorem 3.1 is real, BGU is a sketch: the paper deserves a referee but needs major revision before it can be accepted.","tokens_in":18817,"tokens_out":3977,"would_cite":true,"duration_ms":45652,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65F55","68T09","65Y20"],"pacs":[],"model":"deepseek-v4-flash","headline":"Bidiagonal factorizations can be updated in quadratic time after low-rank data changes, matching SVD accuracy in streaming applications.","keywords":["streaming data","bidiagonal factorization","low-rank updates","Givens rotations","Householder compact WY","subspace tracking","incremental SVD","truncated SVD"],"falsifier":"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.","tokens_in":17967,"feed_emoji":"⚡","tokens_out":6359,"duration_ms":64100,"temperature":0.7,"pith_summary":"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.","feed_headline":"Bidiagonal factorizations update in quadratic time, not cubic","feed_subtitle":"Givens rotations refresh each SVD-type decomposition in ~10 flops, tracking large recommendation and network streams.","key_machinery":"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.","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Establishes that the truncated SVD is the best low-rank approximation and gives the Frobenius error formula that motivates the bidiagonal-decomposition error bounds.","marker":"[15]"},{"why":"Defines Golub-Kahan bidiagonalization, the two-recurrence sparse method that the new algorithms are compared against conceptually.","marker":"[16]"},{"why":"Introduces the incremental thin-SVD updating method used as the baseline in the recommendation experiment.","marker":"[4]"},{"why":"Supplies the randomized power iteration method, datasets, and test setup for the link-prediction comparison.","marker":"[12]"},{"why":"Provides the LAPACK bidiagonalization routine used as the standard dense baseline in the benchmarking table.","marker":"[1]"},{"why":"Introduces the WY representation for products of Householder matrices that the Householder updating method extends.","marker":"[2]"},{"why":"Gives the compact WY analytic formula for products of Householder reflectors that the Householder representation relies on.","marker":"[36]"}],"fun_headline_variants":["Bidiagonal refresh in ~10 flops per rotation","Quadratic-time SVD updates replace cubic recompute","Householder compact WY halves memory for SVD streams","Givens rotations cut SVD update cost to quadratic","Streaming low-rank updates: bidiagonal beats SVD recompute"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Bidiagonal refresh in ~10 flops per rotation","Quadratic-time SVD updates replace cubic recompute","Householder compact WY halves memory for SVD streams","Givens rotations cut SVD update cost to quadratic","Streaming low-rank updates: bidiagonal beats SVD recompute"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00017,"raw_usage":{"total_tokens":1092,"prompt_tokens":718,"completion_tokens":374,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":462,"completion_tokens_details":{"reasoning_tokens":305}},"tokens_in":462,"tokens_out":374,"duration_ms":4765,"temperature":1.0,"reasoning_tokens":305,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T11:21:14.296260+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Golub and W","cited_arxiv_id":null,"evidence_quote":"Defines Golub-Kahan bidiagonalization, the two-recurrence sparse method that the new algorithms are compared against conceptually."},{"cited_title":"Brand, Fast low-rank modifications of the thin singular value decomposition , Linear Algebra and its Applications, 415 (2006), pp","cited_arxiv_id":null,"evidence_quote":"Introduces the incremental thin-SVD updating method used as the baseline in the recommendation experiment."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the randomized power iteration method, datasets, and test setup for the link-prediction comparison."},{"cited_title":"Anderson, Z","cited_arxiv_id":null,"evidence_quote":"Provides the LAPACK bidiagonalization routine used as the standard dense baseline in the benchmarking table."},{"cited_title":"Bischof and C","cited_arxiv_id":null,"evidence_quote":"Introduces the WY representation for products of Householder matrices that the Householder updating method extends."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the compact WY analytic formula for products of Householder reflectors that the Householder representation relies on."}],"review_version":1}