Lower bounds for trace estimation via Block Krylov and other methods

Shi Jie Yu

REVIEW 2 major objections 4 minor 6 references

Lower bounds for trace estimation via Block Krylov and other methods

T0 review · 2 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read A constant-factor estimate of the trace of an inverse power of a Wishart matrix requires Ω(d) matrix-vector queries.

desk verdict A plausible but not-yet-clean extension of the known Wishart query lower bound to inverse powers; the proof has a quantifier gap and the upper-bound section has a degree error, so it needs revision, not rejection. read the letter →

arxiv 2506.22701 v1 pith:Q2OK6CX6 submitted 2025-06-28 math.ST cs.DScs.LGcs.NAmath.NAstat.TH

Shi Jie Yu This is my paper · ORCID

classification math.STcs.DScs.LGcs.NAmath.NAstat.TH MSC 60B2065Y2068Q25

keywords traceestimationlowerboundsWishartmatricesBlockKrylovpolynomialapproximationHutchinson'smethodquerycomplexityinverse

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 sets out to prove that on a $d\times d$ Wishart matrix $W$, any algorithm that estimates the trace of $W^{-p}$ for $p>1/2$ to within a constant factor with high probability must make $n=\Omega(d)$ matrix-vector product queries. If true, constant-factor inverse-power trace estimation is as hard as reading the whole matrix on these random instances, matching the previously known $p=1$ lower bound. The paper also formalizes the connection between the number of Block Krylov iterations and the degree of a polynomial approximating the scalar function $f$, and uses it to derive upper bounds for estimating $\mathrm{tr}(A^{-1/2})$ and $\mathrm{tr}(A^{-1})$. The overall picture is that trace estimation cost is governed by polynomial approximation degree on the upper side and by query-information limits on the lower side.

What carries the argument

The machinery has three load-bearing components. First, a Block Krylov method with $m$ iterations only reaches the subspace $\mathrm{span}\{V, AV, \ldots, A^{m-1}V\}$, so its approximation to $f(A)V$ is exactly a matrix polynomial $Q_{m-1}(A)V$; this equates Krylov iteration count with polynomial degree and reduces upper-bound analysis to scalar polynomial approximation. Second, for a Wishart matrix $W$, any $n<d$ adaptive queries $Wv_1,\ldots,Wv_n$ reveal only a Gaussian linear map: after an orthogonal change of variables, the conditional distribution of $W$ is a block matrix containing an independent $\mathrm{Wishart}(d-n)$ corner, so the unobserved part retains full low-dimensional uncertainty. Third, spectral small-ball estimates for Wishart matrices (the smallest eigenvalue falls below a constant times $d^{-2}$ with probability about $\sqrt{x}$) provide the constant-probability event that drives the lower bound. The chaining of these three pieces is what forces $n=\Omega(d)$.

What would settle it

Compute $\delta_0 = \varepsilon/(2(1+\varepsilon))$ for explicit constants, say $C=2$ and $p=1$, by extracting the hidden constant in Proposition 8's $\asymp$. If $\delta_0$ is smaller than a standard failure probability like $1/3$, then the proof does not establish the theorem for $\delta=1/3$; moreover, an algorithm that estimates $\mathrm{tr}(W^{-1})$ with $o(d)$ queries and success probability $2/3$ would directly refute the claimed lower bound.

Watch

Extended reading notes

Core claim

The central claim is Theorem 5: for any $d\ge 2$, any algorithm that performs $n$ matrix-vector product queries with a $d\times d$ Wishart matrix $W \sim \mathrm{Wishart}(d)$ and outputs an estimator $\hat{tr}$ satisfying $C^{-1}\mathrm{tr}(W^{-p}) \le \hat{tr} \le C\,\mathrm{tr}(W^{-p})$ with probability at least $1-\delta$, where $p>1/2$, must have $n=\Omega(d)$. The proof argues by contradiction, assuming $n\le d/2$. After $n$ queries, the posterior distribution of $W$ has a block form whose lower-right corner is an independent $\mathrm{Wishart}(d-n)$ matrix; with probability at least a constant $\varepsilon$, the smallest eigenvalue of that corner is small, which would force the estimator to be too small on a set of positive probability. Since this failure probability is at least $\varepsilon(1/2-\delta)$, it contradicts the success guarantee when $\delta$ is smaller than a threshold $\delta_0$. The theorem extends an existing $p=1$ lower bound to every $p>1/2$.

Load-bearing premise

The proof only forces a contradiction when the algorithm's failure probability $\delta$ is smaller than a constant $\delta_0$ that depends on both the approximation factor $C$ and the power $p$, while the theorem statement asserts $\delta$ depends only on $C$; if the intended guarantee uses a fixed failure probability such as $1/3$, the final step does not go through.

Editorial extensions

If this is right

If Theorem 5 holds, every constant-factor estimator of $\mathrm{tr}(W^{-p})$ for $p>1/2$ on Wishart matrices requires essentially $d$ matrix-vector products, so the $p=1$ lower bound is not an artifact of the reciprocal function.
The upper-bound analysis shows the Hutchinson-Krylov method achieves cost $O(N_v \sqrt{\kappa}\log(\kappa/\delta))$ for $\mathrm{tr}(A^{-1})$ and $\mathrm{tr}(A^{-1/2})$, tying the number of Krylov steps to the required polynomial degree.
For well-conditioned matrices, near-linear-in-$\kappa$ algorithms are possible, while the Wishart lower bound shows that when the spectrum has heavy small eigenvalues, dimension-scale probing is unavoidable.
The result also clarifies that the information-theoretic hardness comes from the unbounded influence of small eigenvalues of $W$, not from the conditioning number alone.

Reading between the lines

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

An implicit consequence the paper does not draw: the same argument may extend to other spectral functions with singularities at zero, as long as the scalar polynomial approximation degree and the Wishart small-ball probability can be matched; the exact threshold $p>1/2$ is tied to convergence of $\sum_j j^{-2p}$.
The quantifier issue around $\delta$ suggests that a stronger argument, or an explicit handling of the dependency of $\varepsilon$ on $C$ and $p$, is needed to guarantee fixed-failure-probability settings; a reader who only needs error probability $1/3$ should not treat the theorem as proven in its current form.
A direct testable extension would be to run the Hutchinson-Krylov method on Wishart instances with $n=o(d)$ and a constant-factor target, and measure the empirical failure probability; the theorem predicts it stays bounded away from 0.

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.

Desk Editor's Note

read the letter

Short version: the one genuinely new item is the extension of the CDLLN24 Wishart query lower bound from tr(W^{-1}) to tr(W^{-p}) for p>1/2, and the proof follows the right posterior-Wishart template. But the theorem as stated isn't what the proof shows, and the upper-bound section has a degree-computation gap. Both are fixable, so this is a revise-and-resubmit, not a reject.

On the plus side: the structural reduction from Block Krylov iteration count to polynomial degree is cleanly stated, and the lower-bound proof correctly assembles the pieces from BHSW20 and Edelman/Vershynin: the posterior Wishart form, the lambda_min comparison, and the constant-probability small-eigenvalue event. There's no circularity and no fitted parameters. The paper is honest about what is review (Section 3.1) and what is new.

Soft spots: (1) Theorem 5 states delta depends only on C, but the proof derives delta >= delta0 with delta0 = epsilon/(2(1+epsilon)) where epsilon depends on both C and p. The final contradiction only fires if the algorithm's failure probability is below delta0. For a fixed confidence like 1/3, the proof gives nothing. The theorem needs to be restated, or an amplification argument supplied. This is not a tiny typo; it is the load-bearing step. (2) Theorem 3 claims degree O(sqrt(kappa) log(kappa/delta)) but the proof yields O(sqrt(kappa log(kappa/delta)) * log(kappa/delta)), which is about sqrt(kappa) log^{3/2}(kappa/delta) by the paper's own calculation. There is an unaccounted square root of the log factor. That may be fixable with a sharper polynomial approximation or a different parameter choice, but as written the bound doesn't follow. (3) Minor: lots of typos and missing symbols in the text, e.g., the proof of Theorem 5 opens with "Let > 0 be the failure probability," and Proposition 1's statement is mangled. None of this obscures the main idea, but it is not polished.

Who is this for? People working on query complexity of trace estimation or randomized linear algebra. The lower-bound extension is a natural incremental result and deserves a serious referee. My recommendation: send it out; a good referee can check whether the delta quantifier can be repaired, for instance by stating the result for delta below a constant depending on C and p, or by adding a standard amplification argument.

Referee Report

2 major / 4 minor

Summary. This paper studies the query complexity of estimating tr(f(A)) by Hutchinson's method with Block Krylov subspace approximations. It formalizes the relation between Krylov iterations and polynomial degree, gives upper bounds for tr(A^{-1/2}) and tr(A^{-1}), and proves a query lower bound for estimating tr(W^{-p}) for a d-dimensional Wishart matrix W when p>1/2, claiming that n=Ω(d) matrix-vector product queries are necessary for a constant-factor approximation. The lower-bound proof uses a posterior Wishart characterization from BHSW20 and eigenvalue tail bounds from Edelman, Vershynin, and Szarek.

Significance. The paper's upper-bound formalization is useful pedagogy, and the lower-bound extension to p>1/2 is a natural and potentially valuable strengthening of the known p=1 result. The proof strategy of relating queries to a Wishart posterior is principled and builds on established results rather than fitted parameters or self-citations. The main claims are not, however, fully established by the proofs as written: the final paragraph of Theorem 5's proof only covers algorithms with failure probability below an explicit δ0(C,p), and the polynomial-degree calculation in Theorem 3 (and Proposition 2) oversimplifies in a way that invalidates the stated degree bound from the given argument. The results are likely repairable, but the manuscript requires substantive revision.

major comments (2)

[§4.2, final paragraph] The proof of Theorem 5 establishes only the inequality δ ≥ δ0 := ε/(2(1+ε)), where ε depends on both C and p. This yields a contradiction only for algorithms whose failure probability δ is smaller than δ0. The theorem statement says 'δ >0 is dependent only on C' and does not impose δ < δ0; for a fixed confidence value such as δ=1/3 with δ0<1/3, the displayed inequality is consistent with n≤d/2 and the proof does not rule out o(d) queries. To prove the theorem as stated, the author must either add a median-amplification argument (which would transfer the small-δ lower bound to any fixed δ at a constant multiplicative query cost) or restate the theorem with an explicit quantifier of the form 'there exists δ0(C,p)>0 such that for all δ<δ0'. The missing amplification step is load-bearing because the theorem is claimed for arbitrary positive δ, not only for δ below a small threshold.
[§3.2, proof of Theorem 3] The degree calculation is not valid. With T=Cκ log(2κ/δ_P) and δ_T=δ_P/(2T), the dominant degree is O(√T log(T/δ_T)) = O(√(κ log(κ/δ_P)) · log(κ^2 log^2(κ/δ_P)/δ_P)), which is O(√κ (log(κ/δ_P))^{3/2}) for fixed δ_P as κ→∞, not O(√κ log(κ/δ_P)). The displayed chain 'O(√T log T) = O(√κ log(κ/δ_P))' drops a √(log(κ/δ_P)) factor. Since Theorem 3's degree bound is exactly what is used to claim the O(√κ log(κ/δ)) cost for tr(A^{-1}), the proof as written does not establish the stated upper bound. The same simplification appears in the proof of Proposition 2 in §3.1, where the substitution T=O(κ log(κ/δ)) similarly yields an extra √(log(κ/δ)) factor.

minor comments (4)

[§4.2] Theorem 5 states the result for tr(W^{-p}) with p>1/2, but the proof uses q and says 'valid for all q>1/2'; the notation should be aligned.
[§4.2, opening sentence] The sentence 'Let > 0 be the failure probability that we choose later' is missing the symbol for the positive constant; it should read 'Let ε > 0 be a positive constant that we choose later'.
[Theorems 4 and 5] The phrase 'where δ >0 is dependent only on C' is ambiguous and should be replaced by an explicit quantifier, for example 'for every δ∈(0,δ0(C,p))' if that is the intended statement.
[§2.2.2] The reduction 'Total Cost = O(N_v · g(x))' treats N_v as an independent parameter without discussing how N_v trades off against the target success probability or variance of Hutchinson's estimator; stating this assumption explicitly would improve clarity.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central lower bound is an adversary argument built on external published results, and no fitted parameter or self-citation chain carries the conclusion.

full rationale

The paper's main derivation chain is not circular. Theorem 5, the inverse-power trace estimation lower bound, is proved by contradiction using Proposition 6 from BHSW20, Proposition 7 from BHSW20, Proposition 8 from Ede88/Ver18, and Proposition 9 from Sza91. These are external published results, not outputs of the present paper. The proof assumes n ≤ d/2, derives a lower bound on the failure probability δ in terms of a constant ϵ, and then contradicts the theorem's ability to choose δ sufficiently small. This is a standard query-complexity adversary argument and does not presuppose the conclusion. The upper-bound results in Section 3 are likewise derived from the external polynomial-approximation result of Sachdeva and Vishnoi (Proposition 1) and from explicit Taylor/geometric-series estimates; they do not rename an input as a prediction. There are no fitted parameters, no self-citations that are load-bearing, and no ansatz smuggled in via citation. The only notable weakness is a quantifier issue in the final paragraph of Section 4.2: the proof obtains a contradiction only for failure probabilities below δ0 = ε/(2(1+ε)), where ε depends on both C and p, whereas Theorem 5 states δ depends only on C. This means the theorem as stated may not cover standard fixed-confidence settings such as δ = 1/3 without an additional amplification argument. However, this is a correctness/completeness concern, not circularity: the proof does not assume what it is trying to prove, and the cited external results remain independent evidence. Therefore the circularity score is 0.

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

The paper introduces no fitted numerical parameters and no new physical or mathematical entities. Its central claims rest on standard polynomial approximation theorems, Wishart posterior structure from [BHSW20], and eigenvalue tail bounds from [Ede88; Ver18; Sza91]. The only paper-specific loading is the interpretation of the failure probability δ in the lower-bound proof.

assumptions (5)

standard math Existence of low-degree polynomials approximating monomials x^t on [-1,1] (Proposition 1, from [SV+14, Theorem 3.3]).
Used in Propositions 2 and 3 to replace each Taylor term x^t by a lower-degree polynomial while controlling the total error.
standard math Posterior representation of a Wishart matrix after n<d adaptive matrix-vector queries (Proposition 6, from [BHSW20, Lemma 3.4]): conditionally, W has block form with a Wishart(d-n) block fW.
This is the key structural fact for the lower bound; Section 4.1 states it without proof.
standard math Interlacing bound λ_min(W) ≤ λ_min(fW) for the block representation (Proposition 7, from [BHSW20, Lemma 3.5]).
Used in Theorem 5 to connect a small eigenvalue in the posterior block to a small eigenvalue of W.
standard math Extreme eigenvalue tail bounds for Wishart matrices (Proposition 8, from [Ede88; Ver18]) and trace bound (Proposition 9, from [Sza91]).
Used to show tr(W^{-p}) ≤ C'd^{2p} with constant probability and to lower-bound the probability of a small minimum eigenvalue in the posterior block.
ad hoc to paper The lower-bound theorem's success probability δ can be chosen smaller than δ0=ε/(2(1+ε)), where ε depends on C and p.
This convention is asserted at the end of the proof of Theorem 5 but is not reconciled with the theorem statement that says δ depends only on C; it is load-bearing for the contradiction.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Lower bounds for trace estimation via Block Krylov and other methods." pith.science (2026). https://pith.science/paper/Q2OK6CX6

@misc{pith2026250622701,
  author       = {Pith},
  title        = {Pith review of: Lower bounds for trace estimation via Block Krylov and other methods},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Q2OK6CX6}},
  note         = {Machine review of arXiv:2506.22701}
}

abstract

This paper studies theoretical lower bounds for estimating the trace of a matrix function, $\text{tr}(f(A))$, focusing on methods that use Hutchinson's method along with Block Krylov techniques. These methods work by approximating matrix-vector products like $f(A)V$ using a Block Krylov subspace. This is closely related to approximating functions with polynomials. We derive theoretical upper bounds on how many Krylov steps are needed for functions such as $A^{-1/2}$ and $A^{-1}$ by analyzing the upper bounds from the polynomial approximation of their scalar equivalent. In addition, we also develop lower limits on the number of queries needed for trace estimation, specifically for $\text{tr}(W^{-p})$ where $W$ is a Wishart matrix. Our study clarifies the connection between the number of steps in Block Krylov methods and the degree of the polynomial used for approximation. This links the total cost of trace estimation to basic limits in polynomial approximation and how much information is needed for the computation.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

6 extracted references · 6 canonical work pages

[1]

Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix

[AT11] H. Avron and S. Toledo. “Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix”. In: Journal of the ACM (JACM) 58.2 (2011), pp. 1–34. [BHSW20] M. Braverman, E. Hazan, M. Simchowitz, and B. Woodworth. “The gradient complex- ity of linear regression”. In: Conference on Learning Theory. PMLR. 2020, pp. 627–

work page 2011
[193]

Spectral sparsification of graphs

11 [ST11] D. A. Spielman and S.-H. Teng. “Spectral sparsification of graphs”. In: SIAM Journal on Computing 40.4 (2011), pp. 981–1025. [SV+14] S. Sachdeva, N. K. Vishnoi, et al. “Faster algorithms via approximation theory”. In: Foundations and Trends® in Theoretical Computer Science9.2 (2014), pp. 125–210. [Sza91] S. J. Szarek. “Condition numbers of rando...

work page 2011
[647]

Query lower bounds for log-concave sampling

[CDLLN24] S. Chewi, J. de Dios Pont, J. Li, C. Lu, and S. Narayanan. “Query lower bounds for log-concave sampling”. In: Journal of the ACM71.4 (2024), pp. 1–42. [Ede88] A. Edelman. “Eigenvalues and condition numbers of random matrices”. In: SIAM journal on matrix analysis and applications9.4 (1988), pp. 543–560. [FS08] A. Frommer and V. Simoncini. “Matrix...

work page 2024
[1997]

The block Lanczos method for computing eigenval- ues

[GU77] G. H. Golub and R. Underwood. “The block Lanczos method for computing eigenval- ues”. In: Mathematical software. Elsevier, 1977, pp. 361–377. [Hut89] M. F. Hutchinson. “A stochastic estimator of the trace of the influence matrix for Laplacian smoothing splines”. In: Communications in Statistics-Simulation and Computation 18.3 (1989), pp. 1059–1076....

work page 1989
[2013]

Hutch++: Optimal stochastic trace estimation

[MMMW21] R. A. Meyer, C. Musco, C. Musco, and D. P. Woodruff. “Hutch++: Optimal stochastic trace estimation”. In: Symposium on Simplicity in Algorithms (SOSA). SIAM. 2021, pp. 142–155. [Riv20] T. J. Rivlin. Chebyshev polynomials. Courier Dover Publications,

work page 2021
[2020]

Iterative methods for linear systems of equations: A brief historical journey

[Saa19] Y. Saad. “Iterative methods for linear systems of equations: A brief historical journey”. In: arXiv preprint arXiv:1908.01083(2019). [Sad93] M. Sadkane. “A block Arnoldi-Chebyshev method for computing the leading eigenpairs of large sparse unsymmetric matrices”. In: Numerische mathematik 64 (1993), pp. 181–

work page Pith review arXiv 2019

Pith tools

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

[1] [1]

Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix

[AT11] H. Avron and S. Toledo. “Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix”. In: Journal of the ACM (JACM) 58.2 (2011), pp. 1–34. [BHSW20] M. Braverman, E. Hazan, M. Simchowitz, and B. Woodworth. “The gradient complex- ity of linear regression”. In: Conference on Learning Theory. PMLR. 2020, pp. 627–

work page 2011

[2] [193]

Spectral sparsification of graphs

11 [ST11] D. A. Spielman and S.-H. Teng. “Spectral sparsification of graphs”. In: SIAM Journal on Computing 40.4 (2011), pp. 981–1025. [SV+14] S. Sachdeva, N. K. Vishnoi, et al. “Faster algorithms via approximation theory”. In: Foundations and Trends® in Theoretical Computer Science9.2 (2014), pp. 125–210. [Sza91] S. J. Szarek. “Condition numbers of rando...

work page 2011

[3] [647]

Query lower bounds for log-concave sampling

[CDLLN24] S. Chewi, J. de Dios Pont, J. Li, C. Lu, and S. Narayanan. “Query lower bounds for log-concave sampling”. In: Journal of the ACM71.4 (2024), pp. 1–42. [Ede88] A. Edelman. “Eigenvalues and condition numbers of random matrices”. In: SIAM journal on matrix analysis and applications9.4 (1988), pp. 543–560. [FS08] A. Frommer and V. Simoncini. “Matrix...

work page 2024

[4] [1997]

The block Lanczos method for computing eigenval- ues

[GU77] G. H. Golub and R. Underwood. “The block Lanczos method for computing eigenval- ues”. In: Mathematical software. Elsevier, 1977, pp. 361–377. [Hut89] M. F. Hutchinson. “A stochastic estimator of the trace of the influence matrix for Laplacian smoothing splines”. In: Communications in Statistics-Simulation and Computation 18.3 (1989), pp. 1059–1076....

work page 1989

[5] [2013]

Hutch++: Optimal stochastic trace estimation

[MMMW21] R. A. Meyer, C. Musco, C. Musco, and D. P. Woodruff. “Hutch++: Optimal stochastic trace estimation”. In: Symposium on Simplicity in Algorithms (SOSA). SIAM. 2021, pp. 142–155. [Riv20] T. J. Rivlin. Chebyshev polynomials. Courier Dover Publications,

work page 2021

[6] [2020]

Iterative methods for linear systems of equations: A brief historical journey

[Saa19] Y. Saad. “Iterative methods for linear systems of equations: A brief historical journey”. In: arXiv preprint arXiv:1908.01083(2019). [Sad93] M. Sadkane. “A block Arnoldi-Chebyshev method for computing the leading eigenpairs of large sparse unsymmetric matrices”. In: Numerische mathematik 64 (1993), pp. 181–

work page Pith review arXiv 2019