Metraipolis › archive › dc_34def7bf0b6d

Direct Factorization of the Karhunen-Loève Transform of AR(1) Sources — arXiv:2608.06522

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.06522
License (as archived)
CC0-1.0
Archived
2026-10-21T07:13:03.485Z
SHA-256 of the archived text
300dc2d5deab61595ff3abfcd2825b657cf60e3eb17146ca3f92977bbc1edc02
Stable URL of this page
https://metraipolis.com/documento/dc_34def7bf0b6d

How to cite

Direct Factorization of the Karhunen-Loève Transform of AR(1) Sources — arXiv:2608.06522 — arXiv (en), https://arxiv.org/abs/2608.06522 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_34def7bf0b6d (Metraipolis archive dc_34def7bf0b6d, sha256 300dc2d5deab61595ff3abfcd2825b657cf60e3eb17146ca3f92977bbc1edc02)
BibTeX
@misc{dc34def7bf0b6d,
  title = {Direct Factorization of the Karhunen-Loève Transform of AR(1) Sources — arXiv:2608.06522},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.06522},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_34def7bf0b6d; sha256 300dc2d5deab61595ff3abfcd2825b657cf60e3eb17146ca3f92977bbc1edc02},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.06522. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

The Karhunen--Loève transform (KLT) of the stationary AR(1) source is the classical optimality benchmark of transform coding. Its frequencies are roots of the transcendental equations of Ray and Driver, and the transform has therefore long been treated as an unstructured dense matrix. Rather than compute the exact KLT, the field turned to fast approximations of it, most famously the discrete cosine transform (DCT). This paper shows that the retreat was premature. The exact AR(1) KLT admits direct recursive factorizations, at every order $N\ge2$ and every correlation coefficient $\rho\in(0,1)$: at even orders, the transform reduces to a butterfly stage, two half-order copies of itself, and orthogonal corrections generated by rank-one boundary perturbations of the covariance; at odd orders, to two copies of the KLT of the one-sided prediction residual and an arrowhead stage absorbing the center sample. The residual KLT recurses through half order as well. All correction stages are Cauchy-structured, and applying them by the fast multipole method yields exact-KLT algorithms of $O(N\log N)$ complexity---the same order as the FFT and the fast sinusoidal transforms. The factorizations follow from the covariance matrix by the Sherman--Morrison identity and the classical secular eigenvalue updates, and degenerate, as $\rho\to1$, to the known parity splittings of the DCT-II. As secondary results, the factorization constants are shown to be algebraic functions of $\rho$---in radicals for all $N\le8$---and complete exact KLT modules for $N=2,\dots,8$ are given.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-10 in math.IT).
Categorie arXiv: Information Theory (cs.IT).
Pagina del lavoro: https://arxiv.org/abs/2608.06522 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-21T07:07:31.132Z dalla pagina https://arxiv.org/catchup/math.IT/2026-08-10?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).