# Fast DCT+: A Family of Fast Transforms Based on Rank-One Updates of the Path Graph

arXiv: https://arxiv.org/abs/2409.08970 · HTML: https://mlsanity.com/paper/2409.08970/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Sep 2024.

## Built on by (most cited first, 4 of 4)

- [Variable-size Symmetry-based Graph Fourier Transforms for image compression](https://mlsanity.com/paper/2411.15824/) (2024)
- [Image Coding for Machines via Feature-Preserving Rate-Distortion Optimization](https://mlsanity.com/paper/2504.02216/) (2025)
- [L2G-Net: Local to Global Spectral Graph Neural Networks via Cauchy Factorizations](https://mlsanity.com/paper/2602.18837/) (2026)
- [Low-rank Updates in Slowly Time-varying Graphs for Spatial-Temporal Signal Interpolation](https://mlsanity.com/paper/2606.24011/) (2026)

## Abstract (arXiv)

This paper develops fast graph Fourier transform (GFT) algorithms with O(n log n) runtime complexity for rank-one updates of the path graph. We first show that several commonly-used audio and video coding transforms belong to this class of GFTs, which we denote by DCT+. Next, starting from an arbitrary generalized graph Laplacian and using rank-one perturbation theory, we provide a factorization for the GFT after perturbation. This factorization is our central result and reveals a progressive structure: we first apply the unperturbed Laplacian's GFT and then multiply the result by a Cauchy matrix. By specializing this decomposition to path graphs and exploiting the properties of Cauchy matrices, we show that Fast DCT+ algorithms exist. We also demonstrate that progressivity can speed up computations in applications involving multiple transforms related by rank-one perturbations (e.g., video coding) when combined with pruning strategies. Our results can be extended to other graphs and rank-k perturbations. Runtime analyses show that Fast DCT+ provides computational gains over the naive method for graph sizes larger than 64, with runtime approximately equal to that of 8 DCTs.