0.4 Constructing the operator (design)

Constructing the operator (unfinished)

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 ormatrix that when multiplied by $\mathbf{x}$ gives $\mathbf{b}$ . Clearly a solution to this problem would not be unique as stated. In order to pose a better definedproblem, we generally give a set or family of inputs $\mathbf{x}$ and the corresponding outputs $\mathbf{b}$ . If these families are independent, and if the number of them is the same as the size of the matrix, a unique matrix isdefined and can be found by solving simultaneous equations. If a smaller number is given, the remaining degrees of freedom can be used to satisfysome 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 $M$ by $N$ , then we take $N$ inputs ${\mathbf{x}}_{\mathbf{k}}$ for $k=1,2,\cdots ,N$ , each of dimension $N$ and the corresponding $N$ outputs ${\mathbf{b}}_{\mathbf{k}}$ , each of dimension $M$ and form the matrix equation:

where $\mathbf{A}$ is the $M$ by $N$ unknown operator, $\mathbf{X}$ is the $N$ by $N$ input matrix with $N$ columns which are the inputs ${\mathbf{x}}_{\mathbf{k}}$ and $\mathbf{B}$ is the $M$ by $N$ output matrix with columns ${\mathbf{b}}_{\mathbf{k}}$ . The operator matrix is then determined by:

if the inputs are independent which means $\mathbf{X}$ is nonsingular.

This problem can be posed so that there are more (perhaps many more) inputs and outputs than $N$ 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 $\mathbf{A}$ is a row vector of unknown weights and $\mathbf{x}$ is a column vector of known inputs, then $\mathbf{b}$ is a scaler inter product. If a seond experiment gives a second scaler inner product from a secondcolumn vector of known inputs, then we augment $\mathbf{X}$ to have two rows and $\mathbf{b}$ to be a length-2 row vector. This is continued for $N$ experiment to give [link] as a 1 by $N$ row vector times an $M$ by $N$ matrix which equals a 1 by $M$ row vector. It this equation is transposed, it is in the formof [link] 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 $N^2$ degrees of freedom. It may be a cyclic convolution, a non cyclic convolution, a Toeplitz, a Hankel, or a Toeplitz plus Hankelmatrix.

A problem of this sort came up in research on designing efficient prime length fast Fourier transform (FFT) algorithms where $\mathbf{x}$ is the data and $\mathbf{b}$ is the FFT of $\mathbf{x}$ . The problem was to derive an operator that would make this calculation using the least amount of arithmetic. We solved it using aspecial formulation [link] and Matlab.