e convolution filter, the
matrix vector multiply is actually O(N) or O(n2) instead of
O(N2). Therefore, the total running time for a
nbyn image is O(n4) which is markedly better
than the brute force matrix inversion algorithm.Intermediate Values
The key advantage CG has to pure matrix inversion is storage. In each
iteration, one only needs to store a few vectors, and the iteration
only needs those vectors for that iteration or the one immediately
afterwards. Hence, we can store the intermediate data in
O(n2) space, much better than the O(n4) needed
for pure matrix inversion.
The nice thing about iterative methods is that they can be interrupted
halfway and still compute a good approximate. The image above was
not run for 254×190=48260 iterations. Rather, it was
interrupted at roughly 400 iterations after the residual (a measure of
how close the filtered guess is to the filtered original image) and
still showed excellent results.
Currently, the CG algorithm is feasible and applies to a good subset
of the original problem statement. It can generate much better
results than a simple sharpen filter for deblurring. Its storage
requirement scales very well, and its running time is shorter than a
brute force matrix inversion.
There are some situations in which this algorithm would be useful.
Suppose that we have some sort of digital imaging device that has a
known and measured lens/sensor error. For example, a pixel sensor may
accidentally pick up a fraction of signals from neighboring pixels.
If this error data is put into the form of a convolution filter, we
can theoretically correct all images that have this error.
Below are comparison images (zoomed in) for a 64×64 black and
white text image.