17
$\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 to prove that the dual norm of the $\mathcal l_{p}$ norm is the $\mathcal l_{q}$ norm? I read about norms and it was stated without proof in a book.

$\endgroup$
3
  • 2
    $\begingroup$ Are you familiar with Hölder's inequality? $\endgroup$ Dec 27, 2012 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, 2012 at 3:13
  • 3
    $\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, 2012 at 3:54

1 Answer 1

28
$\begingroup$

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.

$\endgroup$
0

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.