FlexTrace: Exchangeable Randomized Trace Estimation for Matrix Functions
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911490208956416 |
|---|---|
| author | Madhavan, Madhusudan Alexanderian, Alen Saibaba, Arvind K. |
| author_facet | Madhavan, Madhusudan Alexanderian, Alen Saibaba, Arvind K. |
| contents | We consider the task of estimating the trace of a matrix function, ${\rm tr}(f({\bf A}))$, of a large symmetric positive semi-definite matrix ${\bf A}$. This problem arises in multiple applications, including kernel methods and inverse problems. A key challenge across existing trace estimation methods is the need for matrix-vector products (matvecs) with $f({\bf A})$, which can be very expensive. In this article, we introduce a novel trace estimator, FlexTrace, an exchangeable, single-pass method that estimates ${\rm tr}(f({\bf A}))$ solely using matvecs with ${\bf A}$. We consider the case where $f$ is an operator monotone matrix function with $f(0)=0$, which includes functions such as $\log(1+x)$ and $x^{1/2}$, and derive probabilistic bounds showcasing the theoretical advantages of FlexTrace. Numerical experiments across synthetic examples and application domains demonstrate that FlexTrace provides substantially more accurate estimates of the trace of $f({\bf A})$ compared to existing methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_05721 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | FlexTrace: Exchangeable Randomized Trace Estimation for Matrix Functions Madhavan, Madhusudan Alexanderian, Alen Saibaba, Arvind K. Numerical Analysis 65F60, 15A15, 68W20, 65C05, 65F40, 62F40 We consider the task of estimating the trace of a matrix function, ${\rm tr}(f({\bf A}))$, of a large symmetric positive semi-definite matrix ${\bf A}$. This problem arises in multiple applications, including kernel methods and inverse problems. A key challenge across existing trace estimation methods is the need for matrix-vector products (matvecs) with $f({\bf A})$, which can be very expensive. In this article, we introduce a novel trace estimator, FlexTrace, an exchangeable, single-pass method that estimates ${\rm tr}(f({\bf A}))$ solely using matvecs with ${\bf A}$. We consider the case where $f$ is an operator monotone matrix function with $f(0)=0$, which includes functions such as $\log(1+x)$ and $x^{1/2}$, and derive probabilistic bounds showcasing the theoretical advantages of FlexTrace. Numerical experiments across synthetic examples and application domains demonstrate that FlexTrace provides substantially more accurate estimates of the trace of $f({\bf A})$ compared to existing methods. |
| title | FlexTrace: Exchangeable Randomized Trace Estimation for Matrix Functions |
| topic | Numerical Analysis 65F60, 15A15, 68W20, 65C05, 65F40, 62F40 |
| url | https://arxiv.org/abs/2603.05721 |