The Algebraic Structure of Linear Transforms

点击翻译按钮获取中文摘要

ABSTRACT0310941Pueschel, MarkusCarnegie Mellon UDiscrete signal processing (DSP) transforms, for example, the discrete Fourier transform (DFT) or the discrete cosine transform (DCT), are major tools that underlie many of the practical applications of signal processing. Deriving and understanding their fast algorithms has been and continues to be a major research thrust. It is well known that the DFT can be characterized in the framework of the representation theory of cyclic groups. This connection provides deep insight into the DFT and, more importantly, provides the tools to understand, concisely derive, and analyze its fast algorithms. The first goal of this research is to develop the corresponding algebraic framework for other transforms, in particular, for the sixteen discrete trignometric transforms (DTT): the eight discrete cosine transforms and eight discrete sine transforms. The investigators characterize the DTTs in the framework of representation theory of polynomial algebras and develop the theory and the methods to derive the DTTs fast algorithms by manipulating algebras rather than transform matrix entries. This algebraic approach addresses one of the large voids in the theory of DSP algorithms: despite the numerous publications on fast DTT algorithms there is yet no general theory that explains why these algorithms exist or that gives insight into their structure. The research will develop a comprehensive algebraic framework for the DTT algorithms that will provide a concise and transparent derivation of their fast algorithms. More importantly, the algebraic approach is the appropriate framework to discover new algorithms that have not been found with conventional methods--recently, the new class of Cooley-Tukey FFT like DCT algorithms was derived by the investigators using these algebraic methods. The second goal of the research is to extend the connection between algebra and signal processing transforms beyond the derivation of fast algorithms to consider the fundamental question of to what extent is transform-based signal processing algebraic. The investigators pursue the following directions: (1) establish the foundation by formally developing the connection between algebra and signal processing by relating signal processing concepts to algebraic concepts; (2) generalize the algebraic approach to derive new transforms and their fast algorithms for applications in one and more dimensions; and (3) to capture existing transforms beyond the DFT and the DTTs in an algebraic framework.In summary, the goal of this research is to work towards a universal algebraic foundation of linear transforms and their fast algorithms.