Estimating a graph's spectrum via random Kirchhoff forests
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913768551743488 |
|---|---|
| author | Barthelmé, Simon Castell, Fabienne Gaudillière, Alexandre Melot, Clothilde Quattropani, Matteo Tremblay, Nicolas |
| author_facet | Barthelmé, Simon Castell, Fabienne Gaudillière, Alexandre Melot, Clothilde Quattropani, Matteo Tremblay, Nicolas |
| contents | Exact eigendecomposition of large matrices is very expensive, and it is practically impossible to compute exact eigenvalues. Instead, one may set a more modest goal of approaching the empirical distribution of the eigenvalues, recovering the overall shape of the eigenspectrum. Current approaches to spectral estimation typically work with \emph{moments} of the spectral distribution. These moments are first estimated using Monte Carlo trace estimators, then the estimates are combined to approximate the spectral density. In this article we show how \emph{Kirchhoff forests}, which are random forests on graphs, can be used to estimate certain non-linear moments of very large graph Laplacians. We show how to combine these moments into an estimate of the spectral density. If the estimate's desired precision isn't too high, our approach paves the way to the estimation of a graph's spectrum in time sublinear in the number of links. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_24236 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Estimating a graph's spectrum via random Kirchhoff forests Barthelmé, Simon Castell, Fabienne Gaudillière, Alexandre Melot, Clothilde Quattropani, Matteo Tremblay, Nicolas Computation Statistics Theory Exact eigendecomposition of large matrices is very expensive, and it is practically impossible to compute exact eigenvalues. Instead, one may set a more modest goal of approaching the empirical distribution of the eigenvalues, recovering the overall shape of the eigenspectrum. Current approaches to spectral estimation typically work with \emph{moments} of the spectral distribution. These moments are first estimated using Monte Carlo trace estimators, then the estimates are combined to approximate the spectral density. In this article we show how \emph{Kirchhoff forests}, which are random forests on graphs, can be used to estimate certain non-linear moments of very large graph Laplacians. We show how to combine these moments into an estimate of the spectral density. If the estimate's desired precision isn't too high, our approach paves the way to the estimation of a graph's spectrum in time sublinear in the number of links. |
| title | Estimating a graph's spectrum via random Kirchhoff forests |
| topic | Computation Statistics Theory |
| url | https://arxiv.org/abs/2503.24236 |