SYSTEM IDENTIFICATION VIA CUR-FACTORED HANKEL APPROXIMATION

Subspace-based system identification for dynamical systems is a sound, systemtheoretic way to obtain linear, time-invariant system models from data. The interplay of data and systems theory is reflected in the Hankel matrix, a block-structured matrix whose factorization is used for system identification. For systems with many inputs, many outputs, or large time-series of system-response data, established methods based on the singular value decomposition (SVD)-such as the eigensystem realization algorithm (ERA)-are prohibitively expensive. In this paper, we propose an algorithm to reduce the complexity of the ERA from cubic to linear, with respect to the Hankel matrix size. Furthermore, our memory requirements scale at the same rate because we never require loading the entire Hankel matrix into memory. These reductions are realized by replacing the SVD with a CUR decomposition that directly seeks a low-rank approximation of the Hankel matrix. The CUR decomposition is obtained using a maximum-volume-based cross-approximation scheme that selects a small number of rows and columns to form the row and column space of the approximation. We present a worst-case error bound for our resulting system identification algorithm, and we demonstrate its computational advantages and accuracy on a numerical example. The example demonstrates that the resulting identification yields almost indistinguishable results compared with the SVD-based ERA yet comes with significant computational savings.