# Tight Computationally Efficient Approximation of Matrix Norms with Applications

arXiv: https://arxiv.org/abs/2110.04389 · HTML: https://mlsanity.com/paper/2110.04389/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Oct 2021.

## Built on by (most cited first, 1 of 1)

- [On robust recovery of signals from indirect observations](https://mlsanity.com/paper/2501.01935/) (2025)

## Abstract (arXiv)

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.