Let $\| \cdot \|$ be a norm on $\mathbb{R}^n$. The associated dual norm, denoted $\| \cdot \|_*$ is defined as $\| z \|_* = \sup\{ z^{t} x : \| x \| < 1 \}$.

Does someone know how prove that the dual norm of the $\mathcal l_{p}$ norm is the $\mathcal l_{q}$ norm? It's not homework. I've been reading about norms and it was stated without proof in a book. Thanks.

  • 2
    $\begingroup$ Are you familiar with Hölder's inequality? $\endgroup$ – Alfonso Fernandez Dec 27 '12 at 3:05
  • 1
    $\begingroup$ hi: yes, I know that it says that \sum_{i=1}^{n} x_i y_i <= (\sum_{i=1}^{n} (|x_{i}|^p ))^(1/p) + (\sum_{i=1}^{n} (|y_{i}|^q ))^(1/q) where 1/p + 1/q = 1. In fact, that was the hint in the statement of the theorem. But I still couldn't figure out how to use that to prove it. Thanks. $\endgroup$ – mark leeds Dec 27 '12 at 3:13
  • 2
    $\begingroup$ For other readers: $$\sum_{i=1}^{n} |x_i y_i| \leq \left(\sum_{i=1}^{n} |x_{i}|^p \right)^{1/p} \cdot \left(\sum_{i=1}^{n} |y_{i}|^q \right)^{1/q} \text{ where } \frac{1}{p} + \frac{1}{q} = 1$$ $\endgroup$ – Alexander Gruber Dec 27 '12 at 3:54
  • $\begingroup$ Nice answer by the way @nullUser. $\endgroup$ – Alexander Gruber Dec 27 '12 at 4:48

Edit: I have edited my answer to conform more to the notation of the paper you linked.

Firstly, suppose $||\cdot||$ is a norm on $\mathbb{R}^n$, and the dual norm $||\cdot||_*$ is defined as $$ ||z||_* := \sup \{ z^{\top} x : x \in \mathbb{R}^n, ||x|| \leq 1\} $$ for all $z \in \mathbb{R}^n$. Note that the quantity $z^{\top} x = z\cdot x = \sum_{i=1}^n z_ix_i$ is just the dot product of $z$ and $x$ if thought of both as row vectors.

The paper you linked only mentions the case $1<p,q<\infty$, so we will work in that framework and not worry about the extremal cases. Fix $p,q \in (1,\infty)$ Holder conjugates (i.e. $\frac1p + \frac1q = 1$). Furthermore, fix $z=(z_1,\ldots,z_n) \in \mathbb{R}^n$. We will show that $$ \sup \left\{ \sum_{i=1}^n z_ix_i : x=(x_1,\ldots,x_n) \in \mathbb{R}^n, ||x||_q \leq 1\right\} = ||z||_p. $$ We may assume without loss of generality that $z \neq 0$, otherwise both norms are trivially zero.

Let $x=(x_1,\ldots,x_n) \in \mathbb{R}^n$ with $||x||_q \leq 1$ be given. We have by Holder's inequality that $$ \sum_{i=1}^n z_ix_i \leq \sum_{i=1}^n |z_ix_i|= ||zx||_1 \leq ||z||_p ||x||_q \leq ||z||_p $$ Hence the supremum in question is at most $||z||_p$. In order to show that the supremum is exactly $||z||_p$, it suffices to find a single $y \in \mathbb{R}^n$ with $||y||_q \leq 1$ such that $\sum_{i=1}^n z_iy_i = ||z||_p$.

Let $x := \mathrm{sign}(z) |z|^{p-1}$, i.e. $x_i := \mathrm{sign}(z_i)|z_i|^{p-1}$ for all $i=1,\ldots,n$. We calculate $$ \sum_{i=1}^n z_i x_i = \sum_{i=1}^n z_i \mathrm{sign}(z_i)|z_i|^{p-1} = \sum_{i=1}^n |z_i|^p = ||z||_p^p $$ where here we used the fact that $z_i \mathrm{sign}(z_i) = |z_i|$. Furthermore, we calculate $$ ||x||_q^q = \sum_{i=1}^n |x_i|^q = \sum_{i=1}^n |\mathrm{sign}(z_i)|z_i|^{p-1}|^q = \sum_{i=1}^n |z_i|^{q(p-1)}= \sum_{i=1}^n |z_i|^p =||z||_p^p $$ where here we used the fact that since $\frac1p + \frac1q = 1$ we have $q(p-1) = p$. Now choose $y := \frac{x}{||x||_q}$ (this is where we used the fact that $z \neq 0$, so that $||x||_q > 0$). By construction we have $||y||_q = 1$, and $$ \sum_{i=1}^n z_i y_i = \sum_{i=1}^n z_i \frac{x_i}{||x||_q} = \frac{1}{||x||_q}\sum_{i=1}^n z_i x_i $$ and using the fact that $||x||_q = (||x||_q^q)^{1/q} = (||z||_p^p)^{1/q} = ||z||_p^{p/q}$ and that $\sum_{i=1}^n z_ix_i = ||z||_p^p$ we have that $$ \frac{1}{||x||_q}\sum_{i=1}^n z_i x_i = \frac{1}{ ||z||_p^{p/q}}||z||_p^p = ||z||_p^{p-p/q} = ||z||_p $$ where here we used the fact that $\frac1p + \frac1q = 1$ implies $p-p/q = p(1-1/q) = p(1/p) = 1$. Thus we have found $y \in \mathbb{R}^n$ with $||y||_q \leq 1$ such that $\sum_{i=1}^n z_i y_i = ||z||_p$ as desired, completing the proof.

  • $\begingroup$ Thanks NullUser. I did know it was a product rather than a sum. That was a typo. As far as the rest of what you wrote, I'll fight through it and see if I can understand it. It's really appreciated. As I've said before. An amazing list to be on. $\endgroup$ – mark leeds Dec 27 '12 at 13:06
  • $\begingroup$ Hi nullUser: I went over your answer but, to be totally honest,I can't follow most of the steps. Would you mind explaining a few of them. I realize it's probably difficult and a lot of work so no problem if the answer is no. Maybe I'll post the question again ? Thanks a lot either way. $\endgroup$ – mark leeds Dec 27 '12 at 20:28
  • $\begingroup$ I would be happy to explain further, where is the first part that you get stuck at? $\endgroup$ – nullUser Dec 27 '12 at 22:04
  • $\begingroup$ @markleeds Perhaps I am misunderstanding your notation. Could you tell me what exactly $\| z \|_* = \sup\{ z^{t} x : \| x \| < 1 \}$ means? What spaces are $z, x$ in? $\endgroup$ – nullUser Dec 27 '12 at 22:14
  • $\begingroup$ Thanks nullUser: That's really kind of you. I'll will find the exact statement and get back to you but I think you DEFINITELY understand it. It's my problem in that I'm not following your derivation. $\endgroup$ – mark leeds Dec 28 '12 at 13:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.