{"id":"0969e591-fe7d-465d-8968-40a31556ca8f","arxiv_id":"2506.15660","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A hybrid randomized estimator that mixes a power-method ratio with a Gaussian norm yields tighter probabilistic upper bounds on matrix spectral norms with the same number of matrix-vector products.","lead":"This paper proposes a randomized estimator, Counterbalance, that combines a power-method ratio with a Gaussian matvec to give probabilistic upper bounds on a matrix's spectral norm using only matrix-vector products. The estimator needs fewer matvecs for the same confidence and produces tighter bounds than standard Vanilla and Dixon estimators on tested synthetic and real-world matrices.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Table 1's θ_cb values appear inconsistent with Theorem 1's stated bound; the δ=0.1 entry θ_cb=1.28 does not satisfy the printed g(θ,ρ) at ρ=1.5.","rationale":"The reader's weakest assumption was that the numerical maximization producing Table 1 is unreported and unverified. A stronger, more load-bearing problem is that the printed Theorem 1 bound and Table 1 appear mathematically inconsistent: at θ=1.28 and ρ=1.5, the stated g(θ,ρ) integral is approximately 0.32, not ≤0.1. Thus the realizable parameter selection, which is essential to the estimator's probabilistic upper-bound guarantee, is not supported by the theorem as written. This differs from the reader's concern about missing code: even with perfect code and certificates, Table 1 could not be obtained by maximizing the printed expression. The issue is fixable in principle (correcting the case split or proof and recomputing Table 1), but as submitted the central claim lacks a valid theoretical basis. For this reason the verdict should move from CONDITIONAL to REJECT, pending correction of the theorem/table inconsistency and independent verification of the numerical parameters.","tokens_in":12231,"tokens_out":39386,"duration_ms":344848,"concrete_test":"Evaluate the third piece of g(θ,ρ) in Theorem 1 (Eq. 14) with high-precision adaptive quadrature at θ=1.28, ρ=1.5, and maximize it over ρ∈[1,1+1.28^{-2}]; if the maximum exceeds 0.1, the δ=0.1 row of Table 1 is invalid under the stated theorem. Repeat for the δ=0.05 row at θ=1.58 with ρ just below 1+1.58^{-2}. This single computational check settles whether the reported θ_cb values follow from the published bound.","verdict_should_be":"REJECT","load_bearing_attack":"The realizable parameters in Table 1 are the load-bearing link between Theorem 1 and the paper's numerical claims. For θ=1.28 (the δ=0.1 row), the third piece of g(θ,ρ) in Eq. (14) applies for ρ in [1, 1+θ^{-2}], e.g., ρ=1.5. Direct quadrature of the printed integral ∫_0^{θ^{-2}} χ_1^2((ρ-1)t/(1-t)) p^{(1,0)}((θ^{-2}-t)/ρ) dt at θ=1.28, ρ=1.5 gives a value around 0.32, far above 0.1. Even if the missing 1/ρ factor in the density change-of-variables is supplied, the value remains above 0.1. Since ρ=1.5 lies in the maximization interval [1,7], the maximization claimed in Section 4.1 could not produce θ_cb=1.28 for δ=0.1 under the theorem as printed. Similar discrepancies appear for other rows when ρ is just below 1+θ^{-2}. This is not merely an unreported numerical maximization; it is an internal inconsistency between Theorem 1 and Table 1. The stated probabilistic guarantee P(T_cb(θ,X)≤||A||_2)≤δ is therefore not established for low effective-rank matrices with the published parameter values. The proof's case handling appears to have an error (possibly swapped case conditions or a missing normalization), so the theorem and the table cannot both be correct as written.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a randomized estimator of the spectral norm of an implicit matrix A using three matvec operations: the Counterbalance estimator T_cb(θ,X) = θ sqrt( (||A^T A X1|| / ||A X1||)^2 + ||A X2||^2 ), where X1 and X2 are independent standard Gaussian vectors. Theorem 1 gives a three-case upper bound g(θ,ρ) on the underestimation probability depending only on the effective rank ρ, and the authors state that they numerically maximize this bound over ρ∈[1,7] to select θ for a prescribed underestimation level δ, producing Table 1. They compare the estimator in the realizable parameter regime with the Vanilla and Dixon estimators on synthetic matrices, a Hilbert matrix, a Fréchet derivative matrix, and a ResNet convolutional-layer Jacobian, reporting smaller means and lower MAE at fixed δ=0.05.","tokens_in":12590,"tokens_out":12902,"duration_ms":120126,"significance":"The estimator idea is interesting and the proof framework is non-circular: the main bound in Theorem 1 is derived from first principles using an external extremal theorem for Gaussian quadratic forms, Jensen's inequality, and a freezing argument, and no free parameter is fitted to the test data. If the parameter table and the numerical comparisons can be corrected and made reproducible, the method would be a useful cheap upper-bound estimator for low effective-rank matrices, which are common in deep learning and inverse problems. However, as submitted the central realizable guarantee is not established because the reported θ values appear inconsistent with the printed bound, and the numerical maximization is neither documented nor shipped as code.","major_comments":[{"comment":"The reported realizable parameters θ_cb are inconsistent with the printed bound g(θ,ρ). For the δ=0.1 row, θ_cb=1.28 gives θ^{-2}=0.610, so ρ=1.5 lies in the third branch of (14), since 1<1.5<1+θ^{-2}=1.610. Direct quadrature of the printed integral ∫_0^{θ^{-2}} χ_1^2((ρ-1)t/(1-t)) p^{(1,0)}((θ^{-2}-t)/ρ)dt at these values yields approximately 0.33, and even after supplying the 1/ρ factor that the change of variables in A.1 (Eq. (22)) introduces, the value is about 0.22. Both are far above δ=0.1. Therefore the maximization over ρ∈[1,7] asserted in Section 4.1 cannot produce θ_cb=1.28 for δ=0.1, and similar checks for the other rows show that Table 1 is not a valid realization of the printed bound. Consequently the guarantee P(T_cb(θ,X)≤||A||_2)≤δ is not established as stated for low effective-rank matrices.","section":"Section 4.1, Eq. (14), Table 1"},{"comment":"The paper states that (14) is maximized over ρ∈[1,7] \"with high accuracy\", but no code, data, or numerical certificate is provided. Table 1 is the only bridge between Theorem 1 and the realizable comparisons in Section 5, so this is not an incidental reproducibility remark: without a verifiable computation, the reader cannot check that the published θ_cb values satisfy the guaranteed underestimation bound. I would require the authors to release the maximization code or provide a verified interval/certificate for each θ_cb entry.","section":"Section 4.1"},{"comment":"The numerical evidence for the superiority of T_cb over Vanilla and Dixon depends directly on the θ_cb values from Table 1, which are invalid per the first major comment. The empirical densities, δ_real values, and MAE comparisons must be recomputed with θ_cb obtained from a corrected and reproducible maximization before the paper's practical claims can be evaluated. In addition, Tables 2 and 3 report point estimates only; standard errors or confidence intervals for the MAE comparisons should be provided.","section":"Section 5, Tables 2 and 3"}],"minor_comments":[{"comment":"The proof's case labels are reversed relative to Theorem 1: the text labels \"1<ρ≤1+θ^{-2}\" as the Second case and \"1+θ^{-2}≤ρ<7\" as the Third case, while the statement of (14) uses the opposite ordering for its second and third branches.","section":"A.1"},{"comment":"In the change of variables from t to v=(θ^{-2}-t)/ρ, the density p^{(1,0)}((θ^{-2}-t)/ρ)dt should acquire a factor 1/ρ; Eq. (22) omits this factor. The displayed inequality remains an upper bound because ρ≥1, but the derivation should be corrected so the stated bound can be checked numerically.","section":"A.1, Eq. (22)"},{"comment":"The sentence \"This matrix has rank ρ=1.09\" should say \"effective rank\" rather than \"rank\".","section":"Section 5.1"},{"comment":"References [9] and [18] are the same article (Bujanović and Kressner); one duplicate entry should be removed.","section":"References"},{"comment":"There are several typographical errors: \"Tailor expansion\" should be \"Taylor expansion\", \"Kroenecker\" should be \"Kronecker\", and \"disjoin\" should be \"disjoint\".","section":"Throughout"},{"comment":"The caption says the plot compares estimators \"across various structured matrices\", but the figure shows only the rank-2 example from Section 5.1; the caption should be made matrix-specific.","section":"Figure 1"}],"recommendation":"major_revision","confidential_remarks":"The core issue is that the parameter table and the theorem cannot both be correct as printed. Since the estimator and proof framework are plausible and the defect appears fixable by recomputing the table with a transparent, reproducible procedure, I recommend major revision rather than rejection. The authors should also be asked whether the corrected θ_cb values preserve the claimed practical advantage; the current empirical claims cannot be trusted until this is done."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The Counterbalance estimator is a genuinely new way to combine the power-method Rayleigh quotient with a Gaussian norm. The paper is clearly written and the idea has real appeal: for low effective rank, ||A^T A X||/||A X|| is a tight lower bound on the spectral norm, and the second term adds a positive correction. That part is solid.\n\nThe problem is the main theorem. In the proof's second case (small ρ), the step from E_Q[χ_1^2((θ^{-2}-Q)/ρ)] to the integral over P(Q≤t) drops a 1/ρ factor from the derivative of χ_1^2. The printed theorem's third case inherits this missing normalization. This isn't cosmetic: for θ=1.28 (the δ=0.1 entry in Table 1) and ρ=1.5, the printed integral is about 0.32, and even with the 1/ρ restored it's about 0.21. Both are far above 0.1. Since ρ=1.5 lies in the stated maximization interval [1,7], Table 1's θ_cb=1.28 cannot be the value that makes sup_ρ g(θ,ρ) ≤ 0.1. The theorem and the table are internally inconsistent as printed, so the paper's headline guarantee isn't established.\n\nCredit where it's due: the estimator is new relative to Dixon, Halko et al., Hochstenbach, and Bujanović–Kressner; the proof strategy (Szekely's theorem plus Jensen on a concave chi-square CDF) is appropriate; and the numerical experiments on Hilbert, dominant-spectrum, Fréchet, and ResNet Jacobian matrices consistently show the Counterbalance statistic taking smaller values than Vanilla and Dixon at the same matvec budget. That empirical observation may well survive a corrected analysis. The literature review is fair, and the sequential/parallel matvec caveats are honestly reported.\n\nThe soft spots are in proportion. The missing 1/ρ is load-bearing, not a typo: it changes the claimed guarantee. The numerical maximization for θ is described as 'high accuracy' but no code, data, or certificate is provided, which is a reproducibility problem exactly where it matters. The experimental matrix set is small (five matrices), but that would be minor if the theory held.\n\nWho this is for: researchers in randomized numerical linear algebra, especially those using spectral norm bounds for Lipschitz regularization or condition estimation. The paper deserves a serious referee because the idea is novel and the failure is localized: a corrected bound and a recomputed Table 1 could turn it into a publishable paper, provided the corrected bound still shows a real advantage. As it stands, the central claim of a probabilistic upper bound with the advertised θ values is not supported. Send it to review, but expect heavy revision.","headline":"The Counterbalance estimator is a fresh idea, but the main theorem has a missing normalization and Table 1 doesn't match the printed bound; the probabilistic guarantee is not currently established.","tokens_in":13089,"tokens_out":13788,"would_cite":false,"duration_ms":115000,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["15A60","65F35","60E15"],"pacs":[],"model":"deepseek-v4-flash","headline":"A three-matvec Counterbalance estimator gives probabilistic upper bounds on the matrix spectral norm and is tighter than classical randomized baselines.","keywords":["Spectral norm estimation","Randomized numerical linear algebra","Matrix-vector products","Probabilistic upper bounds","Effective rank","Counterbalance estimator","Gaussian quadratic forms","Underestimation probability"],"falsifier":"Recompute $\\sup_{\\rho\\in[1,7]} g(\\theta,\\rho)$ for each Table 1 value with a certified global optimizer or a sufficiently fine grid; if any value exceeds the claimed $\\delta$, the universal tuning table fails. Alternatively, simulate Gaussian draws for matrices with effective ranks sampled across $[1,7]$, count the empirical frequency of $T_{\\mathrm{cb}} \\le \\|A\\|_2$, and check whether it exceeds $\\delta$ by more than sampling error.","tokens_in":12053,"feed_emoji":"📐","tokens_out":12202,"duration_ms":116772,"temperature":0.7,"pith_summary":"The paper proposes a spectral-norm estimator that needs three matrix-vector products and carries a probabilistic guarantee that it stays above the true norm. The core idea is to counterbalance the usual random-vector statistic $\\|AX\\|$ with the ratio $\\|A^{\\top} A X\\| / \\|A X\\|$, which equals the spectral norm for rank-one matrices and stays informative when the effective rank is low. The main theorem bounds the underestimation probability by an explicit function of the effective rank, and the tuning parameter is chosen by maximizing that function, so the user needs no knowledge of the singular values. The result is tighter upper bounds than standard one-vector or max-of-vectors estimates at the same matvec budget, which matters for Lipschitz regularization and condition estimation.","feed_headline":"A three-matvec estimator tightens spectral-norm upper bounds","feed_subtitle":"Two Gaussian draws and one ratio term give a tighter bound while respecting the failure budget.","key_machinery":"The load-bearing object is the Counterbalance statistic itself, a sum of two terms under one square root. The first term, $\\|A^{\\top}AY\\|/\\|AY\\|$, is a Rayleigh-quotient-like ratio that equals $\\|A\\|_2$ when $A$ has rank one; the second term, $\\|AX\\|_2$, is the classical random-vector test statistic that tends to overestimate the norm as the effective rank grows. The proof controls the ratio term through a chi-square bound (Lemma 1), and it controls the remaining Gaussian noise with an extremal result for weighted sums of squared Gaussians, which says $\\sup P(\\sum \\lambda_i \\xi_i^2\\le x)=\\chi_1^2(x)$ for weights summing to one. For $\\rho\\ge7$, the proof partitions the singular values into three blocks with comparable energy, reducing the tail to a $\\chi_4^2$ bound that yields $\\theta^{-4}/8$.","core_discovery":"The central result is Theorem 1: for $A\\in\\mathbb{R}^{m\\times n}$ with effective rank $\\rho=\\|A\\|_F^2/\\|A\\|_2^2$ and independent standard Gaussian vectors $X_1,X_2$, the statistic $T_{\\mathrm{cb}}(\\theta,X)=\\theta\\sqrt{(\\|A^{\\top}AX_1\\|/\\|AX_1\\|)^2+\\|AX_2\\|^2}$ satisfies $P(T_{\\mathrm{cb}}(\\theta,X)\\le\\|A\\|_2)\\le g(\\theta,\\rho)$, with $g$ given piecewise: for $\\rho\\ge 7$ it is $\\theta^{-4}/8$, and for lower $\\rho$ it is an integral involving chi-square distributions. The paper then maximizes $g(\\theta,\\rho)$ over $\\rho\\in[1,7]$ numerically to produce a single table of $\\theta$ values for any matrix and a target underestimation probability $\\delta$. The authors report that with these realizable parameters, Counterbalance gives lower mean estimates and lower mean absolute error than the Vanilla and ratio-max baselines on all tested matrices, including kernels with fast-decaying spectra.","pith_inferences":["A natural extension is to insert several ratio terms $\\|A^{\\top}AX_i\\|/\\|AX_i\\|$ inside the square root; the $\\rho\\ge7$ case already groups singular values into three blocks, so a multi-block version could trade extra sequential matvecs for a smaller $\\theta$.","The numerical maximization in Section 4.1 is the only step of the derivation that is not backed by a proof or delivered code; replacing it with a certified maximizer or an analytic envelope would make the table of $\\theta$ values fully rigorous.","The method's matrix-free nature means it can be plugged directly into Lipschitz-constant estimation for neural networks and condition-number estimation for matrix functions; the paper demonstrates a ResNet Jacobian but stops short of claiming end-to-end gains in either application."],"forward_implications":["With the tabulated $\\theta$, $T_{\\mathrm{cb}}$ is a ready recipe: two sequential matvecs compute $A^{\\top}AX_1$ (via $AX_1$ then $A^{\\top}$), one parallel matvec computes $AX_2$, and the output exceeds $\\|A\\|_2$ with probability at least $1-\\delta$.","On every matrix in the paper's test set, the Counterbalance estimator has smaller mean and lower MAE than the Vanilla and ratio-max baselines at the same budget of three matvecs.","For rank-one $A$, the estimator cannot underestimate: $T_{\\mathrm{cb}}(\\theta,X)\\ge\\|A\\|_2$ with probability one when $\\theta\\ge1$.","The $\\theta$ values are matrix-agnostic: once the numerical maximization over effective rank is accepted, the same table works for any $A$, including unknown implicit matrices.","Repeating the three-matvec block at larger budgets, the estimate stabilizes after about nine matvecs in the experiments and remains below the baselines."],"supporting_citations":[{"why":"Supplies the classical one-vector estimator and the type of probabilistic guarantee (1) that the new estimator refines and compares against.","marker":"[5]"},{"why":"Provides the bound (3) for $\\theta\\|AX\\|_2$ and the randomized power-method background that motivates the Counterbalance construction.","marker":"[6]"},{"why":"Contains Theorem 2, the extremal bound for weighted sums of squared Gaussians used in every case of the proof of Theorem 1.","marker":"[20]"},{"why":"Gives the randomized power-method context behind Lemma 1, which controls the underestimation probability of the ratio term in the estimator.","marker":"[21]"}],"fun_headline_variants":["Three matvecs, tighter spectral-norm upper bounds","Counterbalance: sharper spectral-norm upper bounds","Two Gaussians and one ratio tighten norm upper bounds","Beat the power method for spectral-norm bounds"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the tabulated values of $\\theta$ are obtained by accurately maximizing the Theorem 1 bound over effective rank in $[1,7]$; the paper reports 'high accuracy' but gives no code, data, or optimization certificate, so an inaccurate maximum would void the stated underestimation guarantee.","fun_headline_variants_meta":{"raw":{"variants":["Three matvecs, tighter spectral-norm upper bounds","Counterbalance: sharper spectral-norm upper bounds","Two Gaussians and one ratio tighten norm upper bounds","Beat the power method for spectral-norm bounds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000492,"raw_usage":{"total_tokens":2367,"prompt_tokens":843,"completion_tokens":1524,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":459,"completion_tokens_details":{"reasoning_tokens":1462}},"tokens_in":459,"tokens_out":1524,"duration_ms":12749,"temperature":1.0,"reasoning_tokens":1462,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T19:31:54.474285+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Recompute $\\sup_{\\rho\\in[1,7]} g(\\theta,\\rho)$ for each Table 1 value with a certified global optimizer or a sufficiently fine grid; if any value exceeds the claimed $\\delta$, the universal tuning table fails. Alternatively, simulate Gaussian draws for matrices with effective ranks sampled across $[1,7]$, count the empirical frequency of $T_{\\mathrm{cb}} \\le \\|A\\|_2$, and check whether it exceeds $\\delta$ by more than sampling error.","supporting_citations":[{"cited_title":"Dixon, Estimating extremal eigenvalues and condition numbers of matrices, Siam (1983) 812–814","cited_arxiv_id":null,"evidence_quote":"Supplies the classical one-vector estimator and the type of probabilistic guarantee (1) that the new estimator refines and compares against."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Contains Theorem 2, the extremal bound for weighted sums of squared Gaussians used in every case of the proof of Theorem 1."},{"cited_title":"Martinsson, J","cited_arxiv_id":null,"evidence_quote":"Gives the randomized power-method context behind Lemma 1, which controls the underestimation probability of the ratio term in the estimator."}],"review_version":2}