18-899 Adv. Topics in Signal Processing: Algebraic Signal Processing

(12 Units, 1st offering Spring 2004, not taught regularly, graduate course, satisfies ECE coverage requirements) Traditionally,


Digital Signal Processing (DSP) is taught and learned through formulas and summations. Fast algorithms, for example, the FFT, are introduced through intricate index manipulations. The underlying structure is lost with so many fast algorithms dispersed in the literature for the various linear transforms; no wonder it is more of an art of ingenious tricks to develop new fast algorithms. DSP can be understood in a different light, if only we ventured past Linear Algebra and Vector Spaces. Yes, Linear Algebra provides a beautiful geometric picture. But, going beyond illuminates much of the structure underlying many of the transforms and their fast algorithms, and provides a powerful systematization of many apparently disparate algorithms. This course will introduce basic concepts in Algebra with a focus on groups, representations, modules, algebras, and related topics. Applications covered in the course will include linear transforms, particular emphasis on the DFT and trigonometric transforms, their fast algorithms, but include others as well, possibly, in Statistics, for example, from Kendall’s Shape Theory. Students are encouraged to explore their own preferred topics or other directions. On transforms, students will experiment with their fast implementations using SPIRAL. The course will mix formal lectures with discussions of research papers. This is the first time ever this course is offered at CMU, and it is most likely also a first at most other places, so there is ample opportunity for adapting to the students particular interests. Prerequisites: good understanding of Linear Algebra.