Accelerated decomposition of bistochastic kernel matrices by low rank approximation
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911260784721920 |
|---|---|
| author | Vales, Chris Giannakis, Dimitrios |
| author_facet | Vales, Chris Giannakis, Dimitrios |
| contents | We develop an accelerated algorithm for computing an approximate eigenvalue decomposition of bistochastic normalized kernel matrices. Our approach constructs a low rank approximation of the original kernel matrix by the pivoted partial Cholesky algorithm and uses it to compute an approximate decomposition of its bistochastic normalization without requiring the formation of the full kernel matrix. The cost of the proposed algorithm depends linearly on the size of the employed training dataset and quadratically on the rank of the low rank approximation, offering a significant cost reduction compared to the naive approach. We apply the proposed algorithm to the kernel based extraction of spatiotemporal patterns from chaotic dynamics, demonstrating its accuracy while also comparing it with an alternative algorithm consisting of subsampling and Nystroem extension. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_26574 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Accelerated decomposition of bistochastic kernel matrices by low rank approximation Vales, Chris Giannakis, Dimitrios Numerical Analysis Computational Physics We develop an accelerated algorithm for computing an approximate eigenvalue decomposition of bistochastic normalized kernel matrices. Our approach constructs a low rank approximation of the original kernel matrix by the pivoted partial Cholesky algorithm and uses it to compute an approximate decomposition of its bistochastic normalization without requiring the formation of the full kernel matrix. The cost of the proposed algorithm depends linearly on the size of the employed training dataset and quadratically on the rank of the low rank approximation, offering a significant cost reduction compared to the naive approach. We apply the proposed algorithm to the kernel based extraction of spatiotemporal patterns from chaotic dynamics, demonstrating its accuracy while also comparing it with an alternative algorithm consisting of subsampling and Nystroem extension. |
| title | Accelerated decomposition of bistochastic kernel matrices by low rank approximation |
| topic | Numerical Analysis Computational Physics |
| url | https://arxiv.org/abs/2510.26574 |