2
$\begingroup$

Didn't get any biters over at MSE, so I figure this place might be more appropriate...

Say that $V$ is a finite-dimensional real normed vector space, where for some $v \in V$ the norm is notated by $\|v\|$. Then say that $V^*$ is the dual space of linear functionals on $V$.

The "dual norm" $\| \cdot \|^*$ naturally exists on $V^*$, given for some $v^* \in V^*$ by

$\displaystyle\|v^*\|^* = \sup_{v \in V} \left\{ \frac{|\langle v^*, v\rangle|}{\|v\|} \right\} = \sup_{v \in V} \left\{ |\langle v^*, v\rangle| : \|v\| = 1 \right\}$

for $\langle v^*,v \rangle$ the dual pairing between $v^*$ and $v$.

If a basis is chosen for $V$, then is vectors can be represented as $\mathbb{R}$-tuples. Sometimes the original norm on $V$ can be denoted by a closed-form expression on the entries of this tuple. For instance, the $\ell_p$ norm on a vector $(x_1, x_2, ..., x_n)$ is given by $\left(|x_1|^p + |x_2|^p + ... + |x_n|^p\right)^{\frac{1}{p}}$.

In these cases, is there a general algorithm to find a closed-form expression for the dual norm given the dual basis of $V^*$?

(Obviously the solution is well known for the $\ell_p$ norm, but what about in general?)

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ For a general question like this, the general answer is: You find the dual norm by any method which allows you to solve the respective maximization problem. I don't think that one can say something more specific. $\endgroup$
    – Dirk
    Sep 28, 2013 at 13:22
  • $\begingroup$ There need not always be closed form expressions; there can also be examples where computing the dual norm is NP-Hard etc.; this question is not really precise or clear in what it is asking... $\endgroup$
    – Suvrit
    Sep 28, 2013 at 17:34
  • $\begingroup$ Dirk: but is there any specific algorithm that works in general to handle the problem for finite-dimensional vector spaces? $\endgroup$
    – Mike Battaglia
    Sep 28, 2013 at 19:44
  • $\begingroup$ suvrit: I'm looking for a specific algorithm to symbolically compute an expression for the dual norm (when possible). What's an example of a finite-dimensional normed real vector space in which finding the dual norm is NP-hard? $\endgroup$
    – Mike Battaglia
    Sep 28, 2013 at 19:45
  • $\begingroup$ Edited the question to make it clearer that I'm looking for some specific method or algorithm here. $\endgroup$
    – Mike Battaglia
    Sep 28, 2013 at 19:45

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.