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

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

Proposal Summary In this research, we propose to use group representation theory to generate automatically fast algorithms for digital signal processing (DSP) transforms. Group representation theory provides a deeper understanding of the structure of signal transforms and a context to address fundamental questions in modeling and processing of signals. We propose to use representation theory to design new 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 code generator block to produce optimized software implementations for a given computer. SPIRAL applies iteratively fast algorithms, the algorithmic rules, to generate a rich collection of alternative equivalent formulas (the formula space) for the same DSP algorithm. For each formula, SPIRAL then produces automatically optimized code that runs efficiently on the given computer. By searching 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 automatic generation of the fast algorithm, or algorithmic rules. This meta-level is the focus of our proposed research. We exploit group representation theory to develop the theoretical framework and the tools that produce automatically these fast algorithms for a number of DSP transforms. We will implement and interface these tools to a DSP-AL (SPIRAL) which will enable us to translate directly 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 transform is invariant; decomposing stepwise the representations, giving rise to factorized decomposition ma- trices, which determine the factorization of the transform. The symmetry catches redundancy in the 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 decomposition matrices will be derived in the context of a constructive extension of standard representation theory, 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 package for symbolic computation with group representations and structured matrices and interface it with a DSP-AL, namely SPIRAL. We consider different types of "symmetry," going beyond regular representations to include arbitrary permutation and monomial representations, in order to capture in the representation framework a wide class of signal transforms. Besides the DFT, and trigonometric transforms, we will 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 transform can be justified on the basis of the model underlying the data. We have shown this relation to be connected to the boundary conditions (b.c.) assumed in describing a certain class of models widely used 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 signal transform, and the signal models, enabling us to address some fundamental questions, namely how to design a signal transform which is adapted to a given signal model (i.e., reflects a desired symmetry) and is computationally the most efficient.