Adjoint operators

FAMILIAR OPERATORS

The operation $y_i = \sum_j b_{ij} x_j$ is the multiplication of a matrix $\bold B$ by a vector $\bold x$. The adjoint operation is $\tilde x_j = \sum_i b_{ij} y_i$. The operation adjoint to multiplication by a matrix is multiplication by the transposed matrix (unless the matrix has complex elements, in which case we need the complex-conjugated transpose). The following pseudocode does matrix multiplication $\bold y=\bold B\bold x$ and multiplication by the transpose $\tilde \bold x = \bold B' \bold y$:

		if operator itself 


then erase y 


if adjoint 


then erase x 


do iy = 1, ny { 


do ix = 1, nx { 


if operator itself 


y(iy) = y(iy) + b(iy,ix) $\times$ x(ix) 


if adjoint 


x(ix) = x(ix) + b(iy,ix) $\times$ y(iy) 

}}

Notice that the ``bottom line'' in the program is that $x$ and $y$ are simply interchanged. The above example is a prototype of many to follow, so observe carefully the similarities and differences between the operation and its adjoint.

A formal subroutine for matrix multiply and its adjoint is found below. The first step is a subroutine, adjnull(), for optionally erasing the output. With the option add=true, results accumulate like y=y+B*x.

api/c/adjnull.c

void sf_adjnull (bool adj /* adjoint flag */, 
		 bool add /* addition flag */, 
		 int nx   /* size of x */, 
		 int ny   /* size of y */, 
		 float* x, 
		 float* y) 
/*< Zeros out the output (unless add is true). 
  Useful first step for any linear operator. >*/
{
    int i;
    
    if(add) return;
    
    if(adj) {
	for (i = 0; i < nx; i++) {
	    x[i] = 0.;
	}
    } else {
	for (i = 0; i < ny; i++) {
	    y[i] = 0.;
	}
    }
}

The subroutine matmult() for matrix multiply and its adjoint exhibits the style that we will use repeatedly. user/fomels/matmult.c

void matmult_lop (bool adj, bool add, 
		  int nx, int ny, float* x, float*y) 
/*< linear operator >*/
{
    int ix, iy;
    sf_adjnull (adj, add, nx, ny, x, y);
    for (ix = 0; ix < nx; ix++) {
	for (iy = 0; iy < ny; iy++) {
	    if (adj) x[ix] += B[iy][ix] * y[iy];
	    else     y[iy] += B[iy][ix] * x[ix];
	}
    }
}

Sometimes a matrix operator reduces to a simple row or a column.

A row      is a summation operation.

A column is an impulse response.

If the inner loop of a matrix multiply ranges within a

row,      the operator is called sum or pull.

column, the operator is called spray or push.

A basic aspect of adjointness is that the adjoint of a row matrix operator is a column matrix operator. For example, the row operator $[a,b]$

$$y \eq \left[ a b \right] \left[ \begin{array}{l} x_1 \\ x_2 \end{array}\right] \eq a x_1 + b x_2$$ (1)

has an adjoint that is two assignments:

$$\left[ \begin{array}{l} \hat x_1 \\ \hat x_2 \end{arra... ... \left[ \begin{array}{l} a \\ b \end{array} \right] y$$ (2)

The adjoint of a sum of $N$ terms is a collection of $N$ assignments.

Adjoint operators