The generalized matrix norm problem (Q6902506)

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)\).