For a given norm [latex]||\cdot||[/latex] on [latex]\mathbb{R}^n[/latex], the dual norm, denoted [latex]||\cdot||_*[/latex], is the function from [latex]\mathbb{R}^n[/latex] to [latex]\mathbb{R}[/latex] with values

[latex]\begin{align*} \|y\|_* &= \max\limits_{x}x^Ty: \|x\| \leq 1. \end{align*}[/latex]

The above definition indeed corresponds to a norm: it is convex, as it is the pointwise maximum of convex (in fact, linear) functions [latex]x \rightarrow y^Tx[/latex]; it is homogeneous of degree [latex]1[/latex], that is, [latex]||\alpha x||_* = \alpha ||x||_*[/latex] for every [latex]x \in \mathbb{R}^n[/latex] and [latex]\alpha \ge 0[/latex].

By definition of the dual norm,

[latex]\begin{align*} x^Ty &\leq \|x\|\cdot \|y\|_*. \end{align*}[/latex]

This can be seen as a generalized version of the Cauchy-Schwartz inequality, which corresponds to the Euclidean norm.

Examples:

● The norm dual to the Euclidean norm is itself. This comes directly from the Cauchy-Schwartz inequality.

● The norm dual to the [latex]l_\infty[/latex]-norm is the [latex]l_1[/latex]-norm. This is because the inequality

[latex]\begin{align*} x^Ty &\leq \|x\|_\infty \cdot \|y\|_1. \end{align*}[/latex]

holds trivially, and is attained for [latex]x = {\bf sign}(y)[/latex].

● The dual norm above is the original norm we started with. (The proof of this general result is more involved.)