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 x 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 .
- Markus Püschel and José M. F. Moura, ““Algebraic Theory of Signal Processing: Foundation and 1D Time,” IEEE Transactions on Signal Processing, 56:8, pp. 3572-3585, August 2008; (IEEEXplore link here.) See also arxiv: 0612077v1[cs.IT] repository, extended version, 15 December 2006.
- Markus Püschel and José M. F. Moura, “Algebraic Theory of Signal Processing: 1D Space,” IEEE Transactions on Signal Processing, 56:8, pp. 3586-3599, August 2008; (IEEEXplore link here.) See also arxiv: 0612077v1[cs.IT] repository, extended version, 15 December 2006.
- Markus Püschel and José M. F. Moura, “Algebraic Theory of Signal Processing: Cooley-Tukey Type Algorithms for DCTs and DSTs,” IEEE Transactions on Signal Processing, 56: 4, pp. 1502-1521, April 2008; (IEEEXplore link here.) See also arxiv: 0702025v1[cs.IT] repository, 4 February 2007.
- Markus Püschel and José M. F. Moura, “The Algebraic Approach to the Discrete Cosine and Sine Tranforms and their Fast Algorithms,” SIAM Journal of Computing, vol 35:(5), pp. 1280-1316, March 2003.
- Markus Püschel and José M. F. Moura, “Understanding the Fast Algorithms for the Discrete Trigonometric Transforms,” IEEE Digital Signal Processing Workshop, Atlanta, Georgia. September 2002.