“Algebraic Signal Processing Theory”

Abstract:
The talk gives an overview of a new, algebraic approach to linear signal processing (SP). At the core of algebraic signal processing is the concept of a linear signal model defined as a triple (A, M, phi), where familiar concepts like the filter space and the signal space are cast as an algebra A and a module M, respectively, and phi generalizes the concept of the z-transform to bijective linear mappings from a vector space into the module M. The algebraic point of view shows that the same algebraic structure induces many diverse theories of SP, such as infinite and finite discrete time and space, and multidimensional SP. As soon as a signal model is selected, all main SP ingredients follow, including the appropriate notions of z-transform filtering, spectrum, and Fourier transform, which take different forms for different signal models.
The algebraic theory identifies the shift operator q as a key concept and uniquely clarifies its role: the shift operator q is the generator of the algebra of filters A. Once the shift operation is defined, a well-defined procedure that we introduce leads to the definition of the associated signal model. Different choices of shift lead to infinite and finite time models with associated infinite and finite z-transforms, and to infinite and finite space models with associated infinite and finite C-transforms (that we introduce), and to separable and nonseparable signal models for higher dimensions. In particular, we show that the discrete cosine and sine transforms are Fourier transforms for the finite space model. Other definitions of the shift lead to new signal models and to new transforms as associated Fourier transforms. Finally, the algebraic theory provides the means to discover, concisely derive, explain, and classify fast transform algorithms.

More information on the topic is available here.

Biography:
Markus Püschel is a Professor of Computer Science at ETH Zurich, Switzerland. Before, he was a Professor of Electrical and Computer Engineering at Carnegie Mellon University, where he still has an adjunct status. He received his Diploma (M.Sc.) in Mathematics and his Doctorate (Ph.D.) in Computer Science, in 1995 and 1998, respectively, both from the University of Karlsruhe, Germany. From 1998-1999 he was a Postdoctoral Researcher at Mathematics and Computer Science, Drexel University. From 2000-2010 he was with Carnegie Mellon University, and since 2010 he has been with ETH Zurich. He was an Associate Editor for the IEEE Transactions on Signal Processing, the IEEE Signal Processing Letters, was a Guest Editor of the Proceedings of the IEEE and the Journal of Symbolic Computation, and served on various program committees of conferences in computing, compilers, and programming languages. He is a recipient of the Outstanding Research Award of the College of Engineering at Carnegie Mellon and the Eta Kappa Nu Award for Outstanding Teaching. He also holds the title of Privatdozent at the University of Technology, Vienna, Austria. In 2009 he cofounded Spiralgen Inc.
His research interests include program synthesis with the goal of high performance, fast computing, algorithms, applied mathematics, and signal processing theory/software/hardware.

More information on the speaker can be found here.