Lower bounds for trace estimation via Block Krylov and other methods
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909664760823808 |
|---|---|
| author | Yu, Shi Jie |
| author_facet | Yu, Shi Jie |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_22701 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Lower bounds for trace estimation via Block Krylov and other methods Yu, Shi Jie Statistics Theory Data Structures and Algorithms Machine Learning Numerical Analysis 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. |
| title | Lower bounds for trace estimation via Block Krylov and other methods |
| topic | Statistics Theory Data Structures and Algorithms Machine Learning Numerical Analysis |
| url | https://arxiv.org/abs/2506.22701 |