{"id":"88a16d1e-91c5-468b-844e-d811dcde37ed","arxiv_id":"2508.07553","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A blocked randomized low-rank approximation algorithm reveals numerical rank adaptively to a spectral threshold, with new bounds on deflation accuracy.","lead":"This paper introduces a blocked randomized algorithm for approximating large matrices with a guaranteed accuracy threshold, stopping adaptively once the error is small enough. It is positioned for image compression, text retrieval, and video background estimation.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.4 is conditional on a gap inequality the algorithm never verifies; Tables 4.2–4.3 show failures precisely where that inequality is questionable.","rationale":"The reader's weakest-assumption analysis identifies the strong spectral gap and exact arithmetic as the main fragile points, and cites the empirical failure of blarank on Type II matrices. I agree with that diagnosis, but I would sharpen it: the deeper issue is that the algorithm never computes or verifies the distance ε that appears in the theorem, and the stopping criterion is not proven to detect the true crossing point. Thus the theorem, while correct as a conditional statement, does not by itself deliver the paper's advertised guarantee of adaptive rank revealing. The proposed instrumented experiment would directly separate 'the theorem's hypotheses are violated' from 'the theorem is insufficient.' Since the reader's verdict is already CONDITIONAL and my concern is an elaboration rather than a contradiction, I recommend UNCHANGED.","tokens_in":22269,"tokens_out":13131,"duration_ms":150478,"concrete_test":"Reproduce the Type II experiment of Table 4.2 and the Cranfield θ=20% row of Table 4.3 with instrumented blarank/sblarank. After each block, compute the true ε_i = d(R(Q[i]), Rθ(A)) from the full SVD and test the hypotheses of Theorem 3.4/Corollary 3.5: σ_k − ε_i‖A‖₂ > θ > σ_{k+1} + ε_i‖A‖₂ (and, for each intermediate block, σ_{bi} − σ_{bi+1} > 2ε_i‖A‖₂). If every wrong-rank row violates the inequality exactly at the step where the stopping test fires, while every correct-rank row satisfies it, then the theoretical result is a conditional guarantee whose hypotheses the algorithm does not verify, and the paper should present it as such. If any wrong-rank row satisfies the inequality, then the theorem itself is insufficient and needs strengthening.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing guarantee is Theorem 3.4/Corollary 3.5: if the computed basis satisfies ε = d(R(Q), Rθ(A)) < 1 and the two-sided gap σ_k − ε‖A‖₂ > θ > σ_{k+1} + ε‖A‖₂ holds, then each deflation step reduces the numerical rank by exactly b. The proof of this conditional statement appears mathematically sound, but the paper never establishes that the algorithm's Q actually satisfies these hypotheses, nor that the stopping rule detects them. The only randomized bound supplied for ε is (3.3): ε ≤ (σ_{k+1}/σ_b)^{2q+1} ‖Ω₂Ω₁⁻¹‖. For square Gaussian Ω₁, ‖Ω₂Ω₁⁻¹‖ is heavy-tailed and not controlled uniformly; for the paper's own Type II matrices the adjacent ratio σ_{b+1}/σ_b is about 0.75 when b=10, so even with q=2 the resulting ε bound is not guaranteed to sit below the needed margin. Moreover, the stopping rule at Algorithm 2.3/2.4 line 11 uses eigenvalues of Q_i^T A A^T Q_i; no theorem shows that a crossing below θ in this projected matrix coincides with the true numerical rank unless the full-block hypotheses of Theorem 3.4/Corollary 3.5 are already satisfied. The numerical evidence exposes the gap: in Table 4.2, blarank returns rank 22, 29, or 24 instead of 20 with range error 1.00, and in Table 4.3, sblarank at θ=20% of ‖A‖ on Cranfield returns rank 19 instead of SVD's 25. These are exactly heavy-tail or slowly-decaying cases where the theorem's spectral-gap condition is most fragile. The finite-precision stabilization via reorth2 is empirical only; no rounding-error analysis is given. Thus the central claim that the algorithm reliably 'determines the right numerical rank' is not fully supported by the theory as stated.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes two blocked adaptive randomized algorithms, blarank (Algorithm 2.3) and sblarank (Algorithm 2.4), for fixed-threshold low-rank matrix approximation. The basis Q of the approximate numerical range Rθ(A) is built block by block through an implicit deflation procedure with power iteration. The main theoretical results (Theorem 3.2, Theorem 3.4, Corollary 3.5, Theorem 3.6) give subspace-distance and error bounds, and prove that under a spectral-gap condition the deflated matrix has numerical rank reduced by exactly the block size b. Numerical experiments on synthetic matrices, information-retrieval data, image compression, and background estimation compare the algorithms with lansvd/PROPACK and larank.","tokens_in":22738,"tokens_out":8564,"duration_ms":93350,"significance":"The algorithmic idea is attractive and potentially useful: it is pass-efficient, avoids oversampling, uses implicit power iteration, and is built on existing rigorous randomized subspace bounds. The conditional perturbation theorem (Theorem 3.4) is a plausible and useful structural result. The paper explicitly builds on external benchmarks (Saibaba 2019, Gu 2015, Lee-Li-Zeng 2009) and contains no fitted constants, so there is no circularity concern. However, the central guarantee is not connected to the implemented stopping rule, and the paper's own experiments show failures exactly in the heavy-tailed cases emphasized in the introduction. Consequently, the contribution is promising but the main claims are not yet fully established.","major_comments":[{"comment":"The rank-decrease guarantee is conditional on ε = d(R(Q1), Rθ(A)) and on the two-sided gap σk − ε‖A‖₂ > θ > σk+1 + ε‖A‖₂. The paper never proves that the Q produced by Algorithm 2.3 or 2.4 satisfies these hypotheses, nor that the algorithm can verify them. In particular, the stopping rule at Algorithm 2.3/2.4 line 11 checks eigenvalues of Q_i^T A A^T Q_i, but no theorem shows that a crossing below θ² in this projected matrix coincides with rankθ(P⊥_i A) = rankθ(A) − bi. The theorem is therefore not connected to the actual stopping criterion. A theorem stating the exact conditions under which the line-11 test yields the correct rank, together with a high-probability bound on ε for the actual iterates, is needed.","section":"§3, Theorem 3.4 and Corollary 3.5; Algorithms 2.3/2.4"},{"comment":"On Type II matrices, the un-stabilized blarank returns computed ranks 22, 29, 24, 25 instead of the true rank 20 (rows q = 1, 2, 3; b = 10, 20), with range error 1.00. This directly contradicts the paper's claim that the algorithm reveals the correct numerical rank, in exactly the heavy-tail regime the introduction identifies as motivating the work. The text acknowledges that 'larank, blarank fail' in some situations but does not reconcile this with Theorem 3.4 / Corollary 3.5. The theorem's gap hypothesis uses ratios such as σ_{k+1}/σ_b, while the actual first-block quality depends on the worse ratio σ_{b+1}/σ_b ≈ 0.75 for b = 10; this mismatch needs to be addressed explicitly.","section":"§4, Table 4.2"},{"comment":"The method that works empirically in the difficult cases is sblarank, which differs from blarank only by the reorth2 twice-orthogonalization step. The paper states that sblarank is 'mathematically equivalent' to blarank, but no rounding-error analysis is given to show that reorth2 maintains the assumptions ε < 1 and the spectral-gap condition in finite precision. Moreover, Table 4.3 shows that even sblarank returns rank 19 at θ = 20%‖A‖ on Cranfield while the SVD has numerical rank 25; the theoretical results do not cover this regime. Thus the reliability of the actually recommended algorithm is currently supported only empirically, and the theoretical claims need to be narrowed or supplemented by a stability analysis.","section":"§2, Algorithm 2.4; §4, Table 4.3"}],"minor_comments":[{"comment":"The indexing after applying Lemma 3.3 mixes j and b: the line 'σ′_{k−j+1}=σ′_{k−b+2}=...=σ′_k=0' should use a single index (j = b), and later 'ˇσ_{k−j+1}' should be 'ˇσ_{k−b+1}'. This makes the proof harder to follow.","section":"§3, Theorem 3.4 proof"},{"comment":"The eigenvalue check writes 'ˆΛ(t, t)' but should be 'ˆΛ_i(t, t)' to match Algorithm 2.3 and the preceding line.","section":"Algorithm 2.4, line 11"},{"comment":"The column structure of these tables is difficult to parse (especially the svd and larank columns). Please state explicitly, for each column, the method and its parameters, and list the true SVD rank used for comparison.","section":"§4, Tables 4.3 and 4.4"},{"comment":"The sentence 'Flop counting is a necessarily crude approach...' appears to be an incomplete quote and the preceding sentence is cut off ('however, it does not ne cessarily mean larank is the most efficient, since'). Please complete or remove the dangling text.","section":"§2, complexity paragraph"}],"recommendation":"major_revision","confidential_remarks":"The paper is within scope for math.NA and the algorithmic idea is worth pursuing. The key gap is not a mathematical contradiction in the conditional theorem itself, but the lack of a bridge from the analysis to the implemented stopping rule, together with experimental failures that conflict with the stated guarantees. I believe this can be fixed by a substantive revision, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take on Liu-Yu.\n\nWhat's actually new: the blocked adaptive deflation scheme. Instead of larank's one-vector-at-a-time deflation, they build Q block by block and stop when the projected eigenvalues cross below the squared threshold. The load-bearing result, Theorem 3.4, is a conditional perturbation statement: if the computed block basis Q1 is within ε of the true numerical range Rθ(A) and the two-sided gap σ_k − ε‖A‖₂ > θ > σ_{k+1} + ε‖A‖₂ holds, then deflating by Q1 reduces the numerical rank by exactly b and keeps the tail singular values within ε‖A‖₂. That's a clean, useful theorem, and the proof outline is credible despite some indexing slips. Corollary 3.5 extends it to blocks. The complexity analysis is sensible, and the experiments show sblarank is fast on images and video. The benchmarks are external, and the bounds have no fitted constants—good practice.\n\nWhere it gets soft. The theorem's hypotheses are never shown to hold for the algorithm's actual output. The only random bound for ε, Theorem 3.2, involves ‖Ω₂Ω₁⁻¹‖, which is heavy-tailed and can push ε over the needed gap. For Type II matrices, σ_{b+1}/σ_b is about 0.75, so the promised ε is not small enough to make the theorem bite. And indeed blarank fails precisely there: Table 4.2 gives rank 22–29 instead of 20 and range error 1.00. The variant that actually works, sblarank, uses reorth2, which is only empirically justified and is not covered by the analysis. The stopping rule also has no theorem: no result shows that the first projected eigenvalue below θ² marks the true numerical rank unless the full-block hypotheses already hold. The abstract overstates the case: it promises \"more reliable\" behavior than the Lanczos method and Lee-Li-Zeng, but Table 4.3 shows sblarank returning rank 19 when the SVD gives 25. Those are real gaps, not manufactured ones.\n\nThe paper is still worth referee time. The idea is novel, the conditional analysis is a legitimate contribution, and the failures are honestly visible in the tables. What's missing is a bridge—a computable check of the gap condition, a probabilistic analysis of the stopping rule, or at least a reworked abstract that doesn't promise more than the theory and experiments support.\n\nWho is this for? Researchers in randomized NLA and practitioners who need an adaptive spectral-threshold rank finder. I'd bring it to a reading group and would send it to review, but I wouldn't cite it yet in my own work; the gap condition needs to be addressed first.","headline":"Genuinely novel blocked adaptive deflation with spectral stopping, but the main theorem is conditional on a gap the algorithm never verifies and the abstract outruns the data.","tokens_in":23192,"tokens_out":5557,"would_cite":false,"duration_ms":57361,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W20","60B20","15A18"],"pacs":[],"model":"deepseek-v4-flash","headline":"An adaptive randomized algorithm provably finds the numerical rank of a large matrix by deflating it block by block, with spectral and Frobenius error bounds.","keywords":["randomized low-rank approximation","rank-revealing","fixed threshold","numerical range","deflation","randomized QB","singular value thresholding","background estimation"],"falsifier":"Run blarank (Algorithm 2.3, without twice-orthogonalization) on the Type II synthetic matrix of Section 4.1 at $q=1$, $b=20$: it reports computed rank 22 or 800 instead of the true 20 and a range error of 1.00, showing that under floating-point arithmetic the deflation step fails to preserve the numerical rank whenever the tail singular values decay slowly.","tokens_in":22196,"feed_emoji":"🧮","tokens_out":8670,"duration_ms":82720,"temperature":0.7,"pith_summary":"This paper aims to settle a practical question: given only a threshold $\\theta$, how do you compute, in one adaptive pass, the rank of a large matrix above $\\theta$ and an orthonormal basis for the corresponding subspace? Existing fixed-precision randomized methods stop on Frobenius-norm residuals, which misbehave when the singular values have a heavy tail, and the standard sparse-SVD package cannot reveal the rank automatically. The authors propose a blocked randomized deflation: build the basis block by block, strip each block off with $(I-QQ^T)A$, and stop when the computed eigenvalues of the small matrix $Q^TAA^TQ$ drop below $\\theta^2$. Their central theorem says that if the computed block is within distance $\\varepsilon<1$ of the true numerical subspace and the gap between the last retained and first discarded singular value exceeds $2\\varepsilon\\|A\\|_2$, the deflated matrix still has exactly $\\mathrm{rank}_\\theta(A)-b$ and preserves all sub-threshold singular values to within $\\varepsilon\\|A\\|_2$. That guarantee is what makes the stopping rule trustworthy, and it is backed by experiments on synthetic data, document retrieval, image compression, and video background estimation.","feed_headline":"Randomized deflation finds the right numerical rank, block by block","feed_subtitle":"A spectral-gap guarantee lets the algorithm stop exactly where singular values cross the threshold.","key_machinery":"The object that carries the argument is the deflated matrix $B = (I - Q_\\ell Q_\\ell^T)A$ built from a block $Q_\\ell$ obtained by randomized subspace iteration with power $q$, and the metric that controls everything is the subspace distance $\\varepsilon = d(R(Q_\\ell), R_\\theta(A))$ between the computed block and the true numerical range of the current residual. The crucial inequality is that the singular values of $B$ differ from those of the exact projection onto the true subspace by at most $\\varepsilon\\|A\\|_2$, so a spectral gap larger than $2\\varepsilon\\|A\\|_2$ forces exactly $b$ singular values to fall below $\\theta$ and keeps the tail intact. The twice-orthogonalization operator $\\mathr","core_discovery":"The central claim is that numerical rank can be revealed by recursion without ever computing the full SVD. Theorem 3.4 states that if a computed block basis $Q_1$ satisfies $\\varepsilon = d(R(Q_1), R_\\theta(A)) < 1$ and the threshold $\\theta$ satisfies $\\sigma_k - \\varepsilon\\|A\\|_2 > \\theta > \\sigma_{k+1} + \\varepsilon\\|A\\|_2$, then $B = (I - Q_1Q_1^T)A$ keeps every singular value of $A$ below $\\theta$ with absolute error at most $\\varepsilon\\|A\\|_2$, and $\\mathrm{rank}_\\theta(B) = \\mathrm{rank}_\\theta(A) - b$. The proof splits $Q_1 = \\check{Q}_1 + \\ddot{Q}_1$ into its projection onto the numerical range and a tail contamination of norm $\\varepsilon$, shows the numerical-range projection $\\","pith_inferences":["The proofs assume exact arithmetic; the empirical failure of blarank on Type II matrices suggests the twice-orthogonalization in sblarank is not a cosmetic stabilizer but a load-bearing component for floating-point correctness, and a roundoff analysis would be a natural extension.","A testable consequence of Theorem 3.4 is that the maximum tolerable gap violation is $2\\varepsilon\\|A\\|_2$; for heavy-tailed distributions, increasing $q$ or shrinking the block size should shrink $\\varepsilon$ below the gap, something the experiments support but the paper does not prove.","The error bound $|\\tilde{\\sigma}_j - \\sigma_{b(\\ell-1)+j}| \\le \\varepsilon_{\\ell-1}\\|A\\|_2$ suggests a cheaper stopping rule than the eigenvalue test used in the algorithms, worth testing as an alternative termination criterion.","The deflation view connects directly to approximate singular value thresholding: replacing the exact SVT step by one application of sblarank yields a randomized proximal operator whose accuracy is controlled by the same gap condition."],"forward_implications":["For any matrix satisfying the gap condition, sblarank returns the exact numerical rank and an orthonormal basis of the numerical range, with absolute error in the retained singular values controlled by $\\varepsilon\\|A\\|_2$.","The spectral residual $\\|(I-QQ^T)A\\|_2$ is bounded in terms of $\\sigma_{k+1}$ plus gap-dependent factors, giving a reliable stopping criterion even when Frobenius-based criteria fail on heavy-tailed singular value distributions.","Each block costs $O(mnb)$ per pass plus low-order terms, so the total cost scales like $O(mnr)$ with $r$ the numerical rank, comparable to the blocked randQB family but with rank revealing built in.","The two-sided bounds on the singular values of $Q_\\ell^T A$ mean the deflated randomized approximation can serve as a cheap approximate singular value thresholding step inside optimization loops such as robust PCA."],"supporting_citations":[{"why":"Supplies the randomized range-finder prototype and the residual spectral-norm estimate that motivates the adaptive stopping rule.","marker":"[15]"},{"why":"Supplies the blocked randQB algorithmic framework that blarank and sblarank extend with deflation.","marker":"[24]"},{"why":"Supplies the deflation rank-reduction lemma (Lemma 3.3) and the larank algorithm used as a comparison baseline.","marker":"[18]"},{"why":"Supplies the randomized subspace iteration bounds and canonical-angle estimates used in Theorem 2.1.","marker":"[29]"},{"why":"Supplies the tail bound for Gaussian matrices (Lemma 3.1) and the low-rank error bounds used throughout Section 3.","marker":"[14]"},{"why":"Supplies the implicitly-restarted randQB variant whose cost model the paper compares with its own.","marker":"[32]"},{"why":"The reference sparse SVD package used as the Lanczos-based comparison baseline.","marker":"[17]"}],"fun_headline_variants":["Block-by-block deflation reveals numerical rank without full SVD","Adaptive randomized rank-revealing: stop exactly at the threshold","Recursive deflation outperforms Lanczos for large-matrix low-rank","Pass-efficient low-rank approximation with provable error bounds"],"cache_read_input_tokens":2816,"weakest_assumption_plain":"The whole guarantee rests on a strong spectral gap: the gap between the last singular value above the threshold and the first one below it must be larger than twice the distance from the computed basis to the true numerical subspace, so the computed basis must be quite accurate.","fun_headline_variants_meta":{"raw":{"variants":["Block-by-block deflation reveals numerical rank without full SVD","Adaptive randomized rank-revealing: stop exactly at the threshold","Recursive deflation outperforms Lanczos for large-matrix low-rank","Pass-efficient low-rank approximation with provable error bounds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000373,"raw_usage":{"total_tokens":1846,"prompt_tokens":776,"completion_tokens":1070,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":520,"completion_tokens_details":{"reasoning_tokens":1010}},"tokens_in":520,"tokens_out":1070,"duration_ms":8768,"temperature":1.0,"reasoning_tokens":1010,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T22:01:28.688637+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run blarank (Algorithm 2.3, without twice-orthogonalization) on the Type II synthetic matrix of Section 4.1 at $q=1$, $b=20$: it reports computed rank 22 or 800 instead of the true 20 and a range error of 1.00, showing that under floating-point arithmetic the deflation step fails to preserve the numerical rank whenever the tail singular values decay slowly.","supporting_citations":[{"cited_title":"pa ges 15","cited_arxiv_id":null,"evidence_quote":"Supplies the randomized range-finder prototype and the residual spectral-norm estimate that motivates the adaptive stopping rule."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the blocked randQB algorithmic framework that blarank and sblarank extend with deflation."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the deflation rank-reduction lemma (Lemma 3.3) and the larank algorithm used as a comparison baseline."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the randomized subspace iteration bounds and canonical-angle estimates used in Theorem 2.1."},{"cited_title":"Chandrasekaran and I","cited_arxiv_id":null,"evidence_quote":"Supplies the tail bound for Gaussian matrices (Lemma 3.1) and the low-rank error bounds used throughout Section 3."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the implicitly-restarted randQB variant whose cost model the paper compares with its own."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The reference sparse SVD package used as the Lanczos-based comparison baseline."}],"review_version":1}