# Randomized algorithms for Generalized Hermitian Eigenvalue Problems with application to computing Karhunen-Lo\\\`{e}ve expansion

Source: [Randomized algorithms for Generalized Hermitian Eigenvalue Problems with application to computing Karhunen-Lo\\\`{e}ve expansion](<https://www.sota2.com/research/paper/68fa51d21e209131ce9767ac>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2026-06-05T05:00:20.018Z

Authors: Arvind K. Saibaba, Jonghyun Lee, Peter K. Kitanidis

Published: 2013-07-25T22:13:42.000Z

## Abstract

We describe randomized algorithms for computing the dominant eigenmodes of the Generalized Hermitian Eigenvalue Problem (GHEP) $Ax=\\lambda Bx$, with $A$ Hermitian and $B$ Hermitian and positive definite. The algorithms we describe only require forming operations $Ax$, $Bx$ and $B^{-1}x$ and avoid forming square-roots of $B$ (or operations of the form, $B^{1/2}x$ or $B^{-1/2}x$). We provide a convergence analysis and a posteriori error bounds that build upon the work of~\\cite{halko2011finding,liberty2007randomized,martinsson2011randomized} (which have been derived for the case $B=I$). Additionally, we derive some new results that provide insight into the accuracy of the eigenvalue calculations. The error analysis shows that the randomized algorithm is most accurate when the generalized singular values of $B^{-1}A$ decay rapidly. A randomized algorithm for the Generalized Singular Value Decomposition (GSVD) is also provided. Finally, we demonstrate the performance of our algorithm on computing the Karhunen-Lo\\\`{e}ve expansion, which is a computationally intensive GHEP problem with rapidly decaying eigenvalues.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/1307.6885>)

[PDF](<https://arxiv.org/pdf/1307.6885.pdf>)
