A generalization of the Levinson algorithm for Hermitian Toeplitz matrices with any rank profile
P. Delsarte, Yves V. Genin, Yves Kamp · IEEE Transactions on Acoustics Speech and Signal Processing · 1985
The paper describes a recursive algorithm for solving Hermitian Toeplitz systems of linear equations, without any restriction on the ranks of their nested Toeplitz subsystems. Such a general algorithm is needed, e.g., to obtain the eigenfilters for signal processing applications, or to compute the inverse of a nondefinite Toeplitz matrix. The regular portion of the algorithm is made of the classical Levinson recursion. The singular portion requires solving some well-defined systems of linear equations with gradient structure. The dimension of each of these sytems equals the amplitude of the corresponding singularity.