Givens rotation based least squares lattice and related algorithms

The author presents a general and systematic approach for deriving new LS (least squares) estimation algorithms that are based solely on Givens rotations. In particular, this approach is used to derive efficient Givens-rotation-based LS lattice algorithms-the Givens-lattice algorithms. By exploiting the relationship between the Givens algorithms and the recursive modified Gram-Schmidt algorithm, it is shown 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 fast QR algorithm of Cioffi (1987). The derivation of other Givens rotation-based LS estimation algorithms and their systolic array implementations are discussed