Pith. sign in

REVIEW 3 major objections 6 minor 23 references

On the Upper Bounds for the Matrix Spectral Norm

T0 review · 3 major / 6 minor · reviewed 2026-08-15 · deepseek-v4-flash

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

Pith's one-line read A three-matvec Counterbalance estimator gives probabilistic upper bounds on the matrix spectral norm and is tighter than classical randomized baselines.

desk verdict 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. read the letter →

arxiv 2506.15660 v1 pith:TPS2N6EY submitted 2025-06-18 math.NA cs.LGcs.NAmath.STstat.TH

Alexey Naumov , Maxim Rakhuba , Denis Ryapolov , Sergey Samsonov This is my paper · ORCID
classification math.NAcs.LGcs.NAmath.STstat.TH MSC 15A6065F3560E15
keywords SpectralnormestimationRandomizednumericallinearalgebraMatrix-vectorproductsProbabilisticupperboundsEffectiverankCounterbalanceestimatorGaussianquadraticformsUnderestimationprobability
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 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.

What carries the argument

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$.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

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

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 6 minor

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.

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 (3)
  1. [Section 4.1, Eq. (14), Table 1] 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.
  2. [Section 4.1] 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.
  3. [Section 5, Tables 2 and 3] 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.
minor comments (6)
  1. [A.1] 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.
  2. [A.1, Eq. (22)] 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.
  3. [Section 5.1] The sentence "This matrix has rank ρ=1.09" should say "effective rank" rather than "rank".
  4. [References] References [9] and [18] are the same article (Bujanović and Kressner); one duplicate entry should be removed.
  5. [Throughout] There are several typographical errors: "Tailor expansion" should be "Taylor expansion", "Kroenecker" should be "Kronecker", and "disjoin" should be "disjoint".
  6. [Figure 1] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the Counterbalance estimator and its bound are derived from external probabilistic results, and the theta values are chosen from a theoretical bound rather than fitted to data.

full rationale

The paper's central derivation is self-contained relative to its stated inputs. The estimator T_cb(θ,X) in Eq. (13) is defined from two independent Gaussian vectors and the matrix A, with no fitted parameter. Theorem 1's bound g(θ,ρ) in Eq. (14) is proved in Appendix A.1 using an external theorem (Theorem 2 from Szekely [20]) and an auxiliary Lemma 1 for the ratio term; neither result is authored by the present authors, and neither is equivalent to the final bound by construction. The parameter θ is selected in Section 4.1 by numerically maximizing the derived bound g(θ,ρ) over ρ∈[1,7] and then inverting it at a target δ. This is a computation based on the paper's own theorem, not a fit to the test matrices, so the numerical comparisons in Section 5 do not reduce to fitted inputs. There is no self-citation carrying a load-bearing premise, no ansatz smuggled in via prior work of the same authors, and no known result merely renamed. The skeptic's observation that Table 1 may be numerically inconsistent with Eq. (14) at some ρ would be a correctness or reproducibility concern, not a circularity: even if the maximization were inaccurate, the derivation chain would still not be circular. The only mild structural point is that the bound depends on effective rank and the method removes this dependence by maximization; this is a legitimate analytical step rather than a circular one, because the estimator itself is agnostic to ρ. Accordingly, the circularity score is 0.

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

The central result is a new statistic whose analysis uses a published extremal theorem for Gaussian quadratic forms and a numerical maximization that is not independently reproducible. No data-fitted parameters enter the estimator; theta is a user-set confidence parameter.

assumptions (3)
  • standard math Theorem 2 of Szekely [20]: sup over weights lambda_i >= 0, sum lambda_i = 1 of P(sum lambda_i xi_i^2 <= x) = chi_1^2(x) for x in [0,1].
    Used in the proof of Theorem 1 (Appendix A.1) to replace weighted chi-squared sums by a single chi-squared variable; the paper cites [20] and does not prove it.
  • ad hoc to paper The numerical maximization of g(theta, rho) over rho in [1,7] is performed with 'high accuracy' (Section 4.1).
    The table of theta values and the claimed uniform bound rely on this computation, but no code or detailed method is given.
  • domain assumption Standard model of computation: A and A^T are available as exact matvec oracles.
    The estimator is analyzed under exact arithmetic with Gaussian test vectors; the paper does not address floating-point error or approximate matvecs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the Upper Bounds for the Matrix Spectral Norm." pith.science (2026). https://pith.science/paper/TPS2N6EY

@misc{pith2026250615660,
  author       = {Pith},
  title        = {Pith review of: On the Upper Bounds for the Matrix Spectral Norm},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TPS2N6EY}},
  note         = {Machine review of arXiv:2506.15660}
}
read the original abstract

We consider the problem of estimating the spectral norm of a matrix using only matrix-vector products. We propose a new Counterbalance estimator that provides upper bounds on the norm and derive probabilistic guarantees on its underestimation. Compared to standard approaches such as the power method, the proposed estimator produces significantly tighter upper bounds in both synthetic and real-world settings. Our method is especially effective for matrices with fast-decaying spectra, such as those arising in deep learning and inverse problems.

Figures

Figures reproduced from arXiv: 2506.15660 by the authors.

Figure 1
Figure 1. Comparison of the Vanilla, Dixon, and Counterbalance estimators across various [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Empirical density comparison for different methods. [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. Convergence comparison of different estimators as the number of matrix-vector [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Singular values for matrices from Section 5 [PITH_FULL_IMAGE:figures/full_fig_p019_4.png]
Figure 5
Figure 5. Figure 5: Results for Dominant 0.1 matrix Then we give detailed description of Frechet derivative experiment considered in Section 5. We use [22, Section 3.2] to obtain that under certain assumptions on the smoothness of f, f A X 0 A  =  f(A) Df{A}(X) 0 f(A)  . 19 [PITH_F…

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 19 canonical work pages

  1. [1]

    A. H. Al-Mohy, N. J. Higham, Computing the Fr´ echet derivative of the matrix exponential, with an application to condition number estimation, SIAM J. Matrix Anal. Appl. 30 (4) (2009) 1639–1657

    work page 2009

  2. [2]

    A. H. Al-Mohy, N. J. Higham, S. D. Relton, Computing the Fr´ echet derivative of the matrix logarithm and estimating the condition number, SIAM J. Sci. Comput. 35 (4) (2013) C394– C410

    work page 2013

  3. [3]

    S. Wang, H. Yang, H. Li, Condition numbers for the nonlinear matrix equation and their statistical estimation, Linear Algebra and its Applications 482 (2015) 221–240

    work page 2015

  4. [4]

    H. Gouk, E. Frank, B. Pfahringer, M. J. Cree, Regularisation of neural networks by enforcing lipschitz continuity, Machine Learning 110 (2021) 393–416

    work page 2021

  5. [5]

    Dixon, Estimating extremal eigenvalues and condition numbers of matrices, Siam (1983) 812–814

    J. Dixon, Estimating extremal eigenvalues and condition numbers of matrices, Siam (1983) 812–814. 12

    work page 1983

  6. [6]

    Halko, P

    N. Halko, P. G. Martinsson, J. A. Tropp, Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions, SIAM Review 53 (2) (2011) 217–288.arXiv:https://doi.org/10.1137/090771806,doi:10.1137/090771806. URLhttps://doi.org/10.1137/090771806

    doi:10.1137/090771806 2011

  7. [7]

    Boucheron, G

    S. Boucheron, G. Lugosi, P. Massart, Concentration inequalities: A nonasymptotic theory of independence, Oxford University Press, 2013

    work page 2013

  8. [8]

    R. Vershynin, High-Dimensional Probability: An Introduction with Applications in Data Sci- ence, Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press, 2018

    2018

Show all 23 references
  1. [9]

    Bujanovi´ c, D

    Z. Bujanovi´ c, D. Kressner, Norm and trace estimation with random rank-one vectors, SIAM Journal on Matrix Analysis and Applications 42 (1) (2021) 202–223

    2021

  2. [10]

    Kuczy´ nski, H

    J. Kuczy´ nski, H. Wo´ zniakowski, Estimating the largest eigenvalues by the power and lanczos algorithms with a random start, SIAM Journal on Matrix Analysis and Applications 13 (4) (1992) 1094–1122

    1992

  3. [11]

    M. E. Hochstenbach, Probabilistic upper bounds for the matrix two-norm, Journal of Scientific Computing 57 (3) (2013) 464–476

    2013

  4. [12]

    M. F. Hutchinson, A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines, Communications in Statistics - Simulation and Computation 19 (2) (1990) 433–450

    1990

  5. [13]

    Avron, S

    H. Avron, S. Toledo, Randomized algorithms for estimating the trace of an implicit symmetric positive semidefinite matrix, Journal of the ACM 58 (2) (2011) 8:1–8:17

    2011

  6. [14]

    Roosta-Khorasani, U

    F. Roosta-Khorasani, U. Ascher, Improved bounds on sample size for implicit matrix trace estimators, Foundations of Computational Mathematics 15 (2015) 1187–1212

    2015

  7. [15]

    R. A. Meyer, C. Musco, C. Musco, D. P. Woodruff, Hutch++: Optimal stochastic trace esti- mation, in: Proceedings of the SIAM Symposium on Simplicity in Algorithms (SOSA), 2021, pp. 142–148, arXiv:2010.09649

    2021 arXiv

  8. [16]

    J. H. M. Wedderburn, Lectures on matrices, Vol. 17, American Mathematical Soc., 1934

    1934

  9. [17]

    M. T. Chu, R. E. Funderlic, G. H. Golub, A rank–one reduction formula and its applications to matrix factorizations, SIAM review 37 (4) (1995) 512–530

    1995

  10. [18]

    Bujanovic, D

    Z. Bujanovic, D. Kressner, Norm and trace estimation with random rank-one vectors, SIAM Journal on Matrix Analysis and Applications 42 (1) (2021) 202–223

    2021

  11. [19]

    K. He, X. Zhang, S. Ren, J. Sun, Deep residual learning for image recognition, in: Proceedings of the IEEE conference on computer vision and pattern recognition, 2016, pp. 770–778

    2016

  12. [20]

    G. J. Szekely, Extremal probabilities for gaussian quadratic forms, Springer-Verlag (2003). doi:https://doi.org/10.1007/s00440-003-0262-6. 13

    2003 doi

  13. [21]

    Martinsson, J

    P.-G. Martinsson, J. A. Tropp, Randomized numerical linear algebra: Foundations and algo- rithms, Acta Numerica 29 (2020) 403–572

    2020

  14. [22]

    N. J. Higham, Functions of matrices: theory and computation, SIAM, 2008. 14 A Proofs In this section we writeχ 2 k(t),k∈N, for the distribution function of the chi-squared distribution withkdegrees of freedom. In particular, we writeχ 2 1(t) instead ofχ 2 (1,0)(t) for concisen...

    2008

  15. [23]

    15 Using Jensen’s inequality we obtain P ξ2 1≤η =E I ξ2 1≤η =E η Eξ2 1 I(ξ2 1≤η)|η =E η χ2 1(η) ≤χ 2 1(E[η])

    Moreover, E[η] = (ρ−1)t 1−t . 15 Using Jensen’s inequality we obtain P ξ2 1≤η =E I ξ2 1≤η =E η Eξ2 1 I(ξ2 1≤η)|η =E η χ2 1(η) ≤χ 2 1(E[η]). (18) Combining (17) and (18), we get P ξ2 1≤(1−t) −1 kX i=2 ξ2 i σ2 i σ2 1 ! ≤χ 2 1 (ρ−1)t 1−t , and the statement follows. A.1 Proof of ...

Pith tools

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