A general orthogonalization technique with applications to time series analysis and signal processing

Abstract:

A new orthogonalization technique is presented for computing the QR factorization of a general $n \times p$ matrix of full rank $p (n \geqslant p)$. The method is based on the use of projections to solve increasingly larger subproblems recursively and has an $O(n{p^2})$ operation count for general matrices. The technique is readily adaptable to solving linear least-squares problems. If the initial matrix has a circulant structure the algorithm simplifies significantly and gives the so-called lattice algorithm for solving linear prediction problems. From this point of view it is seen that the lattice algorithm is really an efficient way of solving specially structured least-squares problems by orthogonalization as opposed to solving the normal equations by fast Toeplitz algorithms.