Numerical Aspects of Deconvolution
# Numerical Aspects of Deconvolution

The above figure shows that "naive" deconvolution of a noisy
signal can lead to a completely useless deconvolved signal
dominated by erroneous high-frequency components.
Care must be taken to avoid this situation.

The figure - and the example - is from the paper:

- P.C. Hansen,
*Deconvolution and Regularization with Toeplitz
Matrices*, Numerical Algorithms, 29 (2002), pp. 323-378.

The paper describes the inherent difficulties in deconvolution of noisy data,
and their efficient numerical treatment. The emphasis is on the numerical
aspects, and the theory is illustrated with examples.

Discretizations of deconvolution problems lead to Toeplitz matrices,
which are matrices with a very special structure.
One of the topics covered in the lecture note is the efficient
multiplication of an n-times-n Toeplitz matrix with a vector
in O(n log_{2}n) operations by means of the FFT algorithm.
The above figure shows various flop counts for matrix-vector
multiplications with full and banded Toeplitz matrices.