Top

Foundations of Computational Mathematics

Published in:

23-01-2023

On the Sample Complexity of Stabilizing Linear Dynamical Systems from Data

Authors: Steffen W. R. Werner, Benjamin Peherstorfer

Published in: Foundations of Computational Mathematics | Issue 3/2024

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Learning controllers from data for stabilizing dynamical systems typically follows a two-step process of first identifying a model and then constructing a controller based on the identified model. However, learning models means identifying generic descriptions of the dynamics of systems, which can require large amounts of data and extracting information that are unnecessary for the specific task of stabilization. The contribution of this work is to show that if a linear dynamical system has dimension (McMillan degree) \(n\), then there always exist \(n\) states from which a stabilizing feedback controller can be constructed, independent of the dimension of the representation of the observed states and the number of inputs. By building on previous work, this finding implies that any linear dynamical system can be stabilized from fewer observed states than the minimal number of states required for learning a model of the dynamics. The theoretical findings are demonstrated with numerical experiments that show the stabilization of the flow behind a cylinder from less data than necessary for learning a model.

previous article A Stirling-Type Formula for the Distribution of the Length of Longest Increasing Subsequences

next article Optimal Polynomial Meshes Exist on any Multivariate Convex Domain

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Antoulas, A.C.: Approximation of Large-Scale Dynamical Systems, Adv. Des. Control, vol. 6. SIAM, Philadelphia, PA (2005). https://doi.org/10.1137/1.9780898718713

Armstrong, E.: An extension of Bass’ algorithm for stabilizing linear continuous constant systems. IEEE Trans. Autom. Control 20(1), 153–154 (1975). https://doi.org/10.1109/TAC.1975.1100874MathSciNetCrossRef

Armstrong, E., Rublein, G.: A stabilization algorithm for linear discrete constant systems. IEEE Trans. Autom. Control 21(4), 629–631 (1976). https://doi.org/10.1109/TAC.1976.1101295MathSciNetCrossRef

Beattie, C.A., Gugercin, S.: Realization-independent \(\cal{H}_2\)-approximation. In: 51st IEEE Conference on Decision and Control (CDC), pp. 4953–4958 (2012). https://doi.org/10.1109/CDC.2012.6426344

Behr, M., Benner, P., Heiland, J.: Example setups of Navier-Stokes equations with control and observation: Spatial discretization and representation via linear-quadratic matrix coefficients. e-print arXiv:1707.08711, arXiv (2017). https://doi.org/10.48550/arXiv.1707.08711. Mathematical Software (cs.MS)

Benner, P., Castillo, M., Quintana-Ortí, E.S., Hernández, V.: Parallel partial stabilizing algorithms for large linear control systems. J. Supercomput. 15(2), 193–206 (2000). https://doi.org/10.1023/A:1008108004247CrossRef

Benner, P., Gugercin, S., Willcox, K.: A survey of projection-based model reduction methods for parametric dynamical systems. SIAM Rev. 57(4), 483–531 (2015). https://doi.org/10.1137/130932715MathSciNetCrossRef

Benner, P., Heiland, J., Werner, S.W.R.: Robust output-feedback stabilization for incompressible flows using low-dimensional \(\cal H\it _{\infty }\)-controllers. Comput. Optim. Appl. 82(1), 225–249 (2022). https://doi.org/10.1007/s10589-022-00359-xMathSciNetCrossRef

Benner, P., Li, J.R., Penzl, T.: Numerical solution of large-scale Lyapunov equations, Riccati equations, and linear-quadratic optimal control problems. Numer. Lin. Alg. Appl. 15(9), 755–777 (2008). https://doi.org/10.1002/nla.622MathSciNetCrossRef

10.

Benner, P., Schilders, W., Grivet-Talocia, S., Quarteroni, A., Rozza, G., Silveira, L.M.: Model Order Reduction. Volume 1: System- and Data-Driven Methods and Algorithms. De Gruyter, Berlin, Boston (2021). https://doi.org/10.1515/9783110498967

11.

Benner, P., Schilders, W., Grivet-Talocia, S., Quarteroni, A., Rozza, G., Silveira, L.M.: Model Order Reduction. Volume 2: Snapshot-Based Methods and Algorithms. De Gruyter, Berlin, Boston (2021). https://doi.org/10.1515/9783110671490

12.

Benner, P., Werner, S.W.R.: MORLAB – Model Order Reduction LABoratory (version 5.0) (2019). https://doi.org/10.5281/zenodo.3332716. See also: https://www.mpi-magdeburg.mpg.de/projects/morlab

13.

Benner, P., Werner, S.W.R.: MORLAB—The Model Order Reduction LABoratory. In: P. Benner, T. Breiten, H. Faßbender, M. Hinze, T. Stykel, R. Zimmermann (eds.) Model Reduction of Complex Dynamical Systems, International Series of Numerical Mathematics, vol. 171, pp. 393–415. Birkhäuser, Cham (2021). https://doi.org/10.1007/978-3-030-72983-7_19

14.

Berberich, J., Koch, A., Scherer, C.W., Allgöwer, F.: Robust data-driven state-feedback design. In: 2020 American Control Conference (ACC), pp. 1532–1538 (2020). https://doi.org/10.23919/ACC45564.2020.9147320

15.

Boyd, S., Ghaoui, L.E., Feron, E., Balakrishnan, V.: Linear Matrix Inequalities in Systems and Control Theory, Studies in Applied and Numerical Mathematics, vol. 15. SIAM, Philadelphia, PA (1994). https://doi.org/10.1137/1.9781611970777

16.

Breiten, T., Morandin, R., Schulze, P.: Error bounds for port-Hamiltonian model and controller reduction based on system balancing. Comput. Math. Appl. 116, 100–115 (2021). https://doi.org/10.1016/j.camwa.2021.07.022MathSciNetCrossRef

17.

Brunton, S.L., Brunton, B.W., Proctor, J.L., Kutz, J.N.: Koopman invariant subspaces and finite linear representations of nonlinear dynamical systems for control. PLoS ONE 11(2), e0150171 (2016). https://doi.org/10.1371/journal.pone.0150171CrossRef

18.

Brunton, S.L., Kutz, J.N.: Data-driven science and engineering: machine learning, dynamical systems, and control. Cambridge University Press, Cambridge (2019). https://doi.org/10.1017/9781108380690

19.

Brunton, S.L., Proctor, J.L., Kutz, J.N.: Discovering governing equations from data by sparse identification of nonlinear dynamical systems. Proc. Natl. Acad. Sci. U. S. A. 113(15), 3932–3937 (2016). https://doi.org/10.1073/pnas.1517384113MathSciNetCrossRef

20.

Campi, M.C., Lecchini, A., Savaresi, S.M.: Virtual reference feedback tuning: a direct method for the design of feedback controllers. Automatica J. IFAC 38(8), 1337–1346 (2002). https://doi.org/10.1016/S0005-1098(02)00032-8MathSciNetCrossRef

21.

Datta, B.N.: Numerical Methods for Linear Control Systems: Design and Analysis. Academic Press, San Diego, CA (2004). https://doi.org/10.1016/B978-0-12-203590-6.X5000-9

22.

De Hoop, M.V., Kovachki, N.B., Nelsen, N.H., Stuart, A.M.: Convergence rates for learning linear operators from noisy data. e-print 2108.12515, arXiv (2021). https://doi.org/10.48550/arXiv.2108.12515. Statistics Theory (math.ST)

23.

De Persis, C., Tesi, P.: Formulas for data-driven control: Stabilization, optimality, and robustness. IEEE Trans. Autom. Control 65(3), 909–924 (2020). https://doi.org/10.1109/TAC.2019.2959924MathSciNetCrossRef

24.

Dean, S., Mania, H., Matni, N., Recht, B., S., T.: On the sample complexity of the linear quadratic regulator. Found. Comput. Math. 20(4), 633–679 (2020). https://doi.org/10.1007/s10208-019-09426-y

25.

Dragan, V., Halanay, A.: Stabilization of Linear Systems. Systems & Control: Foundations & Applications. Birkhäuser, Boston, MA (1999). https://doi.org/10.1007/978-1-4612-1570-7

26.

Drmač, Z., Mezić, I., Mohr, R.: Data driven modal decompositions: Analysis and enhancements. SIAM J. Sci. Comput. 40(4), A2253–A2285 (2018). https://doi.org/10.1137/17M1144155MathSciNetCrossRef

27.

Fliess, M., Join, C.: Model-free control. Int. J. Control 86(12), 2228–2252 (2013). https://doi.org/10.1080/00207179.2013.810345MathSciNetCrossRef

28.

Gevers, M., Bazanella, A.S., Bombois, X., Miskovic, L.: Identification and the information matrix: How to get just sufficiently rich? IEEE Trans. Autom. Control 54(12), 2828–2840 (2009). https://doi.org/10.1109/TAC.2009.2034199MathSciNetCrossRef

29.

Golub, G.H., Van Loan, C.F.: Matrix Computations, fourth edn. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore (2013)CrossRef

30.

Gosea, I.V., Gugercin, S., Beattie, C.: Data-driven balancing of linear dynamical systems. SIAM J. Sci. Comput. 44(1), A554–A582 (2022). https://doi.org/10.1137/21M1411081MathSciNetCrossRef

31.

Grant, M., Boyd, S.: CVX: Matlab software for disciplined convex programming, version 2.2. http://cvxr.com/cvx (2020)

32.

Grant, M.C., Boyd, S.P.: Graph implementations for nonsmooth convex programs. In: V.D. Blondel, S.P. Boyd, H. Kimura (eds.) Recent Advances in Learning and Control, Lect. Notes Control Inf. Sci., vol. 371, pp. 95–110. Springer, London (2008). https://doi.org/10.1007/978-1-84800-155-8_7

33.

Gurobi Optimization, LLC: Gurobi optimizer reference manual (2022). https://www.gurobi.com

34.

Ho, B.L., Kalman, R.E.: Editorial: Effective construction of linear state-variable models from input/output functions. at-Automatisierungstechnik 14(1–12), 545–548 (1966). https://doi.org/10.1524/auto.1966.14.112.545

35.

Jonckheere, E.A., Silverman, L.M.: A new set of invariants for linear systems–application to reduced order compensator design. IEEE Trans. Autom. Control 28(10), 953–964 (1983). https://doi.org/10.1109/TAC.1983.1103159MathSciNetCrossRef

36.

Kaiser, E., Kutz, J.N., Brunton, S.L.: Sparse identification of nonlinear dynamics for model predictive control in the low-data limit. Proc. R. Soc. A: Math. Phys. Eng. Sci. 474(2219), 20180335 (2018). https://doi.org/10.1098/rspa.2018.0335MathSciNetCrossRef

37.

Kaiser, E., Kutz, J.N., Brunton, S.L.: Data-driven discovery of Koopman eigenfunctions for control. Mach. Learn.: Sci. Technol. 2(3), 035023 (2021). https://doi.org/10.1088/2632-2153/abf0f5

38.

Kramer, B., Peherstorfer, B., Willcox, K.: Feedback control for systems with uncertain parameters using online-adaptive reduced models. SIAM J. Appl. Dyn. Syst. 16(3), 1563–1586 (2017). https://doi.org/10.1137/16M1088958MathSciNetCrossRef

39.

Lancaster, P., Rodman, L.: Algebraic Riccati Equations. Oxford Science Publications. The Clarendon Press, Oxford University Press, New York (1995)CrossRef

40.

Leibfritz, F.: \(COMPl_{e}ib\): COnstrained Matrix-optimization Problem library – a collection of test examples for nonlinear semidefinite programs, control system design and related problems. Tech.-report, University of Trier (2004). http://www.friedemann-leibfritz.de/COMPlib_Data/COMPlib_Main_Paper.pdf

41.

Lequin, O., Gevers, M., Mossberg, M., Bosmans, E., Triest, L.: Iterative feedback tuning of PID parameters: comparison with classical tuning rules. Control Eng. Pract. 11(9), 1023–1033 (2003). https://doi.org/10.1016/S0967-0661(02)00303-9CrossRef

42.

Mayo, A.J., Antoulas, A.C.: A framework for the solution of the generalized realization problem. Linear Algebra Appl. 425(2–3), 634–662 (2007). https://doi.org/10.1016/j.laa.2007.03.008. Special issue in honor of P. A. Fuhrmann, Edited by A. C. Antoulas, U. Helmke, J. Rosenthal, V. Vinnikov, and E. Zerz

43.

MOSEK ApS: The MOSEK optimization toolbox for MATLAB manual. Version 9.1.9 (2019). https://docs.mosek.com/9.1/toolbox/index.html

44.

Peherstorfer, B.: Multifidelity Monte Carlo estimation with adaptive low-fidelity models. SIAM/ASA J. Uncertainty Quantification 7(2), 579–603 (2019). https://doi.org/10.1137/17M1159208MathSciNetCrossRef

45.

Peherstorfer, B.: Sampling low-dimensional Markovian dynamics for preasymptotically recovering reduced models from data with operator inference. SIAM J. Sci. Comput. 42(5), A3489–A3515 (2020). https://doi.org/10.1137/19M1292448MathSciNetCrossRef

46.

Peherstorfer, B., Gugercin, S., Willcox, K.: Data-driven reduced model construction with time-domain Loewner models. SIAM J. Sci. Comput. 39(5), A2152–A2178 (2017). https://doi.org/10.1137/16M1094750MathSciNetCrossRef

47.

Peherstorfer, B., Willcox, K.: Data-driven operator inference for nonintrusive projection-based model reduction. Comput. Methods Appl. Mech. Eng. 306, 196–215 (2016). https://doi.org/10.1016/j.cma.2016.03.025MathSciNetCrossRef

48.

Quarteroni, A., Rozza, G.: Reduced Order Methods for Modeling and Computational Reduction, MS &A – Modeling, Simulation and Applications, vol. 9. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-02090-7

49.

Rosenbrock, H.H.: State-space and Multivariable Theory, Studies in dynamical systems, vol. 3. Wiley, New York (1970)

50.

Safonov, M.G., Tsao, T.C.: The unfalsified control concept: A direct path from experiment to controller. In: B.A. Francis, A.R. Tannenbaum (eds.) Feedback Control, Nonlinear Systems, and Complexity, Lect. Notes Control Inf. Sci., vol. 202, pp. 196–214. Springer, Berlin, Heidelberg (1995). https://doi.org/10.1007/BFb0027678

51.

Schaeffer, H., Caflisch, R., Hauck, C.D., Osher, S.: Sparse dynamics for partial differential equations. Proc. Natl. Acad. Sci. U. S. A. 110(17), 6634–6639 (2013). https://doi.org/10.1073/pnas.1302752110MathSciNetCrossRef

52.

Schaeffer, H., Tran, G., Ward, R.: Extracting sparse high-dimensional dynamics from limited data. SIAM J. Appl. Math. 78(6), 3279–3295 (2018). https://doi.org/10.1137/18M116798XMathSciNetCrossRef

53.

Schmid, P.J.: Dynamic mode decomposition of numerical and experimental data. J. Fluid Mech. 656, 5–28 (2010). https://doi.org/10.1017/S0022112010001217MathSciNetCrossRef

54.

Schulze, P., Unger, B.: Data-driven interpolation of dynamical systems with delay. Syst. Control Lett. 97, 125–131 (2016). https://doi.org/10.1016/j.sysconle.2016.09.007MathSciNetCrossRef

55.

Schulze, P., Unger, B., Beattie, C., Gugercin, S.: Data-driven structured realization. Linear Algebra Appl. 537, 250–286 (2018). https://doi.org/10.1016/j.laa.2017.09.030MathSciNetCrossRef

56.

Sturm, J.F.: Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones. Optim. Methods Softw. 11(1–4), 625–653 (1999). https://doi.org/10.1080/10556789908805766

57.

Tu, J.H., Rowley, C.W., Luchtenburg, D.M., Brunton, S.L., Kutz, J.N.: On dynamic mode decomposition: Theory and applications. J. Comput. Dyn. 1(2), 391–421 (2014). https://doi.org/10.3934/jcd.2014.1.391MathSciNetCrossRef

58.

Tu, S., Boczar, R., Packard, A., Recht, B.: Non-asymptotic analysis of robust control from coarse-grained identification. e-print 1707.04791, arXiv (2017). https://doi.org/10.48550/arXiv.1707.04791. Optimization and Control (math.OC)

59.

Van Overschee, P., De Moor, B.: Subspace Identification for Linear Systems: Theory, Implementation, Applications. Springer, Boston, MA (1996). https://doi.org/10.1007/978-1-4613-0465-4

60.

Van Waarde, H.J., Eising, J., Trentelman, H.L., Camlibel, M.K.: Data informativity: A new perspective on data-driven analysis and control. IEEE Trans. Autom. Control 65(11), 4753–4768 (2020). https://doi.org/10.1109/TAC.2020.2966717MathSciNetCrossRef

61.

Voigt, M.: On linear-quadratic optimal control and robustness of differential-algebraic systems. Dissertation, Otto-von-Guericke-Universität, Magdeburg, Germany (2015)

62.

Werner, S.W.R.: Code, data and results for numerical experiments in “On the sample complexity of stabilizing linear dynamical systems from data” (version 1.0) (2022). https://doi.org/10.5281/zenodo.5902997

63.

Willems, J.C., Rapisarda, P., Markovsky, I., De Moor, B.L.M.: A note on persistency of excitation. Syst. Control Lett. 54(4), 325–329 (2005). https://doi.org/10.1016/j.sysconle.2004.09.003MathSciNetCrossRef

64.

Ziegler, J., Nichols, N.: Optimum settings for automatic controllers. Trans. ASME 64, 759–768 (1942)

Title: On the Sample Complexity of Stabilizing Linear Dynamical Systems from Data
Authors: Steffen W. R. Werner
Benjamin Peherstorfer
Publication date: 23-01-2023
Publisher: Springer US
Published in: Foundations of Computational Mathematics / Issue 3/2024
Print ISSN: 1615-3375
Electronic ISSN: 1615-3383
DOI: https://doi.org/10.1007/s10208-023-09605-y

A Stirling-Type Formula for the Distribution of the Length of Longest Increasing Subsequences

Open Access

On the Computation of Geometric Features of Spectra of Linear Operators on Hilbert Spaces

Open Access

Open Access

Correction to: Conormal Spaces and Whitney Stratifications

Open Access
Correction

Springer Professional

On the Sample Complexity of Stabilizing Linear Dynamical Systems from Data

Abstract

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 3/2024

A Stirling-Type Formula for the Distribution of the Length of Longest Increasing Subsequences

On the Computation of Geometric Features of Spectra of Linear Operators on Hilbert Spaces

Nodal Auxiliary Space Preconditioning for the Surface de Rham Complex

Optimal Polynomial Meshes Exist on any Multivariate Convex Domain

A New Approach to Handle Curved Meshes in the Hybrid High-Order Method

Correction to: Conormal Spaces and Whitney Stratifications

Premium Partner

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

A Stirling-Type Formula for the Distribution of the Length of Longest Increasing Subsequences

On the Computation of Geometric Features of Spectra of Linear Operators on Hilbert Spaces

Nodal Auxiliary Space Preconditioning for the Surface de Rham Complex

Optimal Polynomial Meshes Exist on any Multivariate Convex Domain

A New Approach to Handle Curved Meshes in the Hybrid High-Order Method

Correction to: Conormal Spaces and Whitney Stratifications