Inner-outer factorization and the inversion of locally finite systems of equations

We consider the problem of computing the inverse of a large class of infinite systems of linear equations, which are described by a finite set of data. The class consists of equations in which the linear operator is represented by a discrete time-varying dynamical system whose local state space is of finite dimension at each time point k, and which reduces to time invariant systems for time points k --> +/-infinity. In this generalization of classical matrix inversion theory, inner-outer factorizations of operators play the role that QR-factorization plays in classical linear algebra. Numerically, they lead to so-called 'square root' implementations, for which am-active algorithms can be derived, which do not require the determination of spurious multiple eigenvalues, as would be the case if the problem was converted to a discrete time Riccati equation by squaring. We give an overview of the theory and the derivation of the main algorithms. The theory contains both the standard LTI case and the case of a finite set of linear equations as special instances, a particularly instance of which is called 'matrices of low Hanker rank', recently sometimes called 'quasi-separable matrices'. However, in the general case considered here, new phenomena occur which are not observed in these classical cases, namely the occurrence of 'defect spaces'. We describe these and give an algorithm to compute them as well. In all cases, the algorithms given are linear in the amount of data. (C) 2000 Elsevier Science Inc. All rights reserved.