SMART

Many algorithms in digital signal processing are based on the use of linear discrete signal transforms. Mathematically, such a transform is a matrix-vector multiplication y=M .x where is the sampled signal, and M is the transform over some base field K. Crucial for the applicability of a signal transform M is the existence of fast algorithms that allow its computation with O(n\log n) operations (or better) compared to O(n^2) arising from a direct matrix-vector multiplication. The problem of finding these algorithms for different transforms has been a major research topic leading to a vast number of publications in signal processing and mathematics.

Probably the most famous example of a signal transform is the discrete Fourier transform (DFT), which is used in harmonic analysis to decompose a signal into its frequency components. Important algorithms for the DFT include the “fast Fourier transform” (FFT) found by Cooley/Tukey in 1965 (originally due to Gauss), Rader’s algorithm for prime size (1968), Winograd’s algorithms (1980), and several others.

Another important class of transforms consists of the 8 different types of discrete cosine and sine transforms (DCTs and DSTs), respectively, also called discrete trigonometric transforms
(DTTs). Their applications include image and video compression, (see the 1990 book by Rao). Important algorithms for the trigonometric transforms have been developed by many, including by Chen, Smith and Fralick (Chen:77), Wang (Wang:84), Yip and Rao (Yip:84,Yip:88), Vetterli and Nussbaumer (Vetterli:84), Lee (Lee:84), Feig (Feig:90), Chan and Ho (Chan:90), Steidl and Tasche (Steidl:91), and Feig and Winograd (Feig:92).

Each of these algorithms has been derived through insightful manipulation of the transform matrix entries. The algorithms are highly structured, a property that can be used to write them as sparse factorizations of the transform matrix in a very concise way using mathematical operators.

In SMART (see papers below), we present an algebraic approach to the class of the 16 trigonometric transforms in the framework of algebra representation theory. In particular, the work presents the discrete cosine and sine transforms as decomposition matrices of certain regular modules associated to four series of Chebyshev polynomials. SMART uses algebraic methods to derive most of their known fast algorithms. SMART gives insight into the structure and the existence of these algorithms and extends the relationship between signal processing and algebra that is currently mainly restricted to the discrete Fourier transform.

SMART has been supported by two grants from NSF, CISE Division, CCR Program.

SMART Papers

(For additional papers visit the SMART web site .