Algebraic Signal Processing Theory
Discrete Lattice Transforms
DCT/DST Algorithms
Automatic Generation of Transform Algorithms
Algorithms and Implementations
Other work

Algebraic Signal Processing Theory

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

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.

Learning about the algebraic theory

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