×

System identification via CUR-factored Hankel approximation. (English) Zbl 1383.93022

Summary: Subspace-based system identification for dynamical systems is a sound, system-theoretic 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.

MSC:

93B11 System structure simplification
93B30 System identification
93B40 Computational methods in systems theory (MSC2010)
93C05 Linear systems in control theory
65F99 Numerical linear algebra
15A18 Eigenvalues, singular values, and eigenvectors
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A. C. Antoulas, {\it Approximation of Large-Scale Dynamical Systems}, Adv. Des. Control 6, SIAM, Philadelphia, 2005, . · Zbl 1112.93002
[2] H. Cheng, Z. Gimbutas, P. G. Martinsson, and V. Rokhlin, {\it On the compression of low rank matrices}, SIAM J. Sci. Comput., 26 (2005), pp. 1389-1404, . · Zbl 1083.65042
[3] D. S. Djordjević and N. Č. Dinčić, {\it Reverse order law for the Moore-Penrose inverse}, J. Math. Anal. Appl., 361 (2010), pp. 252-261. · Zbl 1175.47003
[4] P. Drineas, M. W. Mahoney, and S. Muthukrishnan, {\it Relative-error CUR matrix decompositions}, SIAM J. Matrix Anal. Appl., 30 (2008), pp. 844-881, . · Zbl 1183.68738
[5] Z. Drmač and S. Gugercin, {\it A new selection operator for the discrete empirical interpolation method–improved a priori error bound and extensions}, SIAM J. Sci. Comput., 38 (2016), pp. A631-A648, . · Zbl 1382.65193
[6] G. Golub and C. Reinsch, {\it Singular value decomposition and least squares solutions}, Numer. Math., 14 (1970), pp. 403-420. · Zbl 0181.17602
[7] G. Golub and C. F. Van Loan, {\it Matrix Computations}, Johns Hopkins University Press, Baltimore, MD, 1996, pp. 374-426. · Zbl 0865.65009
[8] S. Goreinov, I. Oseledets, D. Savostyanov, E. Tyrtyshnikov, and N. Zamarashkin, {\it How to find a good submatrix}, in Matrix Methods: Theory, Algorithms and Applications, World Scientific, Hackensack, NJ, 2010, pp. 247-256. · Zbl 1215.65078
[9] S. Goreinov and E. Tyrtyshnikov, {\it The maximal-volume concept in approximation by low-rank matrices}, in Structured Matrices in Mathematics, Computer Science, and Engineering, I (Boulder, CO, 1999), Contemp. Math. 280, AMS, Providence, RI, 2001, pp. 47-51. · Zbl 1003.15025
[10] S. Goreinov and E. Tyrtyshnikov, {\it Quasi-optimality of a skeleton approximation of a matrix in the Chebyshev norm}, Dokl. Math., 83 (2011), pp. 374-375. · Zbl 1252.65078
[11] S. A. Goreinov, E. Tyrtyshnikov, and N. Zamarashkin, {\it A theory of pseudoskeleton approximations}, Linear Algebra Appl., 261 (1997), pp. 1-21. · Zbl 0877.65021
[12] S. Gugercin and A. C. Antoulas, {\it Model reduction of large-scale systems by least squares}, Linear Algebra Appl., 415 (2006), pp. 290-321. · Zbl 1112.93015
[13] S. Gugercin, R. Polyuga, C. Beattie, and A. Van Der Schaft, {\it Structure-preserving tangential interpolation for model reduction of port-Hamiltonian systems}, Automatica J. IFAC, 48 (2012), pp. 1963-1974. · Zbl 1257.93021
[14] J. Hokanson, {\it Numerically Stable and Statistically Efficient Algorithms for Large Scale Exponential Fitting}, Ph.D. thesis, Rice University, Houston, TX, 2013.
[15] A. C. Ionita and A. C. Antoulas, {\it Matrix pencils in time and frequency domain system identification}, in Developments in Control Theory towards Glocal Control, IET Control Eng. Ser. 76, IET, London, 2012, pp. 79-88.
[16] J.-N. Juang and R. Pappa, {\it An eigensystem realization algorithm for modal parameter identification and model reduction}, J. Guidance Control Dynam., 8 (1985), pp. 620-627. · Zbl 0589.93008
[17] B. Kramer and S. Gugercin, {\it Tangential interpolation-based eigensystem realization algorithm for MIMO systems}, Math. Comput. Model. Dyn. Syst., 22 (2016), pp. 282-306. · Zbl 1348.93132
[18] S.-Y. Kung, {\it A new identification and model reduction algorithm via singular value decomposition}, in Proceedings of the 12th Asilomar Conference on Circuits, Systems, and Computers, Pacific Grove, CA, 1978, pp. 705-714.
[19] Z. Ma, S. Ahuja, and C. W. Rowley, {\it Reduced-order models for control of fluids using the eigensystem realization algorithm}, Theoret. Comput. Fluid Dynam., 25 (2011), pp. 233-247. · Zbl 1272.76103
[20] M. W. Mahoney and P. Drineas, {\it CUR matrix decompositions for improved data analysis}, Proc. Natl. Acad. Sci. USA, 106 (2009), pp. 697-702. · Zbl 1202.68480
[21] I. Oseledets and E. Tyrtyshnikov, {\it TT-cross approximation for multidimensional arrays}, Linear Algebra Appl., 432 (2010), pp. 70-88. · Zbl 1183.65040
[22] V. Rokhlin, A. Szlam, and M. Tygert, {\it A randomized algorithm for principal component analysis}, SIAM J. Matrix Anal. Appl., 31 (2009), pp. 1100-1124, . · Zbl 1198.65035
[23] D. C. Sorensen and M. Embree, {\it A DEIM induced CUR factorization}, SIAM J. Sci. Comput., 38 (2016), pp. A1454-A1482, . · Zbl 1382.65121
[24] B. Zhu, Q. Zhang, Y. Pan, E. Mace, B. York, A. Antoulas, C. Dacso, and B. W. O’Malley, {\it A cell-autonomous mammalian 12 hr clock coordinates metabolic and stress rhythms}, Cell Metabolism, 25 (2017), pp. 1305-1319.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.