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.

If the unknown operator matrix is of dimension MM by NN, then we take NN inputs xkxk for k=1,2,⋯,Nk=1,2,⋯,N, each of dimension NN and the corresponding NN outputs bkbk, each of dimension MM and form the matrix equation:

where AA is the MM by NN unknown operator, XX is the NN by NN input matrix with NN columns which are the inputs xkxk and BB is the MM by NN output matrix with columns bkbk. The operator matrix is then determined by:

if the inputs are independent which means XX is nonsingular.

This problem can be posed so that there are more (perhaps many more) inputs and outputs than NN with a resulting equation error which can be minimized with some form of pseudoinverse.

Linear regression can be put in this form. If our matrix equation is

where AA is a row vector of unknown weights and xx is a column vector of known inputs, then bb is a scaler inter product. If a seond experiment gives a second scaler inner product from a second column vector of known inputs, then we augment XX to have two rows and bb to be a length-2 row vector. This is continued for NN experiment to give Equation 3 as a 1 by NN row vector times an MM by NN matrix which equals a 1 by MM row vector. It this equation is transposed, it is in the form of Equation 3 which can be approximately solved by the pesuedo inverse to give the unknown weights for the regression.

Alternatively, the matrix may be constrained by structure to have less than N2N2 degrees of freedom. It may be a cyclic convolution, a non cyclic convolution, a Toeplitz, a Hankel, or a Toeplitz plus Hankel matrix.

A problem of this sort 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.