Computer Science – Information Theory
Scientific paper
2010-08-17
SIAM J. Matrix Analysis and Appl. 32 (2) pp. 364-384, 2011
Computer Science
Information Theory
19 pages. Submitted to SIAM Journal on Matrix Analysis and Applications
Scientific paper
A polynomial transform is the multiplication of an input vector $x\in\C^n$ by a matrix $\PT_{b,\alpha}\in\C^{n\times n},$ whose $(k,\ell)$-th element is defined as $p_\ell(\alpha_k)$ for polynomials $p_\ell(x)\in\C[x]$ from a list $b=\{p_0(x),\dots,p_{n-1}(x)\}$ and sample points $\alpha_k\in\C$ from a list $\alpha=\{\alpha_0,\dots,\alpha_{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\log{n})$ general-radix algorithms for the discrete Fourier transform and the discrete cosine transform of type 4.
Kovacevic Jelena
Pueschel Markus
Sandryhaila Aliaksei
No associations
LandOfFree
Algebraic Signal Processing Theory: Cooley-Tukey Type Algorithms for Polynomial Transforms Based on Induction does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Algebraic Signal Processing Theory: Cooley-Tukey Type Algorithms for Polynomial Transforms Based on Induction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algebraic Signal Processing Theory: Cooley-Tukey Type Algorithms for Polynomial Transforms Based on Induction will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-503711