CAUCHY-LIKE PRECONDITIONERS FOR 2-DIMENSIONAL ILL-POSED PROBLEMS

Loading...
Thumbnail Image

Files

CS-TR-3776.ps (979.82 KB)
No. of downloads: 267
CS-TR-3776.pdf (702.71 KB)
No. of downloads: 649

Publication or External Link

Date

1998-10-15

Advisor

Citation

DRUM DOI

Abstract

Ill-conditioned matrices with block Toeplitz, Toeplitz block (BTTB) structure arise from the discretization of certain ill-posed problems in signal and image processing. We use a preconditioned conjugate gradient algorithm to compute a regularized solution to this linear system given noisy data. Our preconditioner is a Cauchy-like block diagonal approximation to an orthogonal transformation of the BTTB matrix. We show the preconditioner has desirable properties when the kernel of the ill-posed problem is smooth: the largest singular values of the preconditioned matrix are clustered around one, the smallest singular values remain small, and the subspaces corresponding to the largest and smallest singular values, respectively, remain unmixed. For a system involving $np$ variables, the preconditioned algorithm costs only $O(np (\lg n + \lg p))$ operations per iteration. We demonstrate the effectiveness of the preconditioner on three examples.

Notes

Rights