An inverse factorization algorithm for linear prediction (Q1194518): Difference between revisions

A method which is based on a fast \(QR\) factorization algorithm of \textit{A. W. Bojanczyk}, \textit{R. P. Brent} and \textit{F. R. de Hoog} [Numer. Math. 49, 81-94 (1986; Zbl 0574.65019)] is described. An inverse factorization technique is presented for solving linear prediction problems arising in signal processing. The algorithm uses the rectangular Toeplitz structure of the data to recursively compute the prediction error and to solve the problem when the optimum filter order is found. The novelty of the scheme is the use of an inverse factorization scheme due to \textit{C.-T. Pan} and the second author [J. Comput. Appl. Math. 27, No. 1/2, 109-127 (1989; Zbl 0677.65037)] for solving the linear prediction problem with low computational complexity and without the need for solving triangular systems. A systolic array implementation of these problems is realized. It is shown that this algorithm has low numerical complexity, and can be implemented on a linear systolic array in \(n+(1/2)p_ 0^ 2+(13/2)p_ 0\) time steps, where \(n\) is the number of data samples and \(p_ 0\) is the optimal order of the predictor.