# An infinity norm proof

Definition

The $$L^p$$ norm is formally defined as

$\norm{x}_p = \left( \sum_i \vert x_i \vert ^p \right) ^ \frac{1}{p}$

The $$L^p$$ norm has several special cases that supposedly arise often in linear algebra, numerical analysis, and machine learning.

The $$L^1$$ norm, commonly called the "taxicab" norm

$\norm{x}_1 = \sum_i \vert x_i \vert$

The $$L^2$$ norm, commonly called the "Euclidean" norm:

$\norm{x}_2 = \sqrt{\sum_i x_i^2}$

The $$L_\infty$$ norm:

$\norm{x}_\infty = \max_i \vert x_i \vert$

It can be shown that this definition of the $$L^\infty$$ norm is equivalent to taking the limit as $$p \to \infty$$ of the $$L^p$$ norm. My machine learning professor claimed this proof would make a good exam problem. It turns out it's not, and he was joking.

Theorem

Let $$x \in \mathbb R^n$$ and define $$\norm{x}_\infty = \max_i \vert x_i \vert$$. Then

$\lim_{p \to \infty} \norm{x}_p = \norm{x}_\infty$

Proof

Let $$\displaystyle\norm{x}_\infty = \max_i \vert x_i \vert$$ and $$\displaystyle\norm{x}_p = \left( \sum_i \vert x_i \vert ^p \right) ^ \frac{1}{p}$$. We wish to show that $$\displaystyle\lim_{p \to \infty} \norm{x}_p = \norm{x}_\infty$$.

We have that

\begin{aligned} \norm{x}_p &= \norm{x}_\infty \frac{\left( \sum_i \vert x_i \vert ^ p \right)^\frac{1}{p}}{\norm{x}_\infty}\\ &= \norm{x}_\infty \left(\sum_i \frac{\vert x_i \vert ^p}{\norm{x}_\infty^p} \right)^\frac{1}{p}\\ &= \norm{x}_\infty \left(\sum_i \left(\frac{\vert x_i \vert}{\norm{x}_\infty}\right)^p\right)^\frac{1}{p}\\ &\leq \norm{x}_\infty n^\frac{1}{p} \end{aligned}

We arrive at the last item because $$\displaystyle\left(\frac{\vert x_i \vert}{\norm{x}_\infty}\right)^p \leq 1$$ for every $$i$$ (because $$\norm{x}_\infty \geq \vert x_i \vert$$ for each $$i$$). Thus we have

$\norm{x}_\infty \leq \norm{x}_p \leq \norm{x}_\infty n^\frac{1}{p}$

so, taking a limit as $$p \to \infty$$, we have

$\norm{x}_\infty \leq \lim_{p \to \infty} \norm{x}_p \leq \norm{x}_\infty \cdot \lim_{p \to \infty} n ^ \frac{1}{p} = \norm{x}_\infty$

In other words, we have $$\lim_{p \to \infty} \norm{x}_p$$ sandwiched between $$\norm{x}_\infty$$ and $$\norm{x}_\infty$$, implying equality. Therefore $$\displaystyle\lim_{p \to \infty} \norm{x}_p = \norm{x}_\infty = \max_i \vert x_i \vert$$.

Consider also this proof:

Proof
Let $$\displaystyle\norm{x}_p = \left( \sum_i \vert x_i \vert ^p \right) ^ \frac{1}{p}$$. Observe that for all $$x$$ we have that

$\max_i \vert x_i \vert \leq \norm{x}_p$

and that

$\norm{x}_p \leq \left(\sum_i \max_i \vert x_i \vert^p\right)^\frac{1}{p}$

Thus,

$\max_i \vert x_i \vert \leq \norm{x}_p \leq \left(\sum_i \max_i \vert x_i \vert ^p\right)^\frac{1}{p}$

but then,

$\left(\sum_i \max_i \vert x_i \vert ^p\right)^\frac{1}{p} = \left(n \cdot \max_i \vert x_i \vert ^ p\right)^\frac{1}{p} = n^\frac{1}{p} \cdot \max_i \vert x_i \vert$

Thus

$\max_i \vert x_i \vert \leq \norm{x}_p \leq n^\frac{1}{p} \cdot \max_i \vert x_i \vert$

however, $$\displaystyle\lim_{p \to \infty} n^\frac{1}{p} = 1$$, so

$\max_i \vert x_i \vert \leq \lim_{p \to \infty}\norm{x}_p \leq \max_i \vert x_i \vert$

or rather, that $$\displaystyle\norm{x}_\infty = \lim_{p \to \infty} \norm{x}_p = \max_i \vert x_i \vert$$.

In hindsight, I regret everything.