10
$\begingroup$

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
    Are you familiar with [Hölder's inequality?](https://en.wikipedia.org/wiki/H%C3%B6lder%27s_inequality)2012-12-27
  • 1
    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.2012-12-27
  • 2
    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$$2012-12-27
  • 0
    Nice answer by the way @nullUser.2012-12-27

1 Answers 1

15

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

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.

  • 0
    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.2012-12-27
  • 0
    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.2012-12-27
  • 0
    I would be happy to explain further, where is the first part that you get stuck at?2012-12-27
  • 0
    @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?2012-12-27
  • 0
    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.2012-12-28
  • 0
    Hi NullUser: The statement is on page 7 of the paper at the link http://arxiv.org/pdf/0706.4138v1.pdf. But you defintely understand it. I will go through your derivation and explain the steps that I can't follow. Thanks so much for your help.2012-12-28
  • 0
    @markleeds I have added the intermediate calculations and changed my notation to conform to the paper you linked. I hope this helps.2012-12-28
  • 0
    Hi nullUser: That is so kind of you. If you wouldn't mind to email me off list at markleeds2@gmail.com, I'd like to send you a token of my appreciation. I was actually starting to follow your old notation/derivation a little better ( after working some of the hidden algebra out myself ) but this new one should really help a lot. I so appreciate it. If you can't email me off list, no problem but I just wanted to do something for you since you've been quite kind, whomever you are !!!!!!!!!2012-12-28
  • 0
    @markleeds verified2012-12-28
  • 0
    Then is there any way that I can prove the Holder inequality given the fact that the p-norm's dual is q-norm?2016-10-02
  • 0
    @markleeds what is an off list?2018-03-21
  • 0
    @user2984602: I just meant to my personal email address. but that's okay. it's not necessary. thanks for great answer.2018-03-22