The Algebraic Structure of Linear Transforms

离散信号处理（DSP）变换，例如离散傅里叶变换（DFT）或离散余弦变换（DCT），是许多信号处理实际应用的基础。 推导和理解他们的快速算法一直是并将继续是一个主要的研究重点。众所周知，DFT可以在循环群的表示理论的框架下刻画。这种联系提供了对DFT的深入了解，更重要的是，提供了理解、简明推导和分析其快速算法的工具。本研究的第一个目标是为其他变换，特别是为16个离散三角变换（DTT）：8个离散余弦变换和8个离散正弦变换开发相应的代数框架。 研究人员在多项式代数表示理论的框架内描述了DTT的特征，并开发了通过操纵代数而不是变换矩阵项来推导DTT快速算法的理论和方法。这种代数方法解决了DSP算法理论中的一个大空白：尽管有许多关于快速DTT算法的出版物，但还没有通用理论来解释为什么这些算法存在或深入了解它们的结构。 该研究将为DTT算法开发一个全面的代数框架，为快速算法提供简洁和透明的推导。更重要的是，代数方法是发现新算法的适当框架，这些新算法在传统方法中找不到--最近，研究人员使用这些代数方法推导出了新的一类Cooley-Tukey FFT DCT算法。研究的第二个目标是扩展代数和信号处理变换之间的联系，超越快速算法的推导，以考虑基于变换的信号处理代数的基本问题。研究者追求以下方向：（1）通过将信号处理概念与代数概念联系起来，正式发展代数与信号处理之间的联系，从而建立基础;（2）推广代数方法，以导出一维和多维应用中的新变换及其快速算法;（3）在代数框架中描述DFT和DTT之外的变换，总之，本研究的目标是建立线性变换及其快速算法的通用代数基础。

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.