Dual Norm

Minkowski norm

Let $S \subset \mathbb{R}^d$ be a convex set. It is symmetric if $S = -S$ , where

-S \doteq \{ - \vec v : \vec v \in S \}.

The Minkowski norm $\Vert \vec x \Vert_S$ induced by the convex body $S$ is defined as

\Vert \vec x \Vert_S \doteq \inf \{ r \in \mathbb{R}_{\ge 0} : \vec x \in r S \},

where $r S \doteq \{ r \vec v : \vec v \in S \}$ .

Fact $\Vert \cdot \Vert_S$ is is a norm.

Proof.

For all $\vec x \in \mathbb{R}^d$ , $\Vert \vec x \Vert_S \ge 0$ .
For all $c \in \mathbb{R}, \vec x \in \mathbb{R}^d$ , $\Vert c \vec x \Vert_S = |c| \cdot \Vert \vec x \Vert_S$ .
For all $\vec x, \vec y \in \mathbb{R}^d$ , $\Vert \vec x + \vec y \Vert_S \le \Vert \vec x \Vert_S + \Vert \vec y \Vert_S$ .

The claim is trivial if $\Vert \vec x \Vert_S$ or $\Vert \vec y \Vert_S = 0$ . Otherwise,
$\begin{aligned} &\Vert \vec x + \vec y \Vert_S \le \Vert \vec x \Vert_S + \Vert \vec y \Vert_S \\ \Longleftrightarrow &\left\Vert \frac{ \Vert \vec x \Vert_S }{ \Vert \vec x \Vert_S + \Vert \vec y \Vert_S } \cdot \frac{ \vec x }{ \Vert \vec x \Vert_S } + \frac{ \Vert \vec y \Vert_S }{ \Vert \vec x \Vert_S + \Vert \vec y \Vert_S } \cdot \frac{ \vec y }{ \Vert \vec y \Vert_S } \right\Vert_S &\le 1 \\ \end{aligned}$
It suffices to assume that $\Vert \vec x \Vert_S = \Vert \vec y \Vert_S = 1$ . But this implies that $x , y \in S$ . Since $S$ is convex, for $a, b \in \mathbb{R}_{\ge 0}$ , s.t., $a + b = 1$ , we have
$a \cdot \vec x + b \cdot \vec y \in S.$

Remark: More rigorously, we require that $\vec 0$ is an inner point of $S$ , so that

\Vert \vec x \Vert_S = 0 \iff \vec x = \vec 0.

$\square$

The polar body $S^*$ of $S$ is defined as

\{ \vec u \in \mathbb{R}^d : \left< \vec u, \vec v \right> \le 1 \, \forall \vec v \in S \}.

Fact. If $S$ is convex and symmetric, so is $S^*$ .

Proof. For all $\vec y, \vec z \in S^*$ , and $a, b \in [0, 1]$ , such that $a + b = 1$ , we have

\sup_{ \vec v \in S} \left< \vec v, a \cdot \vec y + b \cdot \vec z \right> \le \sup_{ \vec v \in S} \left< \vec v, a \cdot \vec y \right> + \sup_{ \vec v \in S} \left< \vec v, b \cdot \vec z \right> \le a + b = 1.

It is trivial to prove that $S^*$ is also symmetric.

$\square$

Definition. The Minkowski norm induced by $S^*$ (if it is convex and symmetric) is the dual norm of $\Vert \cdot \Vert_S$ , and is defined as
$\Vert \vec y \Vert_{S^*} \doteq \sup_{ \vec x \in S } \left< \vec x, \vec y \right>,$
or equivalently,
$\Vert \vec y \Vert_{S^*} \doteq \sup \left< \vec x, \vec y \right>, \, \text{ s.t., } \Vert \vec x \Vert_S = 1.$

Proof. To verify the norm is well defined, we need to prove that

For all $\vec y \in \mathbb{R}^d$ , $\Vert \vec y \Vert_{S^*} \ge 0$ .
For all $c \in \mathbb{R}, \vec y \in \mathbb{R}^d$ , $\Vert c \vec y \Vert_{S^*} = |c| \cdot \Vert \vec y \Vert_{S^*}$ .
For all $\vec y, \vec z \in \mathbb{R}^d$ , $\Vert \vec y + \vec z \Vert_{S^*} \le \Vert \vec y \Vert_{S^*} + \Vert \vec z \Vert_{S^*}$ .

The first two properties are obvious. The triangle inequality follows from that

\sup_{ \Vert x \Vert_S = 1} \left< x, \vec y + \vec z \right> \le \sup_{ \Vert x \Vert_S = 1} \left< x, \vec y \right> + \sup_{ \Vert x \Vert_S = 1} \left< x, \vec z \right>.

$\square$

Fact. For $p, q \in [1, \infty]$ , s.t., $\frac{1}{p} + \frac{1}{q} = 1$ , $\Vert \cdot \Vert_p$ is the dual norm of $\Vert \cdot \Vert_q$ .

Proof. Let

S \doteq \Big\{ \vec x \in \mathbb{R}^d : \Big( \sum_{i \in [d] } |x_i|^p \Big)^{1 / p} \le 1 \Big\}.

By definition, we need to prove that for all $\vec y \in \mathbb{R}^d$ ,

\sup_{ \vec x \in S } \Big\{ \left< \vec x, \vec y \right> \Big\} = \Vert \vec y \Vert_q.

Consider

\max \left< \vec x, \vec y \right> \, s.t., \, \Vert \vec x \Vert_S = 1.

Define

f(\vec x, \lambda) = \left< \vec x, \vec y \right> - \lambda( \Vert \vec x \Vert_p - 1).

WLOG, assume that $\vec y \ge 0$ . Then $\vec x \ge 0$ . Setting

\frac{\partial f}{ \partial x_i} = y_i - \lambda \frac{ p x_i^{ p - 1 } }{ \Big( \sum_{ j \in [d] } x_i^p \Big)^{ 1 - 1 / p} } = 0.

As $\Vert \vec x \Vert_p = 1$ and $1 / q = (p - 1) / p$ , we have

\begin{aligned} x_i &= \left( \frac{ y_i }{ \lambda p} \right)^{1 / (p - 1)} = \left( \frac{ y_i }{ \lambda p} \right)^{ q / p} ,\\ \Vert \vec x \Vert_p^p &= \frac{1}{ (\lambda p)^q } \sum_{i \in [d] } y_i^q = 1. \end{aligned}

Finally,

\begin{aligned} \left< \vec x, \vec y \right> &= \frac{1}{ (\lambda p)^{ q / p} } \sum_{j \in [d] } y_i^{ q / p + 1 } \\ &= \frac{1}{ (\lambda p)^{ q / p} } \sum_{j \in [d] } y_i^{ q } \\ &= \left( \sum_{j \in [d] } y_i^{ q } \right)^{ 1 - \frac{1}{p} } \\ &= \Vert \vec y \Vert_q. \end{aligned}

$\square$

The following fact provides geometric interpretation of Holder Inequality.

Fact (Generalized Holder Inequality).
$\left< \vec x, \vec y \right> \le \Vert \vec x \Vert_S \cdot \Vert \vec y \Vert_{S^*}$

Proof. If $\Vert \vec x \Vert_S \le 1$ , then $\vec x \in S$ . Hence,

\Vert \vec y \Vert_{S^*} \doteq \sup_{ \vec v \in S } \left< \vec v, \vec y \right> \ge \left< \frac{\vec x}{ \Vert \vec x \Vert_S }, \vec y \right>.

We can also see that if $\Vert \vec x \Vert_S = 1$ and $\Vert \vec y \Vert_{S^*} = 1$ , then

\left< \vec x, \vec y \right> \le 1.

This is trivially true by the definition of $S^*$ .

$\square$

Reference

[1] Ryan Tibshirani, 10-725/36-725: Convex Optimization Fall 2018, Lecture 13: Duality: Uses and Correspondences.
[2] A.A. Ahmadi, ORF 523 Lecture 2 Spring 2016.