Exact fast factorizations of the AR(1) Karhunen-Loeve transform
Abstract
We derive a fast factorization of the exact Karhunen--Loève transform (KLT) of an AR(1) source by mapping it onto the Discrete Cosine Transform. For even N and every ρ∈(0,1), the KLT factors exactly into Chen's fast DCT-II structure---butterfly plus fixed half-size DCT-II and DCT-IV cores---completed by two orthogonal corrections: eigenvector matrices of diagonal-plus-rank-one matrices carrying the entire ρ-dependence. Fast DCT factorizations are reused unchanged; as ρ→1 the corrections become identities, recovering Chen's algorithm. At short lengths the design is explicit: at N=4 the transform is one butterfly and two rotations with tan2ψs=−2/(1−ρ), tan2ψa=2/(1+ρ); at N=8 every correction entry is in radicals, via one quartic serving both branches, and factors into six Givens rotations. Complete and scaled realizations run the exact 8-point KLT in 32 and 24 multiplications, about twice the fixed DCT-II; at N=4, a single extra multiplication. At large N, fast-multipole application of the corrections yields the exact KLT in O(Nlog N) operations to prescribed accuracy; this overhead thus peaks at intermediate sizes and vanishes in both limits.
Related
- Fast Karhunen-Loève Expansions via FFT-Accelerated Toeplitz Operators
- On Some Karhunen–Loève Expansions Related to SU(2) with Application to Tests of Symmetry
- Dense Exact Factorizations of Countable Topological Groups
- Exact Factorizations of Rank-One Pointed Hopf Algebras in Positive Characteristic, I
- Mathematical foundation of symmetric fast Fourier transform
BibTeX
@misc{reznik2026exact,
title = {{Exact fast factorizations of the AR(1) Karhunen-Loeve transform}},
author = {Yuriy A. Reznik},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.20221},
eprint = {2609.20221},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.20221},
}
RIS
TY - UNPB
TI - Exact fast factorizations of the AR(1) Karhunen-Loeve transform
AU - Yuriy A. Reznik
PY - 2026
DA - 2026/09/18
PB - arXiv
DO - 10.48550/arxiv.2609.20221
UR - https://arxiv.org/abs/2609.20221
AB - We derive a fast factorization of the exact Karhunen--Loève transform (KLT) of an AR(1) source by mapping it onto the Discrete Cosine Transform. For even N and every ρ∈(0,1), the KLT factors exactly into Chen's fast DCT-II structure---butterfly plus fixed half-size DCT-II and DCT-IV cores---completed by two orthogonal corrections: eigenvector matrices of diagonal-plus-rank-one matrices carrying the entire ρ-dependence. Fast DCT factorizations are reused unchanged; as ρ→1 the corrections become identities, recovering Chen's algorithm. At short lengths the design is explicit: at N=4 the transform is one butterfly and two rotations with tan2ψ_s=−2/(1−ρ), tan2ψ_a=2/(1+ρ); at N=8 every correction entry is in radicals, via one quartic serving both branches, and factors into six Givens rotations. Complete and scaled realizations run the exact 8-point KLT in 32 and 24 multiplications, about twice the fixed DCT-II; at N=4, a single extra multiplication. At large N, fast-multipole application of the corrections yields the exact KLT in O(Nlog N) operations to prescribed accuracy; this overhead thus peaks at intermediate sizes and vanishes in both limits.
ER -