2
$\begingroup$

Is the problem of calculating the induced norm of a linear operator (in a finite or infinite-dimensional space) generally a difficult one ?

And by difficult I mean, that there are no closed formulas or no general procedure that always yields the induced norm.

Of course, for the usual spaces with the usual norms, there are formulas, that makes ones life very, so one can take shortcuts in calculating the induced norm of a operator (instead of trying to use the definition of the induced norm : $ ||A||=\sup_{||x||=1} ||Ax||).$ But is there also a procedure how to calculate $||A||$ for some very weird vector norms, or for some unsual infinitedimensional spaces (since in finite dimensions we can at least use the fact, that every vectors space is isomorphic to $\mathbb{K}^n$ for some $n$) ?

EDIT: I think the user tomasz bst described what I meant. Are there vector norms such that for their induced operator norm it is proven that there isn't a closed expression ?

  • 0
    You need to formulate the notion of 'there isn't a closed expression'. The underlying norm may have no 'closed expression'? I would guess that informally most would say there is no way of computing a general closed expression, but to formalize that may take a bit of work (I'm definitely off-piste here).2012-07-30

2 Answers 2

4

Following on from @tomasz's comment: There are examples of operators whose induced norm is NP-hard to approximate even though the norm in the original vector space can be immediately computed.

Here, we'll work with the real vector space $\ell_p^n$. Consider the problem of computing the norm of a matrix $T: \ell_p^n \to \ell_p^n$, $ \Vert T \Vert_{p \to p} = \sup_{\Vert x \Vert_p =1} \Vert Tx \Vert_p. $ If $p \in \{1, \infty\}$, then the exact value of this norm is easily computed. If $p=2$, then it can be efficiently approximated (where "efficiently" depends on the size $n$ of the problem and the desired accuracy $\varepsilon$). However, this is not true for other values of $p$ even when we insist that the map satisfies the condition $T_{ij} \in \{-1,0,1\}$.

The following theorem is taken from http://arxiv.org/abs/0908.1397 .

Theorem: For any rational $p ∈ [1,\infty)$ except $p = 1,2$, unless P = NP, there is no algorithm which computes the p-norm of a matrix with entries in $\{−1, 0, 1\}$ to relative error $\varepsilon$ with running time polynomial in $n, 1/\varepsilon$ .

In particular, there should be no "nice", "easy" formula in terms of $T_{ij}$ that immediately tells you the value of the induced norm $\Vert T \Vert_{p \to p}$.

1

Consider the linear operator $T : \mathbb{R} \to \mathbb{R}$ which is identically $0$ if the Riemann hypothesis is true and the identity if the Riemann hypothesis is false. What is the operator norm of $T$?

(In general, the question also depends on what you know about $T$.)

  • 0
    Yes, this was facetious. I'm just tryi$n$g to get you to clarify your question.2012-07-31