A lattice algorithm dual to the extended inverse QR algorithm

Abstract

This paper presents a new lattice algorithm dual to the extended Inverse QR (IQR) algorithm recently derived by the authors. The original IQR and our extended IQR algorithms are transversal filter algorithms. We found that by assuming a spatial displacement property on the initial correlation matrix of reference data consistent with a time-shifting property of reference data stored in taps of a transversal filter, we could develop a fast version of the extended IQR algorithm. This fast IQR algorithm turns out to have a lattice filter structure instead of a transversal filter structure. Whereas the extended IQR algorithm requires O(M(2)p) computations per iteration, its fast version called a new hybrid QR/LLS algorithm requires O(Mp(2)) computations per iteration, where M, the number of taps, is usually much greater than p, the number of channels. This new hybrid QR/LLS algorithm differs from Regalia and Bellanger's hybrid QR/LLS algorithm, because the former is dual to the IQR algorithm and is based on the use of variance-normalized a priori backwards prediction errors, while the latter is dual to the QR algorithm and is based on the use of variance-normalized a posteriori backwards prediction errors.