6.3: The Bilinear Structure

The bilinear form introduced in earlier and the related linear form in are very powerful descriptions of both the DFT and convolution.

$Bilinear:\; \; Y=C\left [ AXoBH\right ]$

$Linear:\; \; Y=CDAX$

Since the equation is a bilinear operation defined in terms of a second bilinear operator $$o$$, this formulation can be nested. For example if $$o$$ is itself defined in terms of a second bilinear operator $$@$$, , by

$XoH=C'\left [ A'X@B'H \right ]$

The equation then becomes

$Y=CC'\left [ A'AX@B'BH \right ]$

For convolution, if $$A$$, represents the polynomial residue reduction modulo the cyclotomic polynomials, then $$A$$, is square (e.g. the equation and $$o$$, represents multiplication of the residue polynomials modulo the cyclotomic polynomials. If $$A$$, represents the reduction modulo the cyclotomic polynomials plus the Toom-Cook reduction as was the case in the example of the equation, then $$A$$, is $$N\times M$$ and $$o$$, is term-by- term simple scalar multiplication. In this case $$AX$$, can be thought of as a transform of $$X$$ and $$C$$ is the inverse transform. This is called a rectangular transform because $$A$$ is rectangular. The transform requires only additions and convolution is done with $$M$$ multiplications. The other extreme is when $$A$$ represents reduction over the $$N$$ complex roots of $$s^N-1$$. In this case $$A$$ is the DFT itself, as in the example of ($$43$$), and $$o$$ is point by point complex multiplication and $$C$$ is the inverse DFT. A trivial case is where $$A$$, $$B$$ and $$C$$ are identity operators and $$o$$ is the cyclic convolution.

This very general and flexible bilinear formulation coupled with the idea of nesting in  the equation gives a description of most forms of convolution.

Contributor

• ContribEEBurrus