A FAST ALGORITHM FOR QR-1 FACTORIZATION OF TOEPLITZ MATRICES

In this paper a new order recursive algorithm for the efficient 2R-1 factorization of Toeplitz matrices is described. The proposed algorithm can be seen as a fast modified Gram-Schmidt method which recursively computes the orthonormal columns 2i, i = 1,2,...,p, of 2, as well as the elements of R-1, of a Toeplitz matrix X with dimensions L x p. The 2 factor estimation requires 8Lp MADS (multiplications and divisions). Matrix R-1 is subsequently estimated using 3p2 MADS. A faster algorithm, based on a mixed 2 and R-1 updating scheme, is also derived. It requires 7Lp + 3.5p2 MADS. The algorithm can be efficiently applied to batch least squares FIR filtering and system identification. When determination of the optimal filter is the desired task it can be utilized to compute the least squares filter in an order recursive way. The algorithm operates directly on the experimental data, overcoming the need for covariance estimates. An orthogonalized version of the proposed 2R-1 algorithm is derived. Matlab code implementing the algorithm is also supplied.