Group Representations and Automatic Generation of Fast Algorithms for Discrete Signal Transforms

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

Proposal SummaryIn this research, we propose to use group representation theory to generate automatically fastalgorithms for digital signal processing (DSP) transforms. Group representation theory provides adeeper understanding of the structure of signal transforms and a context to address fundamentalquestions in modeling and processing of signals. We propose to use representation theory to designnew transforms with desirable characteristics.Our work is at the meta-level of DSP algorithm libraries (DSP-AL), like SPIRAL, [23]. SPI-RAL is a library of DSP algorithms that concatenates a formula generator block with a codegenerator block to produce optimized software implementations for a given computer. SPIRALapplies iteratively fast algorithms, the algorithmic rules, to generate a rich collection of alternativeequivalent formulas (the formula space) for the same DSP algorithm. For each formula, SPIRALthen produces automatically optimized code that runs efficiently on the given computer. Bysearching over the formula space, SPIRAL generates automatically the formula and correspond-ing code implementation that matches in an optimized sense the algorithm to the hardware.What SPIRAL, or any other existing DSP-AL for that matter, does NOT do is the automaticgeneration of the fast algorithm, or algorithmic rules. This meta-level is the focus of our proposedresearch. We exploit group representation theory to develop the theoretical framework and thetools that produce automatically these fast algorithms for a number of DSP transforms. We willimplement and interface these tools to a DSP-AL (SPIRAL) which will enable us to translatedirectly a fast DSP algorithm as generated by our tools to an efficient low-level language program.Generating a fast discrete signal transform, given as a matrix, consists of two steps: determin-ing the "symmetry" of the transform, which is a pair of representations under which the transformis invariant; decomposing stepwise the representations, giving rise to factorized decomposition ma-trices, which determine the factorization of the transform. The symmetry catches redundancy inthe transform, and the decomposition of the representations turns the redundancy into a factoriza-tion of the transform - the fast algorithm. To realize this program, new results on decompositionmatrices will be derived in the context of a constructive extension of standard representationtheory, where representations are manipulated up to equality, not only up to equivalence.We will implement the algorithm for generating fast discrete signal transforms within a packagefor symbolic computation with group representations and structured matrices and interface it witha DSP-AL, namely SPIRAL.We consider different types of "symmetry," going beyond regular representations to includearbitrary permutation and monomial representations, in order to capture in the representationframework a wide class of signal transforms. Besides the DFT, and trigonometric transforms, wewill consider other transforms including wavelet transforms.We use the group representation framework to explore the connection between the "symmetry"of a signal transform and its properties with respect to signal processing. The use of a transformcan be justified on the basis of the model underlying the data. We have shown this relation to beconnected to the boundary conditions (b.c.) assumed in describing a certain class of models widelyused in applications. These b.c.'s also reflect the type of "data extension" that is hypothesized,for example, cyclic b.c.'s versus signal periodic extension versus the discrete Fourier transform.This proposal will exploit the relations between the "symmetry" of the representation, the signaltransform, and the signal models, enabling us to address some fundamental questions, namelyhow to design a signal transform which is adapted to a given signal model (i.e., reflects a desiredsymmetry) and is computationally the most efficient.