6.3: The Bilinear Structure

Last updated
Save as PDF

Page ID: 1995

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

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 ] \nonumber \]

\[Linear:\; \; Y=CDAX \nonumber \]

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 ] \nonumber \]

The equation then becomes

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

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