2
$\begingroup$

The DFT has the FFT, Hadamard transform has the Fast Hadamard Transform and so do a number of other unitary transforms (operators). Is there or has there been an attempt at creating FFT style algorithms for generalized unitary transforms?

$\endgroup$
5
$\begingroup$

It's all about structure. One early paper on this is A Unified Treatment of Discrete Fast Unitary Transforms, 1977:

A set of recursive rules which generate unitary transforms with a fast algorithm (FUT) are presented. For each rule, simple relations give the number of elementary operations required by the fast algorithm. The common Fourier, Walsh-Hadamard (W-H), Haar, and Slant transforms are expressed with these rules. The framework developed allows the introduction of generalized transforms which include all common.transforms in a large class of "identical computation transforms". A systematic and unified view is provided for unitary transforms which have appeared in the literature. This approach leads to a number of new transforms of potential interest. Generalization to complex and multidimensional unitary transforms is considered and some structural relations between transforms are established.

Among the most common, the discrete sine (DST), cosine (DCT), Hartley, wavelet transforms and many others (Walsh, Hadamard, Paley or Waleymard, triangle, jacket, slant, Hermite) have fast counterparts.

One global initiative towards a systematic construction was termed Algebraic Signal Processing Theory. Let me mention two papers laying some foundation using basic algebraic structures:

Algebraic Signal Processing Theory: Foundation and 1-D Time, 2008

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 ($\mathcal{A}$, $\mathcal{M}$, $\Phi$) where familiar concepts like the filter space and the signal space are cast as an algebra $\mathcal{A}$ and a module $\mathcal{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 $\mathcal{M}$. 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 $\mathcal{A}$ being commutative. For finite (duration) signals shift invariance then restricts $\mathcal{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.

Algebraic Signal Processing Theory: Cooley-Tukey Type Algorithms for DCTs and DSTs, 2008

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.

Aside, when those transforms are considered in the filter bank framework, other fast versions exist, based on polyphase decomposition or lifting transforms.

Additional references: I do not know of a full book on Algebraic Signal Processing Theory. The above link has a handful of references. For book-style, you have PhD theses:

On filter banks:

$\endgroup$
  • 1
    $\begingroup$ Wow. This is absolutely fantastic! This is exactly what I was searching for, but Google wasn't getting me anywhere. Is there any book on the subject that you would recommend? $\endgroup$ – Television Jun 11 '17 at 3:13
  • $\begingroup$ I have added a few references. Not sure there is a whole book devoted to the topic. $\endgroup$ – Laurent Duval Jun 11 '17 at 7:53
2
$\begingroup$

At the heart of the FFT is the divide and conquer (here) technique of solving a big problem interms of solutions of the smaller ones.

Therefore any transform, for which you can succesfully devise a divide and conquer approach, will benefit from the same efficiency improvement as the FFT benefits for computing the DFT.

The key point is in stating an efficient mechanism of proper integration of the small pieces into the larger one.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.