On Symmetric Lanczos Quadrature for Stochastic Trace Estimation
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918312370241536 |
|---|---|
| author | Li, Wenhao Zhu, Shengxin |
| author_facet | Li, Wenhao Zhu, Shengxin |
| contents | A common approach to approximating quadratic forms of matrix functions is to use a quadrature rule derived from the Lanczos process, known as a Lanczos quadrature. Although symmetric quadrature rules are computationally favorable, it has remained unclear whether a symmetric Lanczos quadrature is practically feasible. In this work, we resolve this ambiguity by establishing necessary and sufficient conditions for the existence of symmetric Lanczos quadratures. We show that the sufficient condition can be met for a class of Jordan-Wielandt matrices by carefully constructing initial vectors with specific distributions for the Lanczos algorithm. Applying such a symmetric Lanczos quadrature to compute the Estrada index of bipartite or directed graphs ensures that the resulting stochastic trace estimators are unbiased. Furthermore, we observe that the variance of the quadratic form estimator based on the symmetric Lanczos quadrature is lower than that of the standard estimator. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_18913 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On Symmetric Lanczos Quadrature for Stochastic Trace Estimation Li, Wenhao Zhu, Shengxin Numerical Analysis 65D32, 65F15 A common approach to approximating quadratic forms of matrix functions is to use a quadrature rule derived from the Lanczos process, known as a Lanczos quadrature. Although symmetric quadrature rules are computationally favorable, it has remained unclear whether a symmetric Lanczos quadrature is practically feasible. In this work, we resolve this ambiguity by establishing necessary and sufficient conditions for the existence of symmetric Lanczos quadratures. We show that the sufficient condition can be met for a class of Jordan-Wielandt matrices by carefully constructing initial vectors with specific distributions for the Lanczos algorithm. Applying such a symmetric Lanczos quadrature to compute the Estrada index of bipartite or directed graphs ensures that the resulting stochastic trace estimators are unbiased. Furthermore, we observe that the variance of the quadratic form estimator based on the symmetric Lanczos quadrature is lower than that of the standard estimator. |
| title | On Symmetric Lanczos Quadrature for Stochastic Trace Estimation |
| topic | Numerical Analysis 65D32, 65F15 |
| url | https://arxiv.org/abs/2504.18913 |