Tight computationally efficient approximation of matrix norms with applications

Juditsky, Anatoli; Kotsalis, Georgios; Nemirovski, Arkadi

Open Journal of Mathematical Optimization, Tome 3 (2022), article no. 7, 38 p.

We address the problems of computing operator norms of matrices induced by given norms on the argument and the image space. It is known that aside of a fistful of “solvable cases”, most notably, the case when both given norms are Euclidean, computing operator norm of a matrix is NP-hard. We specify rather general families of norms on the argument and the images space (“ellitopic” and “co-ellitopic”, respectively) allowing for reasonably tight computationally efficient upper-bounding of the associated operator norms. We extend these results to bounding “robust operator norm of uncertain matrix with box uncertainty”, that is, the maximum of operator norms of matrices representable as a linear combination, with coefficients of magnitude $\le 1$, of a collection of given matrices. Finally, we consider some applications of norm bounding, in particular, (1) computationally efficient synthesis of affine non-anticipative finite-horizon control of discrete time linear dynamical systems under bounds on the peak-to-peak gains, (2) signal recovery with uncertainties in sensing matrix, and (3) identification of parameters of time invariant discrete time linear dynamical systems via noisy observations of states and inputs on a given time horizon, in the case of “uncertain-but-bounded” noise varying in a box.

Mots clés : matrix norms, uncertain matrices, robust control, system identification

[1] Abedor, John; Nagpal, Krishan; Poolla, Kameshwar A linear matrix inequality approach to peak-to-peak gain minimization, Int. J. Robust Nonlinear Control, Volume 6 (1996) no. 9-10, pp. 899-927 | DOI | MR | Zbl

[2] Anderson, Erling D. The MOSEK optimization toolbox for MATLAB manual. Version 8.0 (2015) (https://docs.mosek.com/latest/toolbox/index.html)

[3] Åström, Karl Johan; Eykhoff, Pieter System identification-a survey, Automatica, Volume 7 (1971) no. 2, pp. 123-162 | DOI | MR

[4] Aubrecht, Johannes; Voulgaris, Petros G. Minimization of the peak-to-peak gain in periodic systems under full state feedback, J. Dyn. Syst. Meas. Control, Volume 123 (2001) no. 1, pp. 10-20 | DOI

[5] Balakrishnan, Venkataramanan; Boyd, Stephen On computing the worst-case peak gain of linear systems, Syst. Control Lett., Volume 19 (1992) no. 4, pp. 265-269 | DOI | MR | Zbl

[6] Ben-Tal, Aharon; Nemirovski, Arkadi Lectures on modern convex optimization: analysis, algorithms, and engineering applications, Society for Industrial and Applied Mathematics, 2001 | DOI

[7] Ben-Tal, Aharon; Nemirovski, Arkadi On tractable approximations of uncertain linear matrix inequalities affected by interval uncertainty, SIAM J. Optim., Volume 12 (2002) no. 3, pp. 811-833 | DOI | MR | Zbl

[8] Bertsekas, Dimetri; Rhodes, Ian Recursive state estimation for a set-membership description of uncertainty, IEEE Trans. Autom. Control, Volume 16 (1971) no. 2, pp. 117-128 | DOI | MR

[9] Boyd, Stephen EE263 Lecture Notes, 2007 (https://web.stanford.edu/class/archive/ee/ee263/ee263.1082/lectures/aircraft2.pdf)

[10] Boyd, Stephen; Doyle, John Comparison of peak and RMS gains for discrete-time systems, Syst. Control Lett., Volume 9 (1987) no. 1, pp. 1-6 | DOI | MR | Zbl

[11] Bu, Juanyu; Sznaier, Mario A linear matrix inequality approach to synthesizing low-order suboptimal mixed ${\ell }_1/H_p$ controllers, Automatica, Volume 36 (2000) no. 7, pp. 957-963 | MR

[12] Casini, Marco; Garulli, Andrea; Vicino, Antonio Feasible parameter set approximation for linear models with bounded uncertain regressors, IEEE Trans. Autom. Control, Volume 59 (2014) no. 11, pp. 2910-2920 | DOI | MR | Zbl

[13] Cerone, Vito Feasible parameter set for linear models with bounded errors in all variables, Automatica, Volume 29 (1993) no. 6, pp. 1551-1555 | DOI | Zbl

[14] Cope, J. E.; Rust, Bert W. Bounds on solutions of linear systems with inaccurate data, SIAM J. Numer. Anal., Volume 16 (1979) no. 6, pp. 950-963 | DOI | MR | Zbl

[15] Diaz-Bobillo, Ignacio J.; Dahleh, Munther A. Minimization of the maximum peak-to-peak gain: The general multiblock problem, IEEE Trans. Autom. Control, Volume 38 (1993) no. 10, pp. 1459-1482 | DOI | MR | Zbl

[16] Eykhoff, Pieter Trends and progress in system identification: IFAC Series for Graduates, Research Workers & Practising Engineers, Pergamon Press, 1981

[17] Grant, Michael; Boyd, Stephen The CVX Users Guide. Release 2.1 (2014) (http://web.cvxr.com/cvx/doc/)

[18] Higham, Nicholas J Accuracy and stability of numerical algorithms, Society for Industrial and Applied Mathematics, 2002 | DOI

[19] Jaulin, Luc; Kieffer, Michel; Didrit, Olivier; Walter, Éric Interval analysis, Applied interval analysis, Springer, 2001, pp. 11-43 | DOI | Zbl

[20] Juditsky, Anatoli; Nemirovski, Arkadi Near-optimality of linear recovery from indirect observations, Math. Stat. Learn., Volume 1 (2018) no. 2, pp. 101-110 | MR | Zbl

[21] Juditsky, Anatoli; Nemirovski, Arkadi Statistical Inference via Convex Optimization, Princeton University Press, 2020

[22] Kotsalis, Georgios; Lan, Guanghui; Nemirovski, Arkadi Convex Optimization for Finite-Horizon Robust Covariance Control of Linear Stochastic Systems, SIAM J. Control Optim., Volume 59 (2021) no. 1, pp. 296-319 | DOI | MR | Zbl

[23] Kreinovich, Vladik; Lakeyev, Anatoly V.; Noskov, Sergey I. Optimal solution of interval linear systems is intractable (NP-hard), Interval Comput., Volume 1 (1993), pp. 6-14 | Zbl

[24] Kurzhanskiĭ, Aleksandr B. Control and observation under uncertainty, Nauka, 1977 | Zbl

[25] Kurzhanskiĭ, Aleksandr B. Identification problem-theory of guaranteed estimates, Automation and Remote Control, Volume 52 (1991) no. 4, pp. 447-465 | MR

[26] Kurzhanskiĭ, Aleksandr B.; Vályi, István Ellipsoidal calculus for estimation and control, Systems and Control: Foundations and Applications, Birkhäuser, 1997 | DOI

[27] Ljung, Lennart System identification: Theory for the user, Prentice Hall, 1997

[28] Matasov, Aleksandr Ivanovič Estimators for uncertain dynamic systems, 458, Springer, 1998 | DOI

[29] Mehra, Raman K.; Lainiotis, Dimitri G. System identification advances and case studies, Academic Press Inc., 1977

[30] Milanese, Mario; Norton, John; Piet-Lahanier, Hélène; Walter, Éric Bounding approaches to system identification, Springer, 2013

[31] Nazin, Sergey A.; Polyak, Boris T. Interval parameter estimation under model uncertainty, Math. Comput. Model. Dyn. Syst., Volume 11 (2005) no. 2, pp. 225-237 | DOI | MR | Zbl

[32] Nazin, Sergey A.; Polyak, Boris T. Ellipsoid-based parametric estimation in the linear multidimensional systems with uncertain model description, Automation and Remote Control, Volume 68 (2007) no. 6, pp. 993-1005 | DOI | Zbl

[33] Nemirovski, Arkadi; Roos, Cornelis; Terlaky, Tamás On maximization of quadratic form over intersection of ellipsoids with common center, Math. Program., Volume 86 (1999) no. 3, pp. 463-473 | DOI | MR | Zbl

[34] Nesterov, Yurii Semidefinite relaxation and nonconvex quadratic optimization, Optim. Methods Softw., Volume 9 (1998) no. 1-3, pp. 141-160 | DOI | MR | Zbl

[35] Nesterov, Yurii Global quadratic optimization via conic relaxation, Handbook on Semidefinite Programming (Saigal, R; Wolkowicz, H; Vandenberghe, L, eds.), Kluwer Academic Publishers, 2000, pp. 363-387

[36] Neumaier, Arnold; Neumaier, Arnold Interval methods for systems of equations, Cambridge University Press, 1990 no. 37

[37] Oettli, Werner; Prager, William Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides, Numer. Math., Volume 6 (1964) no. 1, pp. 405-409 | DOI | MR | Zbl

[38] Polyak, Boris T. Robust linear algebra and robust aperiodicity, Directions in Mathematical Systems Theory and Optimization (Rantzer, A.; Byrnes, C., eds.), Springer, 2003, pp. 249-260 | DOI | MR | Zbl

[39] Schweppe, Fred C. Uncertain dynamic systems, Prentice Hall, 1973

[40] Söderström, Torsten; Stoica, Petre System identification, Pearson Education Ltd, 1994

[41] Steinberg, Daureen Computation of matrix norms with applications to robust optimization, Masters thesis, M.Sc. thesis in OR and System Analysis, Technion-Israel Institute of Technology (2005) (https://www2.isye.gatech.edu/~nemirovs/Daureen.pdf)

[42] Tropp, Joel A. An introduction to matrix concentration inequalities, Found. Trends Mach. Learn., Volume 8 (2015) no. 1-2, pp. 1-230 | DOI | Zbl

[43] Walter, Éric Special issue on parameter identification with error bounds, Math. Comput. Simul., Volume 32 (1990) no. 447, p. 607