GIVENS ROTATION BASED LEAST-SQUARES LATTICE AND RELATED ALGORITHMS

In this paper, we present a general and systematic approach for deriving new LS estimation algorithms that are based solely on Givens rotations. In particular, we use this general approach to derive efficient Givens rotation based LS lattice algorithms-the Givens-lattice algorithms. By exploiting the relationship between the Givens algorithms [1]-[3] and the recursive modified Gram-Schmidt (RMGS) [4], [5] algorithm, we show that the time and order update of any order-recursive LS estimation algorithm can be realized by employing only Givens rotations. Applying this general conclusion to LS estimation of time-series signals results in the Givens-lattice algorithms. Two Givens-lattice algorithms, one with square roots and the other without, are presented. It is shown that the Givens-lattice algorithms are computationally more efficient than the newly derived fast QR algorithm [6]. The derivation of other Givens rotation-based LS estimation algorithms and their systolic array implementations are discussed.