Multiresolution fast algorithms for one-dimensional inverse scattering and linear least-squares estimation.

Abstract

The Krein integral equation of one-dimensional (1-D) inverse scattering and the Wiener-Hopf integral equation of linear least-squares estimation are Fredholm equations with a symmetric Toeplitz kernel. They are transformed using a wavelet-based Galerkin method, into a symmetric block slanted Toeplitz (BST) system of equations. This solution method is compared with direct discretization using numerical examples. A Levinson-like fast algorithm is developed for solving the symmetric BST system of equations. This algorithm can be used even if the kernel of the integral equation is not a Calderon-Zygmund operator (in which case the wavelet transform may not sparsify it). Our algorithms exploit the symmetric block slanted Toeplitz structure of the system matrix, and do not rely on sparsity. We also present a wavelet-based Schur-like layer stripping fast algorithm which yields a multiresolution solution to the lattice equations of the 1-D inverse scattering problem without discretization and without having to solve any systems of equations. Furthermore, the Schur-like algorithm can be run in parallel with the Levinson-like algorithm to compute the reflection coefficients of the Levinson-like algorithm, thereby speeding up the operation of the Levinson-like algorithm. The Levinson-like and Schur-like algorithms are shown to yield fast factorizations of the symmetric BST system matrix and its inverse. The Levinson-like algorithm is also used to develop a Gohberg-Semencul-like formula and tests for positive definiteness of the symmetric BST matrix. Symmetric forms of the Levinson-like and Schur-like algorithms are also given. From these, we develop the split Levinson-like and split Schur-like fast algorithms. Finally, we present two algorithms for incorporating a priori information about the reflectivity function into the 1-D inverse scattering solution procedure. The first of these is based on the classical Levinson and Schur algorithms and yields a discrete solution while the second is based on the Levinson-like and Schur-like algorithms and hence yields a wavelet-based solution.