Pivoted Cauchy-like preconditioners for regularized solution of ill-posed problems

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 problem is quite ill conditioned, and noise component s in the approximate null-space dominate the solution vector. Therefore we seek an approximate solution that does not have large components in these d irections. We use a preconditioned conjugate gradient algorithm to compute such a regularized solution. A unitary 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 Cu's fast m odified 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 aro und one, the smallest singular values, corresponding to the lower subspace, remain small, and the upper and lower spaces are relatively unmixed. The p reconditioned algorithm costs only O (n lg n) operations per iteration for a problem with n variables. The effectiveness of the preconditioner for fil tering noise is demonstrated on three examples.