The Algebraic Structure of Linear Transforms
The Algebraic Structure of Linear Transforms
批准号:
0310941
负责人:
Markus Pueschel
金额:
$29.15万
依托单位国家:
美国
项目类别:
Continuing Grant
财政年份:
2003
资助国家:
美国
项目状态:
已结题
起止时间:
2003-09-01 至 2007-08-31
中文摘要
【摘要】离散信号处理(DSP)变换,例如离散傅立叶变换(DFT)或离散余弦变换(DCT),是构成信号处理许多实际应用基础的主要工具。推导和理解它们的快速算法一直是并将继续是一个主要的研究重点。众所周知,DFT可以在循环群表示理论的框架内进行表征。这种联系提供了对DFT的深入了解,更重要的是,提供了理解、简明地推导和分析其快速算法的工具。本研究的第一个目标是为其他变换开发相应的代数框架,特别是16个离散三角变换(DTT): 8个离散余弦变换和8个离散正弦变换。研究人员在多项式代数表示理论的框架下对dts进行了表征,并发展了通过操作代数而不是变换矩阵项来推导dts快速算法的理论和方法。这种代数方法解决了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.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
Algebraic Signal Processing Theory: Towards Multiresolution Analysis
-
批准号:0634967
-
项目类别:Standard Grant
-
资助金额:$0.0万
-
财政年份:2006
-
负责人:Markus Pueschel
-
依托单位:
SOFTWARE: ACR: Advanced Code Generation for Digital Signal Processing Algorithms
-
批准号:0234293
-
项目类别:Continuing Grant
-
资助金额:$45.0万
-
财政年份:2003
-
负责人:Markus Pueschel
-
依托单位:
海外基金