The generalized matrix norm problem

DOI10.1137/23M1605545MaRDI QIDQ6902506zbMATH OpenFDO

Publication date 11 November 2025

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/23M1605545

approximation operator norm pull-back norm push-forward norm

Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60) Norms (inequalities, more than one norm, etc.) of linear operators (47A30) Perturbation theory of linear operators (47A55) Numerical computation of matrix norms, conditioning, scaling (65F35) Analysis of algorithms and problem complexity (68Q25)

Review text

The author studies the computability and approximability of the operator norm of a matrix \(A\) with respect to norms induced by linear operators \(B\). The generalized matrix \(p \mapsto q; B\)-norm of \(A\) is defined as\N\[\N\|A\|_{p \mapsto q; B} := \max_{\|Bv\|_p \le 1} \|Av\|_q,\N\]\Nwhere \(\|x\|_p\) and \(\|x\|_q\) are \(p\) and \(q\)-norms, respectively and \(B\) is a matrix. To compute the generalized matrix \(p \mapsto q\); \(B\)-norm, the author considers the concepts of \textit{push-forward} and \textit{pull-back} of seminorms on a normed space induced by a linear operator. Then the dual of these seminorms are considered. The problem is found to be solvable in polynomial time (tractable) when \(p=q=2\) and \(B\) is injective. For many other cases, the problem is NP-hard (e.g., when \(1 < q \le 2 \le p < \infty\)), leading the study toward approximation methods. The paper introduces two main approximation strategies: \(1 \le q \le 2 \le p < \infty\), and \(q=1\) and \(p \in [1, 2)\).

Cites work

This page was built for publication: The generalized matrix norm problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6902506)