Basic operators and adjoints

Transient convolution

The next operator we examine is convolution. It arises in many applications; and it could be derived in many ways. A basic derivation is from the multiplication of two polynomials, say $X(Z) = x_1 + x_2 Z + x_3 Z^2 + x_4 Z^3 + x_5 Z^4 + x_6 Z^5$ times $B(Z) = b_1 + b_2 Z + b_3 Z^2 + b_4 Z^3$.Identifying the $k$-th power of $Z$ in the product $Y(Z)=B(Z)X(Z)$ gives the $k$-th row of the convolution transformation (4).

$$\bold y \eq \left[ \begin{array}{c} y_1 \\ y_2 \\ y_3 ... ...x_4 \\ x_5 \\ x_6 \end{array} \right] \eq \bold B \bold x$$ (4)

Notice that columns of equation (4) all contain the same ``wavelet'' but with different shifts. This signal is called the filter's impulse response.

Equation (4) could be rewritten as

$$\bold y \eq \left[ \begin{array}{c} y_1 \\ y_2 \\ y_3 ... ...b_1 \\ b_2 \\ b_3 \end{array} \right] \eq \bold X \bold b$$ (5)

In applications, we can choose between $\bold y = \bold X \bold b$ and $\bold y=\bold B\bold x$. In one case, the output $\bold y$ is dual to the filter $\bold b$; and in the other case, the output $\bold y$ is dual to the input $\bold x$. Sometimes, we must solve for $\bold b$ and sometimes for $\bold x$; therefore sometimes we use equation (5) and sometimes (4). Such solutions begin from the adjoints. The adjoint of equation (4) is

$$\left[ \begin{array}{c} \hat x_1 \\ \hat x_2 \\ \hat x_3 ... ... y_4 \\ y_5 \\ y_6 \\ y_7 \\ y_8 \end{array} \right]$$ (6)

The adjoint crosscorrelates with the filter instead of convolving with it (because the filter is backward). Notice that each row in equation (6) contains all the filter coefficients, and there are no rows where the filter somehow uses zero values off the ends of the data as we saw earlier. In some applications, it is important not to assume zero values beyond the interval where inputs are given.

The adjoint of (5) crosscorrelates a fixed portion of filter input across a variable portion of filter output.

$$\left[ \begin{array}{c} \hat b_1 \\ \hat b_2 \\ \hat b_3 ... ... y_4 \\ y_5 \\ y_6 \\ y_7 \\ y_8 \end{array} \right]$$ (7)

Module tcai1 is used for $\bold y=\bold B\bold x$, and module tcaf1 is used for $\bold y = \bold X \bold b$.

user/gee/tcai1.c

    for( b=0; b < nb; b++) {
	for( x=0; x < nx; x++) { y = x + b;
	    if( adj) xx[x] += yy[y] * bb[b];
	    else     yy[y] += xx[x] * bb[b];
	}
    }

user/gee/tcaf1.c

    for (b=0; b < nb; b++) {
	for (x=0; x < nx; x++) { y = x + b;
	    if( adj) bb[b] += yy[y] * xx[x];
	    else     yy[y] += bb[b] * xx[x];
        }
    }

The polynomials $X(Z)$, $B(Z)$, and $Y(Z)$ are called $Z$ transforms. An important fact in real life (but not important here) is that the $Z$ transforms are Fourier transforms in disguise. Each polynomial is a sum of terms, and the sum amounts to a Fourier sum when we take $Z=e^{i\omega\Delta t}$. The very expression $Y(Z)=B(Z)X(Z)$ says that a product in the frequency domain ($Z$ has a numerical value) is a convolution in the time domain. Matrices and programs nearby are doing convolutions of coefficients.

Basic operators and adjoints