Accurate and efficient solution of Hankel matrix systems by FFT and the conjugate gradient methods

Hankel matrix systems often arise in many problems of signal analysis. Toeplitz matrix systems is a special case of a Hankel matrix equations. Both the auto-correlation and the covariance matrix equations are different forms of the Hankel matrix equations. Trench has developed a direct method that can solve Hankel matrix equations in θ(N²) operations. In this paper, we propose an alternate algorithm. This new method is a combination of the FFT and the conjugate gradient method. The advantage of this new approach is that it is computationally robust to highly ill-conditioned and even singular matrix equations. Preliminary results indicated that for very large complex Toeplitz matrix equations, the CPU time is proportional to N as the number of unknowns as increased, as opposed to N²for conventional methods.