NASA Logo

NTRS

NTRS - NASA Technical Reports Server

Back to Results
On realizations of least-squares estimation and Kalman filtering by systolic arraysLeast-squares (LS) estimation is a basic operation in many signal processing problems. Given y = Ax + v, where A is a m x n coefficient matrix, y is a m x 1 observation vector, and v is a m x 1 zero mean white noise vector, a simple least-squares solution is finding the estimated vector x which minimizes the norm of /Ax-y/. It is well known that for an ill-conditioned matrix A, solving least-squares problems by orthogonal triangular (QR) decomposition and back substitution has robust numerical properties under finite word length effect since 2-norm is preserved. Many fast algorithms have been proposed and applied to systolic arrays. Gentleman-Kung (1981) first presented the trianglular systolic array for a basic Givens reduction. McWhirter (1983) used this array structure to find the least-squares estimation errors. Then by geometric approach, several different systolic array realizations of the recursive least-squares estimation algorithms of Lee et al (1981) were derived by Kalson-Yao (1985). Basic QR decomposition algorithms are considered in this paper and it is found that under a one-row time updating situation, the Householder transformation degenerates to a simple Givens reduction. Next, an improved least-squares estimation algorithm is derived by considering a modified version of fast Givens reduction. From this approach, the basic relationship between Givens reduction and Modified-Gram-Schmidt transformation can easily be understood. This improved algorithm also has simpler computational and inter-cell connection complexities while compared with other known least-squares algorithms and is more realistic for systolic array implementation.
Document ID
19860020600
Acquisition Source
Legacy CDMS
Document Type
Conference Paper
Authors
Chen, M. J.
(California Univ. Los Angeles, CA, United States)
Yao, K.
(California Univ. Los Angeles, CA, United States)
Date Acquired
August 12, 2013
Publication Date
June 1, 1986
Publication Information
Publication: A Survey of the State-of-the-Art and Focused Research in Range Systems, Task 2
Subject Category
Electronics And Electrical Engineering
Accession Number
86N30072
Distribution Limits
Public
Copyright
Work of the US Gov. Public Use Permitted.
No Preview Available