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 , 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.
Revised:
Accepted:
Published online:
@article{OJMO_2022__3__A7_0, author = {Juditsky, Anatoli and Kotsalis, Georgios and Nemirovski, Arkadi}, 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 = {http://www.numdam.org/articles/10.5802/ojmo.19/} }
TY - JOUR AU - Juditsky, Anatoli AU - Kotsalis, Georgios AU - Nemirovski, Arkadi 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 - http://www.numdam.org/articles/10.5802/ojmo.19/ DO - 10.5802/ojmo.19 LA - en ID - OJMO_2022__3__A7_0 ER -
%0 Journal Article %A Juditsky, Anatoli %A Kotsalis, Georgios %A Nemirovski, Arkadi %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 http://www.numdam.org/articles/10.5802/ojmo.19/ %R 10.5802/ojmo.19 %G en %F OJMO_2022__3__A7_0
Juditsky, Anatoli; Kotsalis, Georgios; Nemirovski, Arkadi. 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. http://www.numdam.org/articles/10.5802/ojmo.19/
[1] 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] The MOSEK optimization toolbox for MATLAB manual. Version 8.0 (2015) (https://docs.mosek.com/latest/toolbox/index.html)
[3] System identification-a survey, Automatica, Volume 7 (1971) no. 2, pp. 123-162 | DOI | MR
[4] 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] 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] Lectures on modern convex optimization: analysis, algorithms, and engineering applications, Society for Industrial and Applied Mathematics, 2001 | DOI
[7] 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] 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] EE263 Lecture Notes, 2007 (https://web.stanford.edu/class/archive/ee/ee263/ee263.1082/lectures/aircraft2.pdf)
[10] 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] A linear matrix inequality approach to synthesizing low-order suboptimal mixed controllers, Automatica, Volume 36 (2000) no. 7, pp. 957-963 | MR
[12] 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] Feasible parameter set for linear models with bounded errors in all variables, Automatica, Volume 29 (1993) no. 6, pp. 1551-1555 | DOI | Zbl
[14] 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] 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] Trends and progress in system identification: IFAC Series for Graduates, Research Workers & Practising Engineers, Pergamon Press, 1981
[17] The CVX Users Guide. Release 2.1 (2014) (http://web.cvxr.com/cvx/doc/)
[18] Accuracy and stability of numerical algorithms, Society for Industrial and Applied Mathematics, 2002 | DOI
[19] Interval analysis, Applied interval analysis, Springer, 2001, pp. 11-43 | DOI | Zbl
[20] Near-optimality of linear recovery from indirect observations, Math. Stat. Learn., Volume 1 (2018) no. 2, pp. 101-110 | MR | Zbl
[21] Statistical Inference via Convex Optimization, Princeton University Press, 2020
[22] 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] Optimal solution of interval linear systems is intractable (NP-hard), Interval Comput., Volume 1 (1993), pp. 6-14 | Zbl
[24] Control and observation under uncertainty, Nauka, 1977 | Zbl
[25] Identification problem-theory of guaranteed estimates, Automation and Remote Control, Volume 52 (1991) no. 4, pp. 447-465 | MR
[26] Ellipsoidal calculus for estimation and control, Systems and Control: Foundations and Applications, Birkhäuser, 1997 | DOI
[27] System identification: Theory for the user, Prentice Hall, 1997
[28] Estimators for uncertain dynamic systems, 458, Springer, 1998 | DOI
[29] System identification advances and case studies, Academic Press Inc., 1977
[30] Bounding approaches to system identification, Springer, 2013
[31] Interval parameter estimation under model uncertainty, Math. Comput. Model. Dyn. Syst., Volume 11 (2005) no. 2, pp. 225-237 | DOI | MR | Zbl
[32] 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] 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] Semidefinite relaxation and nonconvex quadratic optimization, Optim. Methods Softw., Volume 9 (1998) no. 1-3, pp. 141-160 | DOI | MR | Zbl
[35] 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] Interval methods for systems of equations, Cambridge University Press, 1990 no. 37
[37] 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] 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] Uncertain dynamic systems, Prentice Hall, 1973
[40] System identification, Pearson Education Ltd, 1994
[41] 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] An introduction to matrix concentration inequalities, Found. Trends Mach. Learn., Volume 8 (2015) no. 1-2, pp. 1-230 | DOI | Zbl
[43] Special issue on parameter identification with error bounds, Math. Comput. Simul., Volume 32 (1990) no. 447, p. 607
Cited by Sources: