Least squares modifications with inverse factorizations: Parallel implications

摘要

The process of modifying least squares computations by updating the covariance matrix has been used in control and signal processing for some time in the context of linear sequential filtering. Here we give an alternative derivation of the process and provide extensions to downdating. Our purpose is to develop algorithms that are amenable to implementation on modern multiprocessor architectures. In particular, the inverse Cholesky factor R−1 is considered and it is shown that R−1 can be updated (downdated) by applying the same sequence of orthogonal (hyperbolic) plane rotations that are used to update (downdate) R. We have attempted to provide some new insights into least squares modification processes and to suggest parallel algorithms for implementing Kalman type sequential filters in the analysis and solution of estimation problems in control and signal processing.