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 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ) 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 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> for conventional methods.