Scalable extraction of analytic eigenvalues from a parahermitian matrix

In order to determine the analytic eigenvalues of a parahermitian matrix, the state-of-the-art algorithm offers proven convergence but its complexity grows factorially with the matrix dimension. Operating in the discrete Fourier transform (DFT) domain, its computational bottleneck is a maximum likelihood (ML) sequence estimation, that investigates a set of paths of likely associations across DFT bins. Therefore, this paper investigates an algorithm that remains covered by its predecessor’s proof of convergence but offers a significant reduction in complexity by trading the number of retained paths versus the DFT length. We motivate this, and also introduce an enhanced initialisation point for the ML sequence estimation. The benefits of this proposed scalable analytic extraction algorithm are illustrated in simulations.