Algebraic Signal Processing Theory
18-799F (CMU, ECE), 21-624 (CMU, Math)
- Course number: 18-799F (ECE), 21-624 (Math)
- Spring 2007, MW 2:30pm--4:20 pm WEH 5328
- Instructor: Markus Püschel (PH B16, pueschel at ece, 8-4259)
TA: Aliaksei Sandryhaila (PH B8, asandryh at andrew)
Admin: Carol Patterson (PH B15, carol at ece, 8-7286)
- 12 units
- Office hours: Markus Püschel (B16, Tuesdays 2-3pm), Aliaksei Sandryhaila (PH B8, Fridays 2-3pm)
- Requirements: (ECE students) Signals & Systems, Matrix algebra, one grad SP course; (Math students) Linear algebra
The topic of this course is a new approach to the foundation of linear signal processing (SP), termed algebraic signal processing theory (ASP), that was developed by the instructor and his collaborators. Linear signal processing is built around the fundamental concepts of signals, filters, spectrum, z-transform, Fourier transforms, and many others. ASP generalizes these concepts, and thus linear SP, to provide a unifying approach to many existing SP methods and to enable the derivation of many new ones. This is made possible through the connection between linear SP and abstract algebra that ASP reveals and explores.
Specifically, the course will provide a new look at standard time SP but then introduce various other forms of SP including the non-standard space SP in one and higher dimensions, separable and nonseparable. In each case there will appropriate z-transforms, Fourier transforms, etc. These different SP methods will be derived as instantiations of the general, axiomatic ASP theory. ASP provides detailed insights into existing and novel transforms, their properties, and their fast algorithms, and naturally connects to linear statistical SP (Gauss-Markov random fields and Karhunen-Loeve transforms) as will be discussed in detail. Other topics will include uncertainty relations, sampling theorems, and shift-variant SP.
The course is mathematical in nature. The mathematics needed for ASP will be introduced in the course and learned through concrete exercises. In particular, no background in abstract algebra is needed. The instructor's emphasis regarding math is "hands-on" rather than "abstract."
The course is targeted for graduate students who are interested in enhancing their understanding of the foundation of SP. For any questions please contact the instructor.
- Background: Refresher in linear algebra
- Background: Basic understanding of abstract algebra including rings, algebras, modules, and groups
- The general SP framework provided by ASP; the crucial role of polynomial algebras in SP
- Novel forms of z-transforms, convolutions, Fourier transforms in 1-D and 2-D, separable and non-separable
- 1-D and 2-D Space SP versus time SP
- Detailed understanding of existing and novel transforms including properties and fast algorithms
- Gauss-Markov random fields and ASP
Goals of this Course
- Get a deeper understanding of existing and novel ways of doing linear signal processing (SP)
- Expand your math knowledge: better understanding of linear algebra, basics of commutative and maybe some non-commutative (abstract) algebra
Textbook and other Background Material
There is no textbook for this class.
- 40% homework
- 20% midterm
- 30% project
- 10% attendance
- Template for 4 page paper:
- Everybody reads this: conference.pdf
- For latex use: conference-latex.tgz
- Creating bibliography: latex conference; bibtex conference; latex conference
- Creating a pdf: dvips -t letter -o conference.ps -Ppdf -G0 conference.dvi; ps2pdf conference.ps
- For Word (discouraged) use this: conference-word.doc
- first version of paper due on April 30th (intro, background complete, most of the rest complete); I'll give feedback
- presentations May 2nd
- final version of paper due: May 6th
Here are the selected research projects.
- Asymptotic properties of transforms and their underlying signal models (Doru and Satashu): slides.
- Application study of known and novel transforms (Eak and Peter): slides.
- New algorithms for RDFT and its variants and for lapped transforms (Frederic and Yevgen): slides.
Lectures (including pdfs, paper links may need CMU IP)
- 1. Lecture (17. Jan): Technicalities (slides), a glimpse of ASP
- 2. Lecture (22. Jan): Functions, equivalence relations, the issue of "well-defined," glimpse of (abstract) algebra, groups: definition and generators (notes)
- 3. Lecture (24. Jan): Groups: subgroups, factor groups, homomorphisms, kernel, homomorphism theorem, short history of group theory (notes)
- 4. Lecture (29. Jan): Rings: definition, ideals, homomorphisms, homomorphism theorem (notes)
- 5. Lecture (31. Jan): Types of rings, Euclidean algorithm (notes)
- 6. Lecture (05. Feb): Vector spaces: definition, generators/basis, subspaces (notes)
- 7. Lecture (07. Feb): more on subspaces, linear mappings (notes)
- 8. Lecture (12. Feb): Cartesian products, Chinese remainder theorem (notes)
- 9. Lecture (14. Feb): Coordinatization of vectors and linear mappings (notes)
- 10.-12. Lecture (19./21./26. Feb): Short history of linear algebra, foundation of ASP: algebraic structure in SP, filter and signal space, spectrum, Fourier transform, frequency response, signal model, shift invariance, visualization (notes)
- 13. Lecture (28. Feb): Signal processing on polynomial algebras, or, finite, shift-invariant, 1-D signal models (notes)
- 14. Lecture (05. Mar): Derivation of signal models from the shift, infinite and finite time (notes)
- 15. Lecture (07. Mar): Midterm
- 16. Lecture (19. Mar): finite, real 1-D time model, infinite 1-D space model (notes)
- 17. Lecture (21. Mar): finite space models, DCTs/DSTs, example DCT-3 (notes)
- 18. Lecture (26. Mar): more on finite space models, example DCT-2, DTT relationships, unitary/orthogonal matrices (notes)
- 19. Lecture (28. Mar): orthogonal DTTs, generic next neighbor model, orthogonal polynomials (notes)
- 20. Lecture (02. Apr): fast transform algorithms, based on this paper.
- 21. Lecture (04. Apr): relation between regular signal models, weighted graphs, Markov chains, and matrices (notes)
- 22./23. Lecture (09./11. Apr): on the equivalence of (algebraic) signal models and Gauss-Markov random fields (notes)
- 24. Lecture (16. Apr): finite, shift-invariant 2-D signal models, or, polynomial algebras in 2 variables (notes)
- 25. Lecture (18. Apr): cancelled, replaced by one-on-one meetings
- 26. Lecture (23. Apr): Tensor product of vector spaces, algebras, and signal models; Nonseparable spatial quincunx model (notes)
- 27. Lecture (25. Apr): Nonseparable spatial quincunx model based on this paper (notes)
- 28. Lecture (30. Apr): Overview of things we could not cover: continuous signal models (e.g., 1-D space), sampling, downsampling (notes)
- 29. Lecture (02. May): Research project presentations