Fast transforms

In image or signal processing, linear transforms are commonplace, e.g. in data compaction; their processing time may be a sensitive parameter. To transform an N-vector f according to g = A f (with A a square matrix) into a vector g, requires O(N²) operations; for large N clearly a problem (imagine the File:Hepa img328.gif pixels of an image, redefined every 25msec!). Fortunately, for most unitary transforms (and for N an integral power of 2), fast algorithms exist. They are essentially based on the fact that one can partition the task into some intermediate steps, and subsequently reuse the intermediate results in further iterations.

The Cooley-Tukey algorithm for the discrete Fourier transform is an example. It is based on a factorization algorithm by Good:

where the A_i are very sparse matrices. This reduces the number of operations to File:Hepa img330.gif .

We illustrate this by the 8-point Walsh transform ( Orthogonal Functions), which uses the same algorithm with different coefficients:

with g = W₈ f where f and g are 8-vectors. If this transformation were to be carried out in a straightforward way, 64 additions or subtractions would be necessary. Good's sparse matrix factorization for this case reads W₈ = A₁ A₂ A₃, with the definitions

In the first step, only sums and differences of neighbouring pixels are formed. They are then used in the second step to produce expressions of four pixels, etc. Only three steps are necessary to obtain the entire transform:

The following signal flowchart shows the three steps; solid and dashed lines indicate additions and subtractions, respectively:

A similar gain can be obtained on the Haar transform, whose transformation matrix (for an 8-vector) is given by:

Blind execution needs 64(N²) additions or subtractions (plus a small number of multiplications by 2 or ). Suppressing all zero values, this is reduced to File:Hepa img340.gif . The corresponding signal flowchart shows that only 14, or more generally, File:Hepa img341.gif additions or subtractions are necessary for its computation (remember that N is a power of 2). This is by far the fastest of all unitary transforms.

No efficient algorithm has been found for the optimal Karhunen-Loeve transform, which is signal-dependent. For all other unitary transforms fast algorithms exist. They reduce the task from O(N²) operations to about File:Hepa img343.gif ) operations, except for the very sparse Haar transform, for which O(N) operations suffice.

For the Fourier transform, these operations are complex, for all the others real. Because the non-sinusoidal Walsh and Haar transform matrices consist only of +1, -1 and zero, or simple multiples thereof, only additions or subtractions have to be executed. Comparing complex multiplication with real addition, and considering the necessary high precision for the Fourier kernels File:Hepa img344.gif , the difference in processing time between Fourier and Walsh or Haar transforms is evidently substantial.

For e.g. Beauchamp87, Kunt80more details and references , Pratt78, or Ahmed75.