Algebraic signal processing theory: Cooley-tukey-type algorithms for polynomial transforms based on induction

Aliaksei Sandryhaila, Jelena Kovačević, Markus Püschel

Research output: Contribution to journalArticle

Abstract

A polynomial transform is the multiplication of an input vector x ∈ ℂn by a matrix Pb α ∈ C n×n, whose (k; l)th element is defined as plk) for polynomials pl(x) ∈ ℂ [x] from a list b = {p 0(x);..., pn-1(x)} and sample points α k∈ℂ from a list α - {a0...., αn-1}. Such transforms find applications in the areas of signal processing, data compression, and function interpolation. An important example includes the discrete Fourier transform. 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.

Original languageEnglish (US)
Pages (from-to)364-384
Number of pages21
JournalSIAM Journal on Matrix Analysis and Applications
Volume32
Issue number2
DOIs
StatePublished - 2011

Keywords

  • Algebra
  • Discrete Fourier transform
  • Discrete cosine transform
  • Discrete sine transform
  • Fast Fourier transform
  • Fast algorithm
  • Matrix factorization
  • Module
  • Polynomial transform

ASJC Scopus subject areas

  • Analysis

Fingerprint Dive into the research topics of 'Algebraic signal processing theory: Cooley-tukey-type algorithms for polynomial transforms based on induction'. Together they form a unique fingerprint.

  • Cite this