Open Journal of Mathematical Optimization

Tight computationally efficient approximation of matrix norms with applications
Anatoli Juditsky1; Georgios Kotsalis2; Arkadi Nemirovski2
1 LJK, Université Grenoble Alpes, 700 Avenue Centrale 38401 Domaine Universitaire de Saint-Martin-d’Hères, France
2 Georgia Institute of Technology, Atlanta, Georgia 30332, USA
Open Journal of Mathematical Optimization, Volume 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 ≤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.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/ojmo.19
Keywords: matrix norms, uncertain matrices, robust control, system identification
Anatoli Juditsky 1; Georgios Kotsalis 2; Arkadi Nemirovski 2

1 LJK, Université Grenoble Alpes, 700 Avenue Centrale 38401 Domaine Universitaire de Saint-Martin-d’Hères, France
2 Georgia Institute of Technology, Atlanta, Georgia 30332, USA
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{OJMO_2022__3__A7_0,
     author = {Anatoli Juditsky and Georgios Kotsalis and Arkadi Nemirovski},
     title = {Tight computationally efficient approximation of matrix norms with applications},
     journal = {Open Journal of Mathematical Optimization},
     eid = {7},
     pages = {1--38},
     publisher = {Universit\'e de Montpellier},
     volume = {3},
     year = {2022},
     doi = {10.5802/ojmo.19},
     language = {en},
     url = {https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.19/}
}
TY  - JOUR
AU  - Anatoli Juditsky
AU  - Georgios Kotsalis
AU  - Arkadi Nemirovski
TI  - Tight computationally efficient approximation of matrix norms with applications
JO  - Open Journal of Mathematical Optimization
PY  - 2022
SP  - 1
EP  - 38
VL  - 3
PB  - Université de Montpellier
UR  - https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.19/
DO  - 10.5802/ojmo.19
LA  - en
ID  - OJMO_2022__3__A7_0
ER  - 
%0 Journal Article
%A Anatoli Juditsky
%A Georgios Kotsalis
%A Arkadi Nemirovski
%T Tight computationally efficient approximation of matrix norms with applications
%J Open Journal of Mathematical Optimization
%D 2022
%P 1-38
%V 3
%I Université de Montpellier
%U https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.19/
%R 10.5802/ojmo.19
%G en
%F OJMO_2022__3__A7_0
Anatoli Juditsky; Georgios Kotsalis; Arkadi Nemirovski. Tight computationally efficient approximation of matrix norms with applications. Open Journal of Mathematical Optimization, Volume 3 (2022), article  no. 7, 38 p. doi : 10.5802/ojmo.19. https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.19/

[1] John Abedor; Krishan Nagpal; Kameshwar Poolla 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] Erling D. Anderson The MOSEK optimization toolbox for MATLAB manual. Version 8.0 (2015) (https://docs.mosek.com/latest/toolbox/index.html)

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

[4] Johannes Aubrecht; Petros G. Voulgaris 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] Venkataramanan Balakrishnan; Stephen Boyd 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] Aharon Ben-Tal; Arkadi Nemirovski Lectures on modern convex optimization: analysis, algorithms, and engineering applications, Society for Industrial and Applied Mathematics, 2001 | DOI

[7] Aharon Ben-Tal; Arkadi Nemirovski 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] Dimetri Bertsekas; Ian Rhodes 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] Stephen Boyd EE263 Lecture Notes, 2007 (https://web.stanford.edu/class/archive/ee/ee263/ee263.1082/lectures/aircraft2.pdf)

[10] Stephen Boyd; John Doyle 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] Juanyu Bu; Mario Sznaier A linear matrix inequality approach to synthesizing low-order suboptimal mixed ℓ 1 /H p controllers, Automatica, Volume 36 (2000) no. 7, pp. 957-963 | MR

[12] Marco Casini; Andrea Garulli; Antonio Vicino 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] Vito Cerone Feasible parameter set for linear models with bounded errors in all variables, Automatica, Volume 29 (1993) no. 6, pp. 1551-1555 | DOI | Zbl

[14] J. E. Cope; Bert W. Rust 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] Ignacio J. Diaz-Bobillo; Munther A. Dahleh 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] Pieter Eykhoff Trends and progress in system identification: IFAC Series for Graduates, Research Workers & Practising Engineers, Pergamon Press, 1981

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

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

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

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

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

[22] Georgios Kotsalis; Guanghui Lan; Arkadi Nemirovski 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] Vladik Kreinovich; Anatoly V. Lakeyev; Sergey I. Noskov Optimal solution of interval linear systems is intractable (NP-hard), Interval Comput., Volume 1 (1993), pp. 6-14 | Zbl

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

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

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

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

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

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

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

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

[32] Sergey A. Nazin; Boris T. Polyak 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] Arkadi Nemirovski; Cornelis Roos; Tamás Terlaky 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] Yurii Nesterov Semidefinite relaxation and nonconvex quadratic optimization, Optim. Methods Softw., Volume 9 (1998) no. 1-3, pp. 141-160 | DOI | MR | Zbl

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

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

[37] Werner Oettli; William Prager 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] Boris T. Polyak Robust linear algebra and robust aperiodicity, Directions in Mathematical Systems Theory and Optimization (A. Rantzer; C. Byrnes, eds.), Springer, 2003, pp. 249-260 | DOI | MR | Zbl

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

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

[41] Daureen Steinberg 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] Joel A. Tropp An introduction to matrix concentration inequalities, Found. Trends Mach. Learn., Volume 8 (2015) no. 1-2, pp. 1-230 | DOI | Zbl

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

Cited by Sources: