Abstract

ABSTRACT

Digital signal processing (DSP) is one of the key technologies used in nowadays world, found in devices and applications as diverse as multimedia, communications, biometrics, medical imaging, and many others. Most of the processing in DSP is linear, built around the use of filters and transforms, which effectively are linear mappings on discrete vector spaces. For finite length signals (the common case), transforms are hence matrix-vector multiplications.

Many different transforms are used in DSP including the discrete Fourier transform (DFT), various discrete cosine and sine transforms, and the discrete Hartley transform. For each of these transforms there is a large variety of fast algorithms available from the literature. These algorithms have been typically hand-derived by clever but complicated manipulation of the transform's matrix entries. In other words (with the exception of the DFT), there has been no theory that explains the existence or the structure of these algorithms.

In this talk we present an algebraic theory of transforms and transform algorithms. The algebraic theory identifies for each transform a group algebra or polynomial algebra. This knowledge then enables us to explain, categorize, concisely derive, and find new transform algorithms by manipulating the algebra rather than the matrix. In some cases, it is even possible to generate fast algorithms automatically from the transform's definition using a computer program. Finally, by understanding the connection between the algebraic structure of a transform and its DSP properties, it is possible to derive new transforms. As an example, we present a transform for DSP on a triangular lattice.

Please visit Research Details

Short Bio

Markus Pueschel 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 the Dept. of Mathematics and Computer Science, Drexel University. Since 2000 he has held a Research Faculty position at the Dept. of Electrical and Computer Engineering, Carnegie Mellon University. Dr. Pueschel is on the editorial board of the IEEE Signal Processing Letters and was a guest editor of the Journal of Symbolic Computation and of the Proceedings of the IEEE. His research interests include scientific computing, compilers, applied mathematics and algebra, and signal processing theory/software/hardware. More details can be found on

Pueschel

TUESDAY, November 30, 2004
Time: 1:30 P.M.
Location: PPB 300