| Many one- and two-dimensional Fredholm integral equations of the first kind give rise to ill-posed problems. Approximate solutions to such equations are often formed by applying a regularization technique to the discretized version of the system. The exact solution to the discrete ill-posed problem is often hopelessly contaminated by noise, since the discretized problem is 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 preconditioned Krylov-subspace type algorithms to compute such regularized solutions. In particular, we address the regularization properties of the Krylov subspace methods MINRES and CGLS; we show that the regularization properties of these algorithms can be characterized in terms of convergence properties of the residual. In many applications, such as image and signal processing, the corresponding least squares problem or linear system involves a matrix with a Toeplitz-type structure. For instance, Toeplitz matrices--matrices which are constant along their diagonals--can arise from the discretization of 1-D integral equations with spatially invariant kernels, while matrices which are block Toeplitz with Toeplitz blocks can arise from 2-D integral equations. An orthogonal change of coordinates transforms the matrix with Toeplitz-type structure to a Cauchy-like matrix, and we choose our preconditioners to be particular low rank (block) Cauchy-like matrices augmented by an identity. We show that if the kernel of the underlying integral equation satisfies certain criteria, 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 lower subspace, remain small, and the upper and lower spaces are relatively unmixed. Fast algorithms for applying the preconditioner are given and the effectiveness of the preconditioners for filtering noise is demonstrated on several examples. |
