Fast algorithms for close-to-Toeplitz-plus-Hankel systems of equations and two-sided linear prediction.

Abstract

We extend the low-displacement-rank definition of close-to-Toeplitz (CT) matrices to close-to-Toeplitz-plus-Hankel (CTPH) matrices, and develop new fast algorithms for solving CTPH systems of equations. A matrix is defined as CTPH if it is the sum of a CT matrix and a second CT matrix post-multiplied by an exchange matrix. We then provide an alternative definition of CTPH matrices in terms of UV-rank, relate it to the first definition, and develop new fast algorithms for these CTPH systems of equations. These definitions are motivated by our application of the new algorithms to two-sided linear prediction (TSP), which differs from one-sided linear prediction (OSP) in that both past and future time series values are used in a symmetric manner to estimate the present value of the time series. We define autocorrelation and covariance forms of TSP analogous to those for OSP; the covariance form of TSP is solved using the new CTPH algorithms, just as the covariance form of OSP is solved using CT fast algorithms. We then study TSP itself, and provide the first detailed evaluation of TSP, and the first detailed comparison between TSP and OSP. When applied to linear prediction, TSP is proven to produce smaller residuals than OSP, smaller by a known factor for finite-order autoregressive processes. When applied to spectral estimation, TSP matches spectral valleys better than spectral peaks, while OSP matches spectral peaks better than spectral valleys. Numerical examples show that TSP also performs better than OSP in spectral line estimation, since it is equivalent to the extended Prony's method. We also show that TSP is applicable to the problem of stochastic least-squares blind deconvolution of a symmetric impulse response, which arises in geophysical inversion. Finally, we employ number-theoretic transforms (NTT) to obtain alternative fast algorithms for solving Toeplitz systems of equations and linear least-squares smoothing problems on finite intervals. Employing NTTs greatly reduces the number of multiplications required by these algorithms and eliminates roundoff errors, which can be significant in solving ill-conditioned systems of equations. We present novel ways of representing rational numbers in terms of integers in the ring of integers modulo an integer, and computing determinants of Toeplitz matrices in this ring. The result is an alternative set of fast algorithms for smoothing problems.