FAST ORTHOGONALIZATION ALGORITHM AND PARALLEL ARCHITECTURE FOR AR SPECTRAL ESTIMATION BASED ON FORWARD - BACKWARD LINEAR PREDICTION

Abstract

The truncated QR methods have been shown to be comparable to the SVD-based methods for the sinusoidal frequency estimation based on the forward-backward linear prediction (FBLP) model. However, without exploiting the special structure of the FBLP matrix, the QR decomposition (QRD) of the FBLP matrix has the computational complexity on the order of 2(6m - n)n2/3 + O(n2) for a 2m x n FBLP matrix. Here we propose a fast algorithm to perform the QRD of the FBLP matrix by exploiting its special Toeplitz-Hankel form. The computational complexity is then reduced to 10n2 + 4mn + O(n). The fast algorithm can also be easily implemented onto a linear systolic array. The number of time steps required is further reduced to 2m + 5n - 4 by using the parallel implementation.