Fast DCT+: A Family of Fast Transforms Based on Rank-One Updates of the Path Graph
<|reference_start|>Fast DCT+: A Family of Fast Transforms Based on Rank-One Updates of the Path Graph: 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.<|reference_end|>
@article{fernández-menduiña2024fast,
    title={Fast DCT+: A Family of Fast Transforms Based on Rank-One Updates of the
  Path Graph},
    author={Samuel Fern'andez-Mendui~na, Eduardo Pavez, Antonio Ortega},
    journal={arXiv preprint arXiv:2409.08970},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.08970},
    primaryClass={eess.SP cs.DS}
}