Abstract
Kolmogorov n-widths and Hankel singular values are two commonly used concepts in model reduction. Here, we show that for the special case of linear time-invariant (LTI) dynamical systems, these two concepts are directly connected. More specifically, the greedy search applied to the Hankel operator of an LTI system resembles the minimizing subspace for the Kolmogorov n-width and the Kolmogorov n-width of an LTI system equals its (n + 1)st Hankel singular value once the subspaces are appropriately defined. We also establish a lower bound for the Kolmorogov n-width for parametric LTI systems and illustrate that the method of active subspaces can be viewed as the dual concept to the minimizing subspace for the Kolmogorov n-width.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Adamjan, V., Arov, D., Krein, M.: Analytic properties of Schmidt pairs for a Hankel operator and the generalized schur-Takagi problem. Math. USSR-Sbornik 15(1), 31–73 (1971). https://doi.org/10.1070/SM1971v015n01ABEH001531
Antoulas, A.C.: Approximation of large-scale dynamical systems. Advances in Design and Control. Society for Industrial and Applied Mathematics, Philadelphia. https://doi.org/10.1137/1.9780898718713 (2005)
Baur, U., Benner, P., Feng, L.: Model order reduction for linear and nonlinear systems: a system-theoretic perspective. Arch. Comput. Methods Eng. 21(4), 331–358 (2014). https://doi.org/10.1007/s11831-014-9111-2
Benner, P., Cohen, A., Ohlberger, M., Willcox, K.: Model Reduction and Approximation. SIAM, Philadelphia (2017). https://doi.org/10.1137/1.9781611974829
Benner, P., Gugercin, S., Willcox, K.: A survey of projection-based model reduction methods for parametric dynamical systems. SIAM Review 57(4), 483–531 (2015). https://doi.org/10.1137/130932715
Binev, P., Cohen, A., Dahmen, W., DeVore, R., Petrova, G., Wojtaszczyk, P.: Convergence rates for greedy algorithms in the reduced basis method. SIAM J. Math. Anal. 43, 1457–1472 (2011). https://doi.org/10.1137/100795772
Bui-Thanh, T., Willcox, K., Ghattas, O.: Model reduction for large-scale systems with high-dimensional parametric input space. SIAM J. Sci. Comput. 30 (6), 3270–3288 (2008). https://doi.org/10.1137/070694855
Cagniart, N., Maday, Y., Stamm, B.: Model Order Reduction for Problems with Large Convection Effects, pp. 131–150. Springer International Publishing, Cham (2019). https://doi.org/10.1007/978-3-319-78325-3
Chinesta, F., Huerta, A., Rozza, G., Willcox, K.: Model order reduction: a survey. Wiley Encyclopedia of Computational Mechanics (2016)
Constantine, P.G.: Active subspaces: Emerging ideas for dimension reduction in parameter studies. SIAM spotlights society for industrial and applied mathematics. https://doi.org/10.1137/1.9781611973860 (2015)
Curtain, R.F., Zwart, H.: An Introduction to Infinite-Dimensional Linear Systems Theory. Texts in Applied Mathematics. Springer , New York (1995). https://doi.org/10.1007/978-1-4612-4224-6
Djouadi, S.M.: On the optimality of the proper orthogonal decomposition and balanced truncation. Proc. IEEE Conf. Decis. Control (3): 4221–4226 (2008). https://doi.org/10.1109/CDC.2008.4739458
Djouadi, S.M.: On the connection between balanced proper orthogonal decomposition, balanced truncation, and metric complexity theory for infinite dimensional systems. In: Am. Control Conf, pp. 4911–4916 (2010). https://doi.org/10.1109/ACC.2010.5530920
Francis, B.A.: A Course in H ∞ Control Theory. Lecture Notes in Control and Information Sciences. Springer, Berlin (1987). https://doi.org/10.1007/BFb0007371
Fujimoto, K., Scherpen, J.M.A.: Balanced realization and model order reduction for nonlinear systems based on singular value analysis. SIAM J. Control Optim. 48 (7), 4591–4623 (2010). https://doi.org/10.1137/070695332
Glover, K.: All optimal Hankel-norm approximations of linear multivariable systems and their L ∞-error bounds. Int. J. Control 39(6), 1115–1193 (1984). https://doi.org/10.1080/00207178408933239
Grepl, M., Patera, A.: A posteriori error bounds for reduced-basis approximations of parametrized parabolic partial differential equations. ESAIM-Mathematical Modelling and Numerical Analysis (M2AN) 39(1), 157–181 (2005). https://doi.org/10.1051/m2an:2005006
Haasdonk, B.: Convergence rates of the POD–greedy method. ESAIM: Mathematical Modelling and Numerical Analysis 47(3), 859–873 (2013). https://doi.org/10.1051/m2an/2012045
Haasdonk, B., Ohlberger, M.: Reduced basis method for finite volume approximations of parametrized linear evolution equations. ESAIM: Mathematical Modelling and Numerical Analysis 42(2), 277–302 (2008). https://doi.org/10.1051/m2an:2008001
Hesthaven, J.S., Rozza, G., Stamm, B.: Certified Reduced Basis Methods for Parametrized Partial Differential Equations. Springer Briefs in Mathematics. Springer, Switzerland (2016). https://doi.org/10.1186/2190-5983-1-3
Kolmogorov, A.: ÜBer die beste Annäherung von Funktionen einer gegebenen Funktionenklasse. Ann. Math. 37(1), 107–110 (1936). https://doi.org/10.2307/1968691
Lassila, T., Manzoni, A., Quarteroni, A., Rozza, G. Quarteroni, A., Rozza, G. (eds.): Model Order Reduction in Fluid Dynamics: Challenges and Perspectives. Springer International Publishing, Cham (2014)
Maday, Y., Patera, A.T., Turinici, G.: Global a priori convergence theory for reduced-basis approximations of single-parameter symmetric coercive elliptic partial differential equations. Comptes Rendus Mathematique 335(3), 289–294 (2002). https://doi.org/10.1016/S1631-073X(02)02466-4
Maday, Y., Patera, A.T., Turinici, G.: A priori convergence theory for reduced-basis approximations of single-parameter elliptic partial differential equations. J. Sci. Comput. 17(1), 437–446 (2002). https://doi.org/10.1023/A:1015145924517
Pinkus, A.: N-Widths in Approximation Theory. Ergebnisse der Mathematik und ihrer Grenzgebiete. Springer, Berlin (1985). https://doi.org/10.1007/978-3-642-69894-1
Prud’homme, C., Rovas, D., Veroy, K., Maday, Y., Patera, A., Turinici, G.: Reliable real-time solution of parameterized partial differential equations: Reduced-basis output bound methods. J. Fluids Eng. 124, 70–80 (2002). https://doi.org/10.1115/1.1448332
Quarteroni, A., Manzoni, A., Negri, F.: Reduced Basis Methods for Partial Differential Equations: an Introduction. UNITEXT. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-15431-2
Quarteroni, A., Rozza, G., Manzoni, A.: Certified reduced basis approximation for parametrized partial differential equations and applications. J. Math. Ind. 1(1), 3 (2011). https://doi.org/10.1186/2190-5983-1-3
Reed, M., Simon, B.: Analysis of Operators. Methods of Modern Mathematical Physics. Academic Press, Cambridge (1978)
Wittmuess, P., Tarin, C., Keck, A., Arnold, E., Sawodny, O.: Parametric model order reduction via balanced truncation with taylor series representation. IEEE Trans. Automat. Contr. 61(11), 3438–3451 (2016). https://doi.org/10.1109/TAC.2016.2521361
Acknowledgments
We thank Profs. Christopher Beattie, Volker Mehrmann, and Karen Willcox for their valuable comments.
Funding
The work of the first author was funded by the DFG Collaborative Research Center 910 Control of self-organizing nonlinear systems: theoretical methods and concepts of application. The work of the second author was financially supported in parts by NSF through Grant DMS-1720257 and by the Alexander von Humboldt Foundation.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by: Anthony Nouy
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Unger, B., Gugercin, S. Kolmogorov n-widths for linear dynamical systems. Adv Comput Math 45, 2273–2286 (2019). https://doi.org/10.1007/s10444-019-09701-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10444-019-09701-0
Keywords
- Model reduction
- Hankel singular values
- Kolmogorov n-width
- Hankel operator
- Reduced basis method
- Active subspaces