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

The low-displacement-rank definition of close-to-Toeplitz (CT) matrices is extended to close-to-Toeplitz-plus-Hankel (CTPH) matrices. Fast algorithms for solving CTPH systems of equations are presented. A matrix is defined as CTPH if the sum of a CT matrix and a second CT matrix postmultiplied by an exchange matrix; an equivalent definition in terms of UV rank is also given. This definition is motivated by the application of the algorithms to two-sided linear prediction (TSP). Autocorrelation and covariance forms of TSP analogous to those for one-sided linear prediction (OSP) are defined. The covariance form of TSP is solved using the CTPH fast algorithms, just as the covariance form of OSP is solved using CT fast algorithms. Numerical examples show that TSP produces smaller residuals than OSP and resolves sharp spectral peaks better than OSP, and that covariance TSP produces smaller residuals than autocorrelation TSP