Solving the third problem posed in the introduction to these notes is rather
different from the other two. Here we want to find an operator or matrix that
when multiplied by xx gives
bb . Clearly a solution to this problem would not
be unique as stated. In order to pose a better defined problem, we generally
give a set or family of inputs xx and the
corresponding outputs bb . If these families are
independent, and if the number of them is the same as the size of the matrix,
a unique matrix is defined and can be found by solving simultaneous equations.
If a smaller number is given, the remaining degrees of freedom can be used to
satisfy some other criterion. If a larger number is given, there is probably
no exact solution and some approximation will be necessary.
Alternatively, the matrix may be constrained by structure to have less than
N
2
N
2
degrees of freedom. It may be a cyclic convolution, a non cyclic convolution,
a Toeplitz, a Hankel, or a Toeplitz plus Hankel matrix.
This problem came up in research on designing efficient prime length fast
Fourier transform (FFT) algorithms where xx is the
data and bb is the FFT of
xx . The problem was to derive an operator that
would make this calculation using the least amount of arithmetic. We solved it
using a special formulation
[1] and Matlab.
