Fast identification of state-space models via exploitation of displacement structure

The computational burden of state-space model identification has prevented its real-time application, although it offers some important advantages over other methods based on input/output transfer functions. A recently proposed state-space identification method uses ideas from sensor array signal processing to somewhat reduce the computational burden. The major costs still remain because of the need for the singular value (or sometimes QR) decomposition, which requires O(MN²) hops and O(N²) storage when the data matrix has size M×N, N>M. It turns out that proper exploitation, using results from the theory of displacement structure, of the Toeplitz-like nature of several matrices arising in the procedure reduces the computational effort to O(MN) flops with O(M²+N) storage. Further computational gains are made by using the recently developed fast subspace decomposition methods. Results of the study of an actual system are described