compendium

A. Sandryhaila, J. Kovačević and M. Püschel. Algebraic signal processing theory: Cooley-Tukey type algorithms for polynomial transforms based on induction. SIAM J. Matrix Anal. Appl., 32(2):364-384, 2011.

[ pdf | @ SIAM website | bibtex]

A polynomial transform is the multiplication of an input vector x ∈ Cⁿ by a matrix P_b,α ∈ C_n×n, whose (k,l)-th element is defined as p_l(αk) for polynomials p_l(x) ∈ C[x] from a list b = {p₀(x),...,p_n-1(x)} and sample points α_k ∈ C from a list α = {α₀,...,α_n-1}. Such transforms find applications in the areas of signal processing, data compression, and function interpolation. Important examples include the discrete Fourier and cosine transforms. In this paper we introduce a novel technique to derive fast algorithms for polynomial transforms. The technique uses the relationship between polynomial transforms and the representation theory of polynomial algebras. Specifically, we derive algorithms by decomposing the regular modules of these algebras as a stepwise induction. As an application, we derive novel O(n logn) general-radix algorithms for the discrete Fourier transform and the discrete cosine transform of type 4.

matlab

This work is licensed under a Creative Commons GNU General Public License. To view a copy of this license, visit http://creativecommons.org/licenses/GPL/2.0. If you use this code or any part thereof in your research or publication, please also include a reference to this paper. Thank you!

All necessary proofs are included in the paper.