Copyrights to these papers may be held by the publishers. The download files are preprints. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
Aliaksei Sandryhaila, Jelena Kovacevic and Markus Püschel (IEEE Transactions on Signal Processing, Vol. 60, No. 5, pp. 2247-2259, 2012)
Algebraic Signal Processing Theory: 1-D Nearest-Neighbor Models
Preprint (241 KB)
Published paper (link to publisher)
Bibtex
We present a signal processing framework for the analysis of discrete signals represented as linear combinations of orthogonal polynomials. We demonstrate that this representation implicitly changes the associated shift operation from the standard time shift to the nearest-neighbor shift introduced in this paper. Using the algebraic signal processing theory, we construct signal models based on this shift and derive their corresponding signal processing concepts, including the proper notions of signal and filter spaces, z-transform, convolution, spectrum, and Fourier transform. The presented results extend the algebraic signal processing theory and provide a general theoretical framework for signal analysis using orthogonal polynomials.
Aliaksei Sandryhaila, Samir Saba, Markus Püschel and Jelena Kovacevic (IEEE Transactions on Signal Processing, Vol. 60, No. 2, pp. 947-955, 2012)
Efficient compression of QRS complexes using Hermite expansion
Preprint (1 MB)
Bibtex
We propose a novel algorithm for the compression of ECG signals, in particular QRS complexes. The algorithm is based on the expansion of signals with compact support into a basis of discrete Hermite functions. These functions can be constructed by sampling continuous Hermite functions at specific sampling points. They form an orthogonal basis in the underlying signal space. The proposed algorithm relies on the theory of signal models based on orthogonal polynomials. We demonstrate that the constructed discrete Hermite functions have important advantages compared to continuous Hermite functions, which have previously been suggested for the compression of QRS complexes. Our algorithm achieves higher compression ratios compared with previously reported algorithms based on continuous Hermite functions, discrete Fourier, cosine, or wavelet transforms.
Aliaksei Sandryhaila, Jelena Kovacevic and Markus Püschel (SIAM Journal on Matrix Analysis and Applications, Vol. 32, No. 2, pp. 364-384, 2011)
Algebraic Signal Processing Theory: Cooley-Tukey Type Algorithms for Polynomial Transforms Based on Induction
Preprint (232 KB)
Bibtex
A polynomial transform is the multiplication of an input vector $x\in\C^n$ by a matrix $\PT_{b,\alpha}\in\C^{n\times n},$ whose $(k,\ell)$-th element is defined as $p_\ell(\alpha_k)$ for polynomials $p_\ell(x)\in\C[x]$ from a list $b=\{p_0(x),\dots,p_{n-1}(x)\}$ and sample points $\alpha_k\in\C$ from a list $\alpha=\{\alpha_0,\dots,\alpha_{n-1}\}$. Such transforms find applications in the areas of signal processing, data compression, and function interpolation. Important examples include the discrete Fourier and cosine transforms. In this paper we introduce a novel technique to derive fast algorithms for polynomial transforms. The technique uses the relationship between polynomial transforms and the representation theory of polynomial algebras. Specifically, we derive algorithms by decomposing the regular modules of these algebras as a stepwise induction. As an application, we derive novel $O(n\log{n})$ general-radix algorithms for the discrete Fourier transform and the discrete cosine transform of type 4.
Aliaksei Sandryhaila, Jelena Kovacevic and Markus Püschel (Proc. IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), pp. 581-584, 2011)
Compression of QRS Complexes Using Hermite Expansion
Preprint (817 KB)
Published paper (link to publisher)
Bibtex
We propose an algorithm for the compression of ECG signals, in particular QRS complexes, based on the expansion of signals with compact support into a basis of discrete Hermite functions. These functions are obtained by sampling continuous Hermite functions, previously used for the compression of ECG signals. Our algorithm uses the theory of signal models based on orthogonal polynomials, and achieves higher compression ratios compared with algorithms previously reported, both those using Hermite functions, as well as those using the discrete Fourier and discrete cosine transforms.
Aliaksei Sandryhaila (PhD. thesis, Electrical and Computer Engineering, Carnegie Mellon University, 2010)
Algebraic Signal Processing: Modeling and Subband Analysis
Preprint (1.8 MB)
Bibtex
Traditional linear signal processing is based on viewing signals as sequences or functions in time that flow in one direction, from past through present into future. Somewhat surprisingly, the assumption that the most basic operation that can be performed on a signal is a time shift, or ``delay,'' is sufficient to derive many relevant signal processing concepts, including spectrum, Fourier transform, frequency response and others. This observation has led us to search for other linear, shift-invariant signal models that are based on a different definition of a basic signal shift, and hence have different notions of filtering, spectrum, and Fourier transform. Such models can serve as alternatives to the time signal model traditionally assumed in modern linear signal processing, and provide valuable insights into signal modeling in different areas of signal processing. The platform for our work is the algebraic signal processing theory, a recently developed axiomatic approach to, as well as a generalization of linear signal processing. In this thesis we present a new class of infinite and finite discrete signal models built on a new basic shift called the generic nearest-neighbor shift. We construct filter and signals spaces for these new models, and identify the corresponding signal processing concepts, such as frequency, spectrum, Fourier transform, frequency response, and convolution. We also derive relevant properties of these models, such as the Parseval equality and the notions of low and high frequencies. We then consider the problem of subband analysis for the newly constructed signal models. As a corresponding subband analysis tool for infinite signals, we extend the definition of filter banks to the new models, and construct perfect-reconstruction filter banks for subband decomposition. We also construct filter banks for robust signal transmission. As a subband analysis tool for finite signals, we study the implementation of appropriate discrete Fourier transforms. We propose a mathematical approach to the factorization of general discrete Fourier transform matrices, and apply it to construct fast computational algorithms for the Fourier transforms of interest. Finally, we consider possible applications of the constructed signal models in different areas of signal processing. For example, we demonstrate that the use of new signal models can be beneficial in such applications as the compression of ECG signals and the efficient implementation of widely-used discrete signal transforms, such as the discrete cosine transform.
Jelena Kovacevic and Markus Püschel (IEEE Transactions on Signal Processing, Vol. 58, No. 1, pp. 242-257, 2010)
Algebraic Signal Processing Theory: Sampling for Infinite and Finite 1-D Space
Preprint (586 KB)
Published paper (link to publisher)
Bibtex
We derive a signal processing framework, called space signal processing, that parallels time signal processing. As such, it comes in four versions (continuous/discrete, infinite/finite), each with its own notion of convolution and Fourier transform. As in time, these versions are connected by sampling theorems that we derive. In contrast to time, however, space signal processing is based on and derived from a different notion of shift, space shift, which operates symmetrically. Our work rigorously connects known and novel concepts into a coherent framework; most importantly, it shows that the sixteen discrete cosine and sine transforms are the space equivalent of the discrete Fourier transform, and hence can be derived by sampling. The platform for our work is the algebraic signal processing theory, an axiomatic approach and generalization of linear signal processing that we recently introduced.
Aliaksei Sandryhaila, Amina Chebira, Christina Milo, Jelena Kovacevic and Markus Püschel (IEEE Transactions on Signal Processing, Vol. 58, No. 5, pp. 2556-2567, 2010)
Systematic Construction of Real Lapped Tight Frame Transforms
Preprint (801 KB)
Bibtex
We present a constructive algorithm for the design of real lapped equal-norm tight frame transforms. These transforms can be efficiently implemented through filter banks and have recently been proposed as a redundant counterpart to lapped orthogonal transforms, as well as an infinite-dimensional counterpart to harmonic tight frames. The proposed construction consists of two parts: First, we design a large class of new real lapped orthogonal transforms derived from submatrices of the discrete Fourier transform. Then, we seed these to obtain real lapped tight frame transforms corresponding to tight, equal-norm frames. We identify those frames that are maximally robust to erasures, and show that our construction leads to a large class of new lapped orthogonal transforms as well as new lapped tight frame transforms.
Yevgen Voronenko and Markus Püschel (IEEE Transactions on Signal Processing, Vol. 57, No. 1, pp. 205-222, 2009)
Algebraic Signal Processing Theory: Cooley-Tukey Type Algorithms for Real DFTs
Preprint (324 KB)
Bibtex
In this paper we systematically derive a large class of fast general-radix algorithms for various types of real discrete Fourier transforms (real DFTs) including the discrete Hartley transform (DHT) based on the algebraic signal processing theory. This means that instead of manipulating the transform definition, we derive algorithms by manipulating the polynomial algebras underlying the transforms using one general method. The same method yields the well-known Cooley-Tukey FFT as well as general radix discrete cosine and sine transform algorithms. The algebraic approach makes the derivation concise, unifies and classifies many existing algorithms, yields new variants, enables structural optimization, and naturally produces a human-readable structural algorithm representation based on the Kronecker product formalism.
Aliaksei Sandryhaila, Amina Chebira, Markus Püschel and Jelena Kovacevic (Proc. SPIE Conf. on Wavelet Applications in Signal and Image Processing, Proceedings of SPIE, Vol. 7446, pp. 74460M-74460M-8, 2009)
A New Class of Seeded Real Lapped Tight Frame Transforms
Preprint (178 KB)
Bibtex
We propose a design procedure for the real, equal-norm, lapped tight frame transforms (LTFTs). These transforms have been recently proposed as both a redundant counterpart to lapped orthogonal transforms and an infinite-dimensional counterpart to harmonic tight frames.In addition, LTFTs can be efficiently implemented with filter banks. The procedure consists of two steps. First, we construct new lapped orthogonal transforms designed from submatrices of the DFT matrix. Then we specify the seeding procedure that yields real equal-norm LTFTs. Among them we identify the subclass of maximally robust to erasures LTFTs.
Markus Püschel and José M. F. Moura (IEEE Transactions on Signal Processing, Vol. 56, No. 8, pp. 3586-3599, 2008)
Algebraic Signal Processing Theory: 1-D Space
Preprint (272 KB)
Published paper (link to publisher)
Bibtex
In [3], we presented the algebraic signal processing theory, an axiomatic and general framework for linear signal processing. The basic concept in this theory is the signal model defined as the triple (A, M, Phi), where A is a chosen algebra of filters, M an associated A-module of signals, and Phi is a generalization of the z-transform. Each signal model has its own associated set of basic SP concepts including filtering, spectrum, and Fourier transform. Examples include infinite and finite discrete time where these notions take their well-known forms. In this paper, we use the algebraic theory to develop infinite and finite space signal models. These models are based on a symmetric space shift operator, which is distinct from the standard time shift. We present the space signal processing concepts of filtering or convolution, ``z-transform,'' spectrum, and Fourier transform. For finite length space signals, we obtain 16 variants of space models, which have the 16 discrete cosine and sine transforms (DCTs/DSTs) as Fourier transforms. Using this novel derivation, we provide missing signal processing concepts associated with the DCTs/DSTs, establish them as precise analogs to the DFT, get deep insight into their origin, and enable the easy derivation of many of their properties including their fast algorithms.
Markus Püschel and José M. F. Moura (IEEE Transactions on Signal Processing, Vol. 56, No. 4, pp. 1502-1521, 2008)
Algebraic Signal Processing Theory: Cooley-Tukey Type Algorithms for DCTs and DSTs
Preprint (347 KB)
Published paper (link to publisher)
Bibtex
This paper presents a systematic methodology to derive and classify fast algorithms for linear transforms. The approach is based on the algebraic signal processing theory. This means that the algorithms are not derived by manipulating the entries of transform matrices, but by a stepwise decomposition of the associated signal models, or polynomial algebras. This decomposition is based on two generic methods or algebraic principles that generalize the well-known Cooley-Tukey FFT and make the algorithms' derivations concise and transparent. Application to the 16 discrete cosine and sine transforms yields a large class of fast general radix algorithms, many of which have not been found before.
Markus Püschel and Martin Rötteler (Applicable Algebra in Engineering, Communication and Computing, special issue on "The memory of Thomas Beth", Vol. 19, No. 3, pp. 259-292, 2008)
Algebraic Signal Processing Theory: Cooley-Tukey Type Algorithms on the 2-D Spatial Hexagonal Lattice
Preprint (277 KB)
Bibtex
Recently, we introduced the framework for signal processing on a nonseparable 2-D hexagonal spatial lattice including the associated notion of Fourier transform called discrete triangle transform (DTT). Spatial means that the lattice is undirected in contrast to earlier work by Mersereau introducing hexagonal discrete Fourier transforms. In this paper we derive a general-radix algorithm for the DTT of an nxn 2-D signal, focusing on the radix-2x2 case. The runtime of the algorithm is O(n^2 log(n)), which is the same as for commonly used separable 2-D transforms. The DTT algorithm derivation is based on the algebraic signal processing theory. This means that instead of manipulating transform coefficients, the algorithm is derived through a stepwise decomposition of its underlying polynomial algebra based on a general theorem that we introduce. The theorem shows that the obtained DTT algorithm is the precise equivalent of the well-known Cooley-Tukey fast Fourier transform, which motivates the title of this paper.
Markus Püschel and José M. F. Moura (IEEE Transactions on Signal Processing, Vol. 56, No. 8, pp. 3572-3585, 2008)
Algebraic Signal Processing Theory: Foundation and 1-D Time
Preprint (274 KB)
Published paper (link to publisher)
Bibtex
This paper introduces a general and axiomatic approach to linear signal processing (SP) that we refer to as the algebraic signal processing theory (ASP). Basic to ASP is the linear signal model defined as a triple (A, M, Phi) where familiar concepts like the filter space and the signal space are cast as an algebra A and a module M, respectively. The mapping Phi generalizes the concept of z-transform to bijective linear mappings from a vector space of signal samples into the module~$\md$. Common concepts like filtering, spectrum, or Fourier transform have their equivalent counterparts in ASP. Once these concepts and their properties are defined and understood in the context of ASP, they remain true and apply to specific instantiations of the ASP signal model. For example, to develop signal processing theories for infinite and finite discrete time signals, for infinite or finite discrete space signals, or for multidimensional signals, we need only to instantiate the ASP signal model to a signal model that makes sense for that specific class of signals. Filtering, spectrum, Fourier transform, and other notions follow then from the corresponding ASP concepts. Similarly, common assumptions in SP translate into requirements on the ASP signal model. For example, shift-invariance is equivalent to A being commutative. For finite (duration) signals shift invariance then restricts A to polynomial algebras. We explain how to design signal models from the specification of a special filter, the shift. The paper illustrates the general ASP theory with the standard time shift, presenting a unique signal model for infinite time and several signal models for finite time. The latter models illustrate the role played by boundary conditions and recover the discrete Fourier transform~(DFT) and its variants as associated Fourier transforms. Finally, ASP provides a systematic methodology to derive fast algorithms for linear transforms. This topic and the application of ASP to space dependent signals and to multidimensional signals are pursued in companion papers.
Doru Balcan, Aliaksei Sandryhaila, Jonathan Gross and Markus Püschel (Proc. IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), pp. 3537-3540, 2008)
Alternatives to the Discrete Fourier Transform
Preprint (601 KB)
Published paper (link to publisher)
Bibtex
It is well-known that the discrete Fourier transform (DFT) of a finite length discrete-time signal samples the discrete-time Fourier transform of the same signal at equidistant points on the unit circle. Hence, as the signal length goes to infinity, the DFT approaches the DTFT. Associated with the DFT are circular convolution and a periodic signal extension. In this paper we identify a large class of alternatives to the DFT using the theory of polynomial algebras. Each of these Fourier transforms approaches the DTFT just as the DFT does, but has its own signal extension and notion of convolution. Further, these Fourier transforms have Vandermonde structure, which enables their fast computation. We provide a few experimental examples that confirm our theoretical results.
Markus Püschel (in Fast Fourier Transforms, Eds. C. Sidney Burrus, Connexions 2008)
DFT and FFT: An Algebraic View
Preprint (98 KB)
Published paper (link to publisher)
Bibtex
Aliaksei Sandryhaila, Jelena Kovacevic and Markus Püschel (Proc. IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), pp. 3505-3508, 2008)
Haar Filter Banks for 1-D Space Signals
Preprint (117 KB)
Published paper (link to publisher)
Bibtex
We recently introduced the framework for 1-D space signal processing, termed this way since it is built on a symmetric definition of the shift operation in contrast to the directed time shift operation. The framework includes the proper notion of signal and filter space, "z-transform," convolution, and Fourier transform, each of which is different from their time equivalents. In this paper, we extend this framework by deriving the proper notions of a Haar filter bank for space signal processing and show that it has a similar yet different form compared to the time case. Our derivation also sheds light on the nature of filter banks and makes a case for viewing them as projections on subspaces rather than as composition of filters.
Markus Püschel and Martin Rötteler (IEEE Transactions on Image Processing, Vol. 16, No. 6, pp. 1506-1521, 2007)
Algebraic Signal Processing Theory: 2-D Spatial Hexagonal Lattice
Preprint (359 KB)
Published paper (link to publisher)
Bibtex
We develop the framework for signal processing on a spatial, or undirected, 2-D hexagonal lattice for both an infinite and a finite array of signal samples. This framework includes the proper notions of z-transform, boundary conditions, filtering or convolution, spectrum, frequency response, and Fourier transform. In the finite case, the Fourier transform is called discrete triangle transform. Like the hexagonal lattice, this transform is nonseparable. The derivation of the framework makes it a natural extension of the algebraic signal processing theory that we recently introduced. Namely, we construct the proper signal models, given by polynomial algebras, bottom-up from a suitable definition of hexagonal space shifts using a procedure provided by the algebraic theory. These signal models, in turn, then provide all the basic signal processing concepts. The framework developed in this paper is related to Mersereau's early work on hexagonal lattices in the same way as the discrete cosine and sine transforms are related to the discrete Fourier transform-a fact that will be made rigorous in this paper.
Yevgen Voronenko and Markus Püschel (Proc. IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Vol. 3, pp. 876-879, 2006)
Algebraic Derivation of General Radix Cooley-Tukey Algorithms for the Real Discrete Fourier Transform
Preprint (84 KB)
Published paper (link to publisher)
Bibtex
We first show that the real version of the discrete Fourier transform (called RDFT) can be characterized in the framework of polynomial algebras just as the DFT and the discrete cosine and sine transforms. Then, we use this connection to algebraically derive a general radix Cooley-Tukey type algorithm for the RDFT. The algorithm has a similar structure as its complex counterpart, but there are also important differences, which are exhibited by our Kronecker product style presentation. In particular, the RDFT is decomposed into smaller RDFTs but also other auxiliary transforms, which we then decompose by their own Cooley-Tukey type algorithms to obtain a full recursive algorithm for the RDFT.
Markus Püschel and José M. F. Moura (http://arxiv.org/abs/cs.IT/0612077, 2006)
Algebraic Signal Processing Theory
Published paper (link to publisher)
Bibtex
This paper presents an algebraic theory of linear signal processing. At the core of algebraic signal processing is the concept of a linear signal model defined as a triple (A, M, phi), where familiar concepts like the filter space and the signal space are cast as an algebra A and a module M, respectively, and phi generalizes the concept of the z-transform to bijective linear mappings from a vector space of, e.g., signal samples, into the module M. A signal model provides the structure for a particular linear signal processing application, such as infinite and finite discrete time, or infinite or finite discrete space, or the various forms of multidimensional linear signal processing. As soon as a signal model is chosen, basic ingredients follow, including the associated notions of filtering, spectrum, and Fourier transform. The shift operator is a key concept in the algebraic theory: it is the generator of the algebra of filters A. Once the shift is chosen, a well-defined methodology leads to the associated signal model. Different shifts correspond to infinite and finite time models with associated infinite and finite z-transforms, and to infinite and finite space models with associated infinite and finite C-transforms (that we introduce). In particular, we show that the 16 discrete cosine and sine transforms are Fourier transforms for the finite space models. Other definitions of the shift naturally lead to new signal models and to new transforms as associated Fourier transforms in one and higher dimensions, separable and non-separable. We explain in algebraic terms shift-invariance (the algebra of filters A is commutative), the role of boundary conditions and signal extensions, the connections between linear transforms and linear finite Gauss-Markov fields, and several other concepts and connections.
Markus Püschel (Proc. IEEE Digital Signal Processing Workshop, pp. 386-391, 2006)
Algebraic Signal Processing Theory: An Overview
Preprint (110 KB)
Published paper (link to publisher)
Bibtex
We give an overview of the algebraic signal processing theory, a recently proposed generalization of linear signal processing (SP). Algebraic SP (ASP) is built axiomatically on top of the concept of a signal model, which is a triple (A, M, Phi), where A is a chosen algebra of filters, M an associated A-module of signals, and Phi generalizes the idea of a z-transform. ASP encompasses standard time SP (continuous and discrete, infinite and finite duration), but goes beyond it, for example, by defining meaningful notions of space SP in one and higher dimensions, separable and non-separable. ASP identifies many known transforms as Fourier transforms for a suitably chosen signal model and provides the means to derive and explain existing and novel transform algorithms. As one example, the discrete cosine transform is in ASP the Fourier transform for the finite space model and possesses general radix Cooley-Tukey type algorithms derived by the theory.
Jelena Kovacevic and Markus Püschel (Proc. IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Vol. 3, 2006)
Sampling Theorem Associated with the Discrete Cosine Transform
Preprint (154 KB)
Published paper (link to publisher)
Bibtex
One way of deriving the discrete Fourier transform (DFT) is by equispaced sampling of periodic signals or signals on a circle. In this paper, we show that an analogous derivation can be used to obtain the DCT (type 2). To achieve this goal, we replace the circle by a line graph with symmetric boundary conditions, and define signal space, filter space, and filtering operation appropriately. Further, we derive the corresponding sampling theorem including the proper notions of “bandlimited” and “sinc function.” The results show that, in a rigorous sense, the DCT is closely related to the DFT, and can be introduced without concepts from statistical signal processing as is the current practice.
Markus Püschel and José M. F. Moura (Proc. IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Vol. 5, 2006)
The Algebraic Structure in Signal Processing: Time and Space
Preprint (93 KB)
Published paper (link to publisher)
Bibtex
The assumptions underlying linear signal processing (SP) produce more structure than vector spaces. We capture this structure by describing the space of filters as an algebra and the space of signals as the associated module. We formulate an algebraic approach to SP that is axiomatically based on the concept of a signal model. Signal models for time are visualized as directed graphs. We construct corresponding models for undirected graphs, which we hence call space models, and show that, in particular, the 16 DCTs and DSTs are Fourier transforms for these finite space models. Finally, we discuss the extension of our theory to separable and nonseparable 2-D SP.
Markus Püschel and Martin Rötteler (Proc. IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Vol. 4, pp. 401-404, 2005)
Fourier Transform for the Directed Quincunx Lattice
Preprint (77 KB)
Published paper (link to publisher)
Bibtex
We introduce a new signal transform for computing the spectrum of a signal given on a two-dimensional directional quincunx lattice. The transform is non-separable, but closely related to a two-dimensional (separable) discrete Fourier transform. We derive the transform using recently discovered connections between signal transforms and polynomial algebras. These connections also yield several important properties of the new transform.
Markus Püschel and Martin Rötteler (Proc. IEEE International Conference on Image Processing (ICIP), Vol. 2, pp. 494-497, 2005)
Fourier Transform for the Spatial Quincunx Lattice
Preprint (87 KB)
Published paper (link to publisher)
Bibtex
We derive a new, two-dimensional nonseparable signal transform for computing the spectrum of spatial signals residing on a finite quincunx lattice. The derivation uses the connection between transforms and polynomial algebras, which has long been known for the discrete Fourier transform (DFT), and was extended to other transforms in recent research. We also show that the new transform can be computed with O(n log(n)) operations, which puts it in the same complexity class as its separable counterparts.
Markus Püschel and Jelena Kovacevic (Proc. Data Compression Conference (DCC), pp. 63-72, 2005)
Real, Tight Frames Maximally Robust To Erasures
Preprint (84 KB)
Published paper (link to publisher)
Bibtex
Motivated by the use of frames for robust transmission over the Internet, we present a first systematic construction of real tight frames with maximum robustness to erasures. We approach the problem in steps: we first construct maximally robust frames by using polynomial transforms. We then add tightness as an additional property with the help of orthogonal polynomials. Finally, we impose the last requirement of equal norm and construct, to our best knowledge, the first real, tight, equal-norm frames maximally robust to erasures.
Markus Püschel and Martin Rötteler (Proc. IEEE Digital Signal Processing Workshop, pp. 158-162, 2004)
Cooley-Tukey FFT Like Algorithm for the Discrete Triangle Transform
Published paper (link to publisher)
Bibtex
The discrete triangle transform (DTT) was recently introduced as an example of a non-separable transform for signal processing on a two-dimensional triangular grid. The DTT is built from Chebyshev polynomials in two variables in the same way as the DCT, type III, is built from Chebyshev polynomials in one variable. We show that, as a consequence, the DTT has, like the type III DCT, a Cooley-Tukey FFT type fast algorithm. We derive this algorithm and an upper bound for the number of complex operations it requires. Similar to most separable two-dimensional transforms, the operations count of this algorithm is O(n^2 log(n)) for an input of size n x n.
Sebastian Egner and Markus Püschel (Journal of Symbolic Computation, special issue on "Computer Algebra and Signal Processing", Vol. 37, No. 2, pp. 157-186, 2004)
Symmetry-Based Matrix Factorization
Preprint (330 KB)
Bibtex
We present a method to factor a given matrix M into a short product of sparse matrices, provided M has a suitable ``symmetry''. This sparse factorization represents a fast algorithm for the matrix-vector multiplication with M. The factorization method consists of two essential steps. First, a combinatorial search is used to compute a suitable symmetry of M in the form of a pair of group representations. Second, the group representations are decomposed stepwise, which yields factorized decomposition matrices and determines a sparse factorization of M. The focus of this article is the first step, finding the symmetries. All algorithms described have been implemented in the library AREP. We present examples for automatically generated sparse factorizations---and hence fast algorithms---for a class of matrices corresponding to digital signal processing transforms including the discrete Fourier, cosine, Hartley, and Haar transform.
Markus Püschel and Martin Rötteler (Proc. IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Vol. 3, pp. 45-48, 2004)
The Discrete Triangle Transform
Preprint (89 KB)
Published paper (link to publisher)
Bibtex
Markus Püschel (Proc. IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Vol. 2, pp. 501-504, 2003)
Cooley-Tukey FFT like Algorithms for the DCT
Preprint (71 KB)
Published paper (link to publisher)
Bibtex
The Cooley-Tukey FFT algorithm decomposes a discrete Fourier transform (DFT) of size n = km into smaller DFT of size k and m. In this paper we present a theorem that decomposes a polynomial transform into smaller polynomial transforms, and show that the FFT is obtained as a special case. Then we use this theorem to derive a new class of recursive algorithms for the discrete cosine transforms (DCT) of type II and type III. In contrast to other approaches, we manipulate polynomial algebras instead of transform matrix entries, which makes the derivation transparent, concise, and gives insight into the algorithms' structure. The derived algorithms have a regular structure and, for 2-power size, minimal arithmetic cost (among known DCT algorithms).
Markus Püschel and José M. F. Moura (SIAM Journal of Computing, Vol. 32, No. 5, pp. 1280-1316, 2003)
The Algebraic Approach to the Discrete Cosine and Sine Transforms and their Fast Algorithms
Preprint (327 KB)
Published paper (link to publisher)
Bibtex
It is known that the discrete Fourier transform (DFT) used in digital signal processing can be characterized in the framework of representation theory of algebras, namely as the decomposition matrix for the regular module C[Z_n] = C[x]/(x^n - 1). This characterization provides deep insight on the DFT and can be used to derive and understand the structure of its fast algorithms. In this paper we present an algebraic characterization of the important class of discrete cosine and sine transforms as decomposition matrices of certain regular modules associated to four series of Chebyshev polynomials. Then we derive most of their known algorithms by pure algebraic means. We identify the mathematical principle behind each algorithm and give insight into its structure. Our results show that the connection between algebra and digital signal processing is stronger than previously understood.
Markus Püschel, Sebastian Egner and Thomas Beth (in Computer Algebra Handbook, Foundations, Applications, Systems, Eds. J. Grabmeier, E. Kaltofen, V. Weispfenning, pp. 461-462, Springer 2002)
AREP
Published paper (link to publisher)
Bibtex
Markus Püschel (Journal of Symbolic Computation, Vol. 34, No. 6, pp. 561-596, 2002)
Decomposing Monomial Representations of Solvable Groups
Preprint (548 KB)
Bibtex
We present an efficient algorithm that decomposes a monomial representation of a solvable group G into its irreducible components. In contradistinction to other approaches, we also compute the decomposition matrix $A$ in the form of a product of highly structured, sparse matrices. This factorization provides a fast algorithm for the multiplication with A. In the special case of a regular representation, we hence obtain a fast Fourier transform for G. Our algorithm is based on a constructive representation theory that we develop. The term ``constructive'' signifies that concrete matrix representations are considered and manipulated, rather than equivalence classes of representations as it is done in approaches that are based on characters. Thus, we present well-known theorems in a constructively refined form and derive new results on decomposition matrices of representations. Our decomposition algorithm has been implemented in the GAP share package AREP. One application of the algorithm is the automatic generation of fast algorithms for discrete linear signal transforms.
Markus Püschel and José M. F. Moura (Proc. IEEE Digital Signal Processing Workshop, pp. 268-273, 2002)
The Discrete Trigonometric Transforms and Their Fast Algorithms: An Algebraic Symmetry Approach
Published paper (link to publisher)
Bibtex
It is well-known that the discrete Fourier transform (DFT) can be characterized as decomposition matrix for the polynomial algebra C[x]/(x^n - 1). This property gives deep insight into the DFT and can be used to explain and derive its fast algorithms. In this paper we present the polynomial algebras associated to the 16 discrete cosine and sine transforms. Then we derive important algorithms by manipulating algebras rather than matrix entries. This makes the derivation more transparent and explains their structure. Our results show that the relationship between signal processing and algebra is stronger than previously understood.
Sebastian Egner, Jeremy Johnson, David Padua, Markus Püschel and Jianxin Xiong (ACM SIGSAM Bulletin Communications in Computer Algebra, Vol. 35, No. 2, pp. 1-19, 2001)
Automatic Derivation and Implementation of Signal Processing Algorithms
Preprint (249 KB)
Bibtex
Sebastian Egner and Markus Püschel (IEEE Transactions on Signal Processing, Vol. 49, No. 9, pp. 1992-2002, 2001)
Automatic Generation of Fast Discrete Signal Transforms
Preprint (300 KB)
Published paper (link to publisher)
Bibtex
This paper presents an algorithm that derives fast versions for a broad class of discrete signal transforms symbolically. The class includes but is not limited to the discrete Fourier and the discrete trigonometric transforms. This is achieved by finding fast sparse matrix factorizations for the matrix representations of these transforms. Unlike previous methods, the algorithm is entirely automatic and uses the defining matrix as its sole input. The sparse matrix factorization algorithm consists of two steps: first, the ``symmetry'' of the matrix is computed in the form of a pair of group representations; second, the representations are stepwise decomposed, giving rise to a sparse factorization of the original transform matrix. We have successfully demonstrated the method by computing automatically efficient transforms in several important cases: for the DFT, we obtain the Cooley/Tukey FFT; for a class of transforms including the DCT, type II, the number of arithmetic operations for our fast transforms is the same as for the best known algorithms. Our approach provides new insights and interpretations for the structure of the considered signal transforms and why fast algorithms do exist. The sparse matrix factorization algorithm is implemented within the software package AREP.
Markus Püschel (PhD. thesis, Computer Science, University of Karlsruhe, 1999, Technical Report Drexel-MCS-1999-1 (Translation of 4))
Constructive Representation Theory and Fast Discrete Signal Transforms
Published paper (link to publisher)
Bibtex
Sebastian Egner and Markus Püschel (GAP share package and manual, 1998)
AREP - A Package for Constructive Representation Theory and Fast Signal Transforms
Published paper (link to publisher)
Bibtex
José M. F. Moura and Marcelo Bruno (IEEE Transactions on Signal Processing, Vol. 46, No. 9, pp. 2571-2574, 1998)
DCT/DST and Gauss-Markov Fields: Conditions for Equivalence
Published paper (link to publisher)
Bibtex
The correspondence addresses the intriguing question of which random models are equivalent to the discrete cosine transform (DCT) and discrete sine transform (DST). Common knowledge states that these transforms are asymptotically equivalent to first-order Gauss causal Markov random processes. We establish that the DCT and the DST are exactly equivalent to homogeneous one-dimensional (1-D) and two-dimensional (2-D) Gauss noncausal Markov random fields defined on finite lattices with appropriate boundary conditions
Markus Püschel (PhD. thesis, Computer Science, University of Karlsruhe, 1998, (Translated in 2))
Konstruktive Darstellungstheorie und Algorithmengenerierung
Published paper (link to publisher)
Bibtex
Sebastian Egner (PhD. thesis, Computer Science, University of Karlsruhe, 1997)
Zerlegungstheorie linearer Transformationen mit Symmetrie
Published paper (link to publisher)
Bibtex