Fast Karhunen-Loève Expansions via FFT-Accelerated Toeplitz Operators
Abstract
Gaussian random fields are a versatile tool used in the fields of stochastic PDEs, uncertainty quantification, and geostatistical simulation. One way to obtain them is to use a truncated Karhunen-Loève expansion (KLE). Computing the expansion requires the leading eigenpairs of an N × N covariance matrix, where N is the total number of grid cells. These are usually computed with a Krylov eigensolver, which relies on the covariance operator only within matrix-vector products. Stored densely, the matrix takes 𝒪(N2) memory and each product 𝒪(N2) time. For a stationary kernel on an equispaced grid, the covariance matrix becomes (block-) Toeplitz and the product evaluates in 𝒪(Nlog N) time using FFT-based circulant embedding, without the need to assemble the dense matrix. In a matched single-threaded comparison, the median speedup of the eigensolve grows from 18 × at N = 4096 to 183 × at N = 215. This makes it possible to compute discretized fields that would otherwise be infeasible to compute in the standard formulation. We show that the same construction carries over to non-separable kernels as well as d dimensions, using block-Toeplitz matrices. We extend it to piecewise-constant fields on arbitrary domains given as subsets of a tensor grid. Computational savings grow with problem size, and storage drops from 𝒪(N2) to 𝒪(2dN).
Related
- On Some Karhunen–Loève Expansions Related to SU(2) with Application to Tests of Symmetry
- Exact fast factorizations of the AR(1) Karhunen-Loeve transform
- Block Toeplitz Operators, Matrix Valued Truncated Toeplitz operators, and Conjugations
- Characterizations of Toeplitz operators on the annulus
- Hyponormal Toeplitz operators with operator valued normal symbols
BibTeX
@misc{wildt2026fast,
title = {{Fast Karhunen-Loève Expansions via FFT-Accelerated Toeplitz Operators}},
author = {Nils Wildt and Wolfgang Nowak},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.26459},
eprint = {2609.26459},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.26459},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Fast Karhunen-Loève Expansions via FFT-Accelerated Toeplitz Operators
AU - Nils Wildt
AU - Wolfgang Nowak
PY - 2026
DA - 2026/09/23
PB - arXiv
DO - 10.48550/arxiv.2609.26459
UR - https://arxiv.org/abs/2609.26459
AB - Gaussian random fields are a versatile tool used in the fields of stochastic PDEs, uncertainty quantification, and geostatistical simulation. One way to obtain them is to use a truncated Karhunen-Loève expansion (KLE). Computing the expansion requires the leading eigenpairs of an N × N covariance matrix, where N is the total number of grid cells. These are usually computed with a Krylov eigensolver, which relies on the covariance operator only within matrix-vector products. Stored densely, the matrix takes 𝒪(N^2) memory and each product 𝒪(N^2) time. For a stationary kernel on an equispaced grid, the covariance matrix becomes (block-) Toeplitz and the product evaluates in 𝒪(Nlog N) time using FFT-based circulant embedding, without the need to assemble the dense matrix. In a matched single-threaded comparison, the median speedup of the eigensolve grows from 18 × at N = 4096 to 183 × at N = 2^15. This makes it possible to compute discretized fields that would otherwise be infeasible to compute in the standard formulation. We show that the same construction carries over to non-separable kernels as well as d dimensions, using block-Toeplitz matrices. We extend it to piecewise-constant fields on arbitrary domains given as subsets of a tensor grid. Computational savings grow with problem size, and storage drops from 𝒪(N^2) to 𝒪(2^dN).
ER -