Signal Processing - November 2016 - 135

lecture notes
James Folberth and Stephen Becker

Efficient Adjoint Computation for Wavelet
and Convolution Operators

irst-order optimization algorithms,
often preferred for large problems,
require the gradient of the differentiable terms in the objective function.
These gradients often involve linear
operators and their adjoints, which must
be applied rapidly. We consider two
example problems and derive methods
for quickly evaluating the required
adjoint operator. The first example is an
image deblurring problem where we
must compute efficiently the adjoint
of multistage wavelet reconstruction.
Our formulation of the adjoint works
for a variety of boundary conditions,
which allows the formulation to generalize to a larger class of problems.
The second example is a blind channel estimation problem taken from the
optimization literature where we must
compute the adjoint of the convolution of two signals. In each example,
we show how the adjoint operator can
be applied efficiently while leveraging
existing software.

Prerequisites
The reader should be familiar with linear algebra, wavelets, and basic Fourier
analysis. Knowledge of first-order iterative optimization algorithms is beneficial for motivating the need for a fast
adjoint computation but should not be
necessary to understand the adjoint
computation itself.

Motivation
Many estimation problems are modeled
using the composition of a differentiable loss , with an affine map
x 7 Ax + b , the simplest such examples being generalized linear models
such as least-square data fitting. The
gradient of , % A is given by the chain
rule as A ) d, (Ax + b) . For small problems, A may be explicitly represented
as a matrix and A ) calculated as the
conjugate transpose of the matrix.
In contrast, larger problems are
often carefully formulated to involve
only linear operators A , which have a
fast transform [e.g., fast Fourier transform (FFT), wavelet transform, convolution] and are therefore never
explicitly stored as matrices. While
many software packages provide fast
routines to compute A -1 or the pseudoinverse A @, few packages include
routines for A ).
The purpose of this lecture note is to
describe a few cases where one can
compute the action of A ) with the same
complexity as applying A. Boundary
conditions play a confounding role in
the calculation, and we present a simple framework to correctly take them
into account.

Example 1: An image
deblurring problem

Digital Object Identifier 10.1109/MSP.2016.2594277
Date of publication: 4 November 2016

Digital images can be blurred through a
variety of means. For example, the
optical system can be out of focus and/
or atmospheric turbulence can cause

IEEE Signal Processing Magazine

November 2016

blurring of astronomical images. The
goal of image deblurring is to recover
the original, sharp image. One class of
techniques poses the deblurring problem as an optimization problem, where
the optimization variables are the
wavelet coefficients of the recovered
image. We assume that the blurring
operator R is known. For instance, R
could represent a Gaussian point
spread function (PSF) under symmetric
(reflexive) boundary conditions. The
blurring operator is usually singular or
ill conditioned [1].
Let W represent a multilevel wavelet
reconstruction operator with suitable
boundary conditions, b be the observed,
blurry image, and A = RW be the linear operator that synthesizes an image
from wavelet coefficients x and then
blurs the synthesized image under the
blurring operator R. To both regularize the problem and take into account
that many real-world images have a
sparse wavelet representation, we
solve the following standard model,
which seeks to recover sparse wavelet
coefficients that accurately reconstruct
the blurred image:
1 < RWx - b < 2 + m < x < , m 2 0.
min
1
2
x
2
(1)
This commonly used formulation [2] is
sometimes called the synthesis formulation since we reconstruct an image Wx
from the wavelet coefficients in the optimization variable x. We seek to find an
135

Table of Contents for the Digital Edition of Signal Processing - November 2016