Tight computationally efficient approximation of matrix norms with applications
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...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Université de Montpellier
2022-11-01
|
| Series: | Open Journal of Mathematical Optimization |
| Subjects: | |
| Online Access: | https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.19/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1825204938456694784 |
|---|---|
| author | Juditsky, Anatoli Kotsalis, Georgios Nemirovski, Arkadi |
| author_facet | Juditsky, Anatoli Kotsalis, Georgios Nemirovski, Arkadi |
| author_sort | Juditsky, Anatoli |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-2461c5f817714b6c981e84db44dad4ba |
| institution | Kabale University |
| issn | 2777-5860 |
| language | English |
| publishDate | 2022-11-01 |
| publisher | Université de Montpellier |
| record_format | Article |
| series | Open Journal of Mathematical Optimization |
| spelling | doaj-art-2461c5f817714b6c981e84db44dad4ba2025-02-07T14:02:43ZengUniversité de MontpellierOpen Journal of Mathematical Optimization2777-58602022-11-01313810.5802/ojmo.1910.5802/ojmo.19Tight computationally efficient approximation of matrix norms with applicationsJuditsky, Anatoli0Kotsalis, Georgios1Nemirovski, Arkadi2LJK, Université Grenoble Alpes, 700 Avenue Centrale 38401 Domaine Universitaire de Saint-Martin-d’Hères, FranceGeorgia Institute of Technology, Atlanta, Georgia 30332, USAGeorgia Institute of Technology, Atlanta, Georgia 30332, USAWe 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.https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.19/matrix normsuncertain matricesrobust controlsystem identification |
| spellingShingle | Juditsky, Anatoli Kotsalis, Georgios Nemirovski, Arkadi Tight computationally efficient approximation of matrix norms with applications Open Journal of Mathematical Optimization matrix norms uncertain matrices robust control system identification |
| title | Tight computationally efficient approximation of matrix norms with applications |
| title_full | Tight computationally efficient approximation of matrix norms with applications |
| title_fullStr | Tight computationally efficient approximation of matrix norms with applications |
| title_full_unstemmed | Tight computationally efficient approximation of matrix norms with applications |
| title_short | Tight computationally efficient approximation of matrix norms with applications |
| title_sort | tight computationally efficient approximation of matrix norms with applications |
| topic | matrix norms uncertain matrices robust control system identification |
| url | https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.19/ |
| work_keys_str_mv | AT juditskyanatoli tightcomputationallyefficientapproximationofmatrixnormswithapplications AT kotsalisgeorgios tightcomputationallyefficientapproximationofmatrixnormswithapplications AT nemirovskiarkadi tightcomputationallyefficientapproximationofmatrixnormswithapplications |