Algebraic Signal Processing Theory

This page is organized into the following sections (click for navigation):

• Questions and answers
• Overview of published, submitted, and planned papers (journal only)
• Learning about the algebraic theory: Overview presentation and publication

Questions and answers

We give some answers to the following questions:

• What is the algebraic signal processing theory?
• What is the scope of the algebraic theory?
• What does the algebraic theory enable me to do that I could not do before?
• How accessible is the algebraic theory (how much math do I need)?

What is the algebraic signal processing theory? The algebraic signal processing theory is a new approach to and an extension of linear signal processing (henceforth called SP), that is, SP built around the concepts of filters, spectrum, Fourier transform, and others. The theory provides a general framework of signals, filtering, z-transform, Fourier transforms, etcetera. Well-known and new ways of doing SP are instantiations of this framework.

Examples of instantiations include discrete infinite and finite time and discrete infinite and finite space in one and higher dimensions, separable and non-separable. A glimpse is shown in the table. In the left column is the generic theory, the four right columns are instantiations. Note that every instantiation has a "z-transform." Also note that the discrete cosine and sine transforms DCTs/DSTs) are Fourier transforms in the theory. Some of the concepts in this table are introduced in the papers below. For a more detailed overview, please see the overview presentation or papers below.

What is the scope of the algebraic theory? The algebraic signal processing theory is a theory of linear signal processing. This means, signal processing built around concepts like filters, convolution, spectrum, Fourier transform and others. The theory also addresses linear statistical signal processing, i.e., Gauss-Markov random fields. Within linear SP, the theory aims to be very general. You can think of it as an expansion of the above table: we add rows for the generic theory for the concepts of spectrum, frequency response, filterbanks, multiresolution analysis, sampling theorem, etc.; we add columns for various instantiations of the generic theory in one and higher dimensions.

What does the algebraic theory enable me to do that I could not do before? Here are a few applications of the algebraic theory: (1) The discovery, concise derivation, and classification the many existing and many new fast transform algorithms. Examples. (2) The derivation of new transforms for non-separable SP in two dimensions. Examples. (3) Identification of the proper notions of z-transform, signal and filter space, and convolution for all trigonometric transforms. See papers below. (4) Insight into the need for and common choices of boundary conditions and signal extension (e.g., why periodic for finite time?). See papers below.

How accessible is the algebraic theory (how much math do I need)? As the name suggest, the theory connects signal processing and algebra, specifically the representation theory of algebras. However, it does not really introduce concepts new to SP, but rather generalizes well-known concepts such as filtering, spectrum, and Fourier transform. Working with (meaning actually using) the theory, as done in the below papers, requires only knowledge of polynomials and basic linear algebra, such as computing a base change.

Overview of published, submitted and planned papers

We plan to develop all aspects of the algebraic signal processing theory in a series of papers that address all aspects of linear signal processing (SP), including the basics (such as filtering, spectrum, frequency response, Fourier transforms, fast algorithms, sampling theorems) and more advanced ones (such as filterbanks, multiresolution analysis, uncertainty, frames). Here is an overview of the first set with comments (journal papers only):

• Algebraic signal processing theory: Foundation and 1-D time (submitted)
• Algebraic signal processing theory: 1-D Space (submitted)
• Algebraic signal processing theory: Cooley-Tukey type algorithms for the DCTs and DSTs (to appear in IEEE Transactions on Signal Processing)
• Algebraic signal processing theory: 2-D spatial hexagonal lattice (IEEE Transactions on Image Processing, based on conference papers)
• Algebraic signal processing theory: Cooley-Tukey algorithms on the 2-D spatial hexagonal lattice (to appear in AAECC, based on conference papers)
• Algebraic signal processing theory: Sampling in 1-D space (in writing, based on conference paper)
• Algebraic signal processing theory: 2-D spatial quincunx lattice (based on conference papers)
• Algebraic signal processing theory: 1-D Rader type algorithms
• Algebraic signal processing theory: 1-D Cooley-Tukey type algorithms, part III
• Algebraic signal processing theory: m-D spatial simplex lattice

Filterbanks, multiresolution analysis, and other topics are under research.

Learning about the algebraic theory: Overview presentation and publication

To learn about the algebraic signal processing theory you can do the following (ordered by increasing level of effort):

• Read the above
• Look at an overview presentation I gave so far at MIT (Boston), EPFL (Lausanne), UIUC (Champaign), Rice (Houston), and TU Munich
• Read these recent overview papers: ICASSP 2006 or DSP workshop 2006
• Read the first long introductory paper: Algebraic Signal Processing Theory. Parts of this paper are submitted for publication.
• Ask for preprints of any of the submitted papers below: email to pueschel (at) ece.cmu.edu

Papers submitted so far:

• Markus Püschel and José Moura
  Algebraic Signal Processing Theory: Foundation and 1-D Time
  submitted for publication, part of this monograph
  

  This paper presents an algebraic theory of linear signal processing. At the core of algebraic signal processing is the concept of a linear signal model defined as a triple (A, M, Phi), where familiar concepts like the filter space and the signal space are cast as an algebra A and a module M, respectively, and Phi generalizes the concept of the z-transform to bijective linear mappings from a vector space of, e.g., signal samples, into the module M. A signal model provides the structure for a particular linear signal processing application, such as infinite and finite discrete time, or infinite or finite discrete space, or the various forms of multidimensional linear signal processing. As soon as a signal model is chosen, basic ingredients follow, including the associated notions of filtering, spectrum, and Fourier transform.

  The shift operator, which is at the heart of ergodic theory and dynamic systems, is a key concept in the algebraic theory: it is the generator of the algebra of filters A. Once the shift is chosen, a well-defined methodology leads to the associated signal model. Different shifts correspond to infinite and finite time models with associated infinite and finite z-transforms, and to infinite and finite space models with associated infinite and finite C-transforms (that we introduce). In particular, the 16 discrete cosine and sine transforms become Fourier transforms for the finite space models. Other definitions of the shift naturally lead to new signal models and to new transforms as associated Fourier transforms in one and higher dimensions, separable and non-separable.

  We explain in algebraic terms shift-invariance (the algebra of filters A is commutative), the role of boundary conditions and signal extensions, and several other concepts and connections. Finally, the algebraic theory is a means to discover, concisely derive, explain, and classify fast transform algorithms.

• Markus Püschel and José Moura
  Algebraic Signal Processing Theory: 1-D Space
  submitted for publication, part of this monograph
  

  The algebraic signal processing theory developed in [1] is a general approach to linear signal processing. The theory is built on top of the concept of a signal model, which is defined as the triple (A, M, Phi), where A is a chosen algebra of filters, M an associated A-module of signals, and Phi a generalization of the z-transform. We showed that infinite and finite discrete time are examples of signal models in this sense.

  In this second paper, we develop a theory of infinite and finite 1-D space signal processing. We derive the corresponding signal models completely analogous to the time models in [1], but starting from a different definition of the shift operator, called the space shift. The space shift is symmetric and thus the obtained models are undirected in contrast to the directed time models. Associated with the space models are the infinite and finite C-transform, proper notions of filtering or convolution, spectrum, and Fourier transforms. These concepts are different from the ones associated with the standard time models. For the finite space model we discover the 16 discrete cosine and sine transforms (DCTs and DSTs) as associated Fourier transforms. We also introduce a more general notion of space model based on the generic next neighbor shift.

  Finally, we investigate the relationship between algebraic signal models and Gauss-Markov random fields and establish conditions for equivalence. In these cases, the notions of Fourier transform (in the general sense of the algebraic theory) and Karhunen-Loève transform (KLT) coincide. As an example, the DCTs and DSTs are established as (exact) KLTs.

• Markus Püschel and José Moura
  Algebraic Signal Processing Theory: Cooley-Tukey Type Algorithms for DCTs and DSTs
  to appear in IEEE Transactions on Signal Processing
  

  This paper presents a systematic methodology based on the algebraic signal processing theory to classify and derive fast algorithms for linear transforms. Instead of manipulating the entries of transform matrices, our approach derives the algorithms by stepwise decomposition of the associated signal models, or polynomial algebras. This decomposition is based on two generic methods or algebraic principles that generalize the well-known Cooley-Tukey FFT and make the algorithms' derivations concise and transparent. Application to the 16 discrete cosine and sine transforms yields a large class of fast algorithms, many of which have not been found before.

• Markus Püschel and Martin Rötteler
  Algebraic Signal Processing Theory: 2-D Spatial Hexagonal Lattice
  IEEE Transactions on Image Processing, Vol. 16, No. 6, pp. 1506-1521
  

  We develop the framework for signal processing on a spatial, or undirected, 2-D hexagonal lattice for both an infinite and a finite array of signal samples. This framework includes the proper notions of z-transform, boundary conditions, filtering or convolution, spectrum, frequency response, and Fourier transform. In the finite case, the Fourier transform is called discrete triangle transform (DTT). Like the hexagonal lattice, this transform is nonseparable. The derivation of the framework makes it a natural extension of the algebraic signal processing theory that we recently introduced. Namely, we construct the proper signal models, given by polynomial algebras, bottom-up from a suitable definition of hexagonal space shifts using a procedure provided by the algebraic theory. These signal models, in turn, then provide all the basic signal processing concepts. The framework developed in this paper is related to Mersereau's early work on hexagonal lattices in the same way as the discrete cosine and sine transforms are related to the discrete Fourier transform---a fact that will be made rigorous in this paper.

• Markus Püschel and Martin Rötteler
  Algebraic Signal Processing Theory: Cooley-Tukey Type Algorithms on the 2-D Spatial Hexagonal Lattice
  to appear in Applicable Algebra in Engineering, Communication and Computing, special issue in memory of Thomas Beth

  Recently, we introduced the framework for signal processing on a 2-D hexagonal spatial lattice. Spatial means that the lattice is undirected in contrast to the directed lattices that were studied by Mersereau. The framework includes the proper notions of filter and signal space, "z-transform," convolution, spectrum, and Fourier transform. The latter we termed discrete triangle transform (DTT). The DTT is a nonseparable 2-D transform. The derivation of the framework uses the algebraic signal processing theory. This means that the above concepts are obtained by constructing polynomial algebras with suitable structure.

  In this paper, we derive general-radix algorithms for the DTT, focusing on the radix-2x2 case. The derivation is based on a stepwise decomposition of the polynomial algebra underlying the DTT. The 1-D equivalent of this technique underlies a large class of 1-D transform algorithms including the Cooley-Tukey FFT. The obtained DTT algorithm has a runtime of O(n^2 log(n)). This puts the DTT into the same complexity class as its separable counterparts.