Levinson-like and Schur-like fast algorithms for solving block-slanted Toeplitz systems of equations arising in wavelet-based solution of integral equations

The Wiener-Hopf integral equation of linear least-squares estimation of a wide-sense stationary random process and the Krein integral equation of one-dimensional (1-D) inverse scattering are Fredholm equations with symmetric Toeplitz kernels. They are transformed using a wavelet-based Galerkin method into a symmetric “block-slanted Toeplitz (BST)” system of equations. Levinson-like and Schur-like fast algorithms are developed for solving the symmetric BST system of equations. The significance of these algorithms is as follows. If the kernel of the integral equation is not a Calderon-Zygmund operator, the wavelet transform may not sparsify it. The kernel of the Krein and Wiener-Hopf integral equations does not, in general, satisfy the Calderon-Zygmund conditions. As a result, application of the wavelet transform to the integral equation does not yield a sparse system matrix. There is, therefore, a need for fast algorithms that directly exploit the (symmetric block-slanted Toeplitz) structure of the system matrix and do not rely on sparsity. The first such O(n²) algorithms, viz., a Levinson-like algorithm and a Schur (1917) like algorithm, are presented. These algorithms are also applied to the factorization of the BST system matrix. The Levinson-like algorithm also yields a test for positive definiteness of the BST system matrix. The results obtained are directly applicable to the problem of constrained deconvolution of a nonstationary signal, where the locations of the smooth regions of the signal being deconvolved are known a priori