Connections of Time-Varying Systems and Computational Linear Algebra
A. van Veen, Patrick M. Dewilde · Research Repository (Delft University of Technology) · 1993
Linear algebra problems such as matrix-vector multiplication, inversion and factorizations may be studied from the point of view of time-varying systems and state realizations. This leads to new and efficient algorithms for solving certain large structured matrix problems. In this paper, we treat the matrix inversion problem in more detail. 1. STATE REALIZATION OF A MATRIX In a number of signal processing applications, such as inverse filtering and spectrum estimation, the basic algorithmic kernel consists of QR-factorizations and matrix inversions of fairly large matrices. Usually, these matrices are not fully random but have some kind of structure, which is inherited from the underlying signal properties. For example, in stationary environments, the covariance matrices formed on the data have a Toeplitz structure (constant along diagonals). Efficient algorithms which exploit this structure are known in this case: the inverse can be computed via Levinson recursions or Gohberg/Semencul recursions [1], and the QR-factorization can be computed via a generalization of the Schur recursion [2]. The resulting algorithms have computational complexity of order (n 2) for matrices of size (n×n), as compared to (n3) for algorithms that do not take the Toeplitz structure into account. In this paper, we consider a different (complementary) kind of structure in a matrix which applies, for example, to non-stationary signal models. Let T = [Tij] n i,j=1 be a matrix with entries Tij. For added generality, we will allow T to be a block matrix so that the entries are matrices themselves: Tij is an Mi × Nj matrix, where the dimensions Mi and Nj need not be constant over i and j, and can even be equal to zero at some points. When a (row) vector is viewed as a signal sequence on a finite discrete-time interval, then a vector-matrix multiplication corresponds to the application of a system to the signal. The i-th row of the matrix is the impulse response of the system due to an impulse at time i, and the system is causal if the matrix is block upper. We will say that T has a state realization (computational network) if there exist matrices