An inverse factorization algorithm for linear prediction

DOI10.1016/0024-3795(92)90025-6MaRDI QIDQ1194518zbMATH OpenOpenAlexWikidataFDO

Authors James G. Nagy, Robert J. Plemmons

Publication date 27 September 1992

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0024-3795(92)90025-6

zbMATH Keywords

computational complexityfast \(QR\) factorization algorithminverse factorization schemelinear predictionoptimum filter ordersignal processingsystolic array

Mathematics Subject Classification ID

Prediction theory (aspects of stochastic processes) (60G25) Inference from stochastic processes and prediction (62M20) Probabilistic methods, stochastic differential equations (65C99)

Review text

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.

Recommendations

• Recursive Least Squares Algorithm for Linear Prediction Problems
• Fast algorithms for linear prediction and system identification filters with linear phase
• Systolic implementation of the lattice algorithm for least squares linear prediction problems
• Recursive solution of the covariance equations for linear prediction
• A General Orthogonalization Technique with Applications to Time Series Analysis and Signal Processing

Cites work

• A General Orthogonalization Technique with Applications to Time Series Analysis and Signal Processing
• A parallel implementation of the inverse QR adaptive filter
• Analysis of a recursive least squares hyperbolic rotation algorithm for signal processing
• Fast Parallel Algorithms for QR and Triangular Factorization
• scientific article; zbMATH DE number 4213315 (Why is no real title available?)
• Least squares modifications with inverse factorizations: Parallel implications
• QR factorization of Toeplitz matrices
• Recursive Least Squares Algorithm for Linear Prediction Problems
• Superfast Solution of Real Positive Definite Toeplitz Systems
• Systolic implementation of the lattice algorithm for least squares linear prediction problems

Cited in

(8)

• Systolic implementation of the lattice algorithm for least squares linear prediction problems
• Recursive solution of the covariance equations for linear prediction
• Three-dimensional linear prediction and its application to digital angiography
• Conference celebrating the 60th birthday of Robert J. Plemmons. Papers from the conference, Winston-Salem, NC, USA, January 1999
• Dedication to Robert J. Plemmons
• A General Orthogonalization Technique with Applications to Time Series Analysis and Signal Processing
• Fast algorithms for linear prediction and system identification filters with linear phase
• Recursive Least Squares Algorithm for Linear Prediction Problems

This page was built for publication: An inverse factorization algorithm for linear prediction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1194518)