## Pivoted Cauchy-like Preconditioners for Regularized Solution of Ill-Posed Problems

##### Abstract

Many ill-posed problems are solved using a discretization that
results in a least squares problem or a linear system involving a
Toeplitz matrix. The exact solution to such problems
is often hopelessly contaminated by noise, since the discretized problemis quite ill-conditioned, and noise components in the approximate
null-space dominate the solution vector.
Therefore we seek an approximate solution that does not
have large components in these directions.
We use a preconditioned conjugate gradient algorithm to compute
such a regularized solution. An orthogonal change
of coordinates transforms the Toeplitz matrix to
a Cauchy-like matrix, and we choose our preconditioner
to be a low rank Cauchy-like matrix determined in the course
of Gu's fast modified complete pivoting algorithm.
We show that if the kernel of the ill-posed problem is smooth, then
this preconditioner has desirable properties:
the largest singular values of the preconditioned
matrix are clustered around one,
the smallest singular values, corresponding to the noise subspace,
remain small, and the signal and noise spaces are relatively
unmixed.
The preconditioned algorithm costs only $O(n \lg n)$
operations per iteration for a problem with $n$ variables.
The effectiveness of the preconditioner for filtering
noise is demonstrated on three examples.
(Also cross-referenced as UMIACS-TR-96-63)

University of Maryland, College Park, MD 20742-7011 (301)314-1328.

Please send us your comments.