$$

$p$-norms are ways to aggregate numbers based on their $p^{\text{th}}$ power (for $1\le p\le \mathrm{\infty }$). The higher $p$ is, the more it cares about extreme values. In fact, the $\mathrm{\infty }$-norm is precisely the maximum value.

Depending on how you scale them, there are two kinds of $p$-norms:

• $p$-lengths, which “sum” the numbers,
• $p$-means, which “average” the numbers.

$p$-length

This is the usual notion of $p$-norm of a vector $x\in {\mathbb{R}}^n$:

$${\Vert x\Vert }_p:={(|x_1{|}^p+\cdots |x_n{|}^p)}^{1/p}.$$

In particular:

• ${\Vert x\Vert }_1$ is the Manhattan length,
• ${\Vert x\Vert }_2$ is the Euclidean length,
• ${\Vert x\Vert }_{\mathrm{\infty }}$ is just the (absolute) maximum: ${\Vert x\Vert }_{\mathrm{\infty }}=\underset{i}{max}|x_i|$.

The $p$-length decreases with $p$: when $p=1$, every number contributes to the sum “equally”, but as the power $p$ increases, the lower elements become less and less significant to the sum, until only the maximum value matters at all.

It decreases a lot unless $x$ is sparse

Let $1\le p<q<\mathrm{\infty }$. Since the function $x^{q/p}$ is strictly convex, by superadditivity, we have

$$\begin{array}{rl}{\Vert x\Vert }_q& ={(|x_1{|}^q+\cdots |x_n{|}^q)}^{1/q}\\ & ={({\left(|x_1{|}^p\right)}^{q/p}+\cdots +{\left(|x_n{|}^p\right)}^{q/p})}^{1/q}\\ \text{(superadditivity)}& & \le {\left({(|x_1{|}^p+\cdots +|x_n{|}^p)}^{q/p}\right)}^{1/q}& ={(|x_1{|}^p+\cdots +|x_n{|}^p)}^{1/p}\\ & ={\Vert x\Vert }_p,\end{array}$$

with equality iff all but one of the coordinates are zero: vector $x$ is “perfectly sparse”.

This is actually robust fact: if the ratio $\frac{{\Vert x\Vert }_p}{{\Vert x\Vert }_q}$ is small, then $x$ must be sparse (in $q$-norm). Indeed, for any threshold $h$, you can separate $x=x^{\ge h}+x^{<h}$ where $x^{\ge h}$ contains the entries bigger than $h$ and $x^{<h}$ contains the rest. Then by the same calculation as above,

$${\Vert x^{<h}\Vert }_q^q\le {\Vert x^{<h}\Vert }_p^p{h}^{q-p}\le {\Vert x\Vert }_p^p{h}^{q-p},$$

so you can make sure that $x^{<h}$ contains at most a $\delta$ fraction of the $q$-norm by setting

$${\Vert x\Vert }_p^p{h}^{q-p}=\delta {\Vert x\Vert }_q^q\iff h:={\left(\frac{\delta {\Vert x\Vert }_q^q}{{\Vert x\Vert }_p^p}\right)}^{\frac{1}{q-p}},$$

and then the number of nonzero entries in $x^{\ge h}$ is at most

$$\frac{{\Vert x\Vert }_p^p}{h^p}={\left(\frac{{\left({\Vert x\Vert }_p/{\Vert x\Vert }_q\right)}^q}{\delta }\right)}^{\frac{p}{q-p}}.$$

See Lower-degree norms give sparsity for more intuition and details.

$p$-mean

Let $a_1,\dots ,a_n\in {\mathbb{R}}_{\ge 0}$. If you divide the sum of the $p^{\text{th}}$ powers by $n$, you get a sort of average called “$p$-mean”¹

$$M_p(a):={\left(\frac{a_1^p+\cdots a_n^p}{n}\right)}^{1/p}.$$

More generally, we can consider the $p^{\text{th}}$ moment of a random variable $\mathit{X}$ (which we’ll assume is nonnegative for simplicity)

$${\Vert \mathit{X}\Vert }_p:=\mathrm{E}[{\mathit{X}}^p{]}^{1/p}.$$

In particular:

• $M_1(a)$ is the arithmetic mean and ${\Vert \mathit{X}\Vert }_1$ is the expectation,
• $M_2(a)$ is the quadratic mean,
• $M_{\mathrm{\infty }}(a)$ and ${\Vert \mathit{X}\Vert }_{\mathrm{\infty }}$ are just the maximum.²

The $p$-mean / $p^{\text{th}}$ moment increases with $p$: when $p=1$, every number contributes to the average “equally”, but as the power $p$ increases, the lower elements become less and less significant to the average, until only the maximum value matters at all.

It increases a lot unless $a$ is spread / $\mathit{X}$ is reasonable

Let $1\le p<q<\mathrm{\infty }$. Since the function $x^{q/p}$ is strictly convex, by convexity, we have

$$\begin{array}{rl}{\Vert \mathit{X}\Vert }_p& ={(\mathrm{E}[{\mathit{X}}^p])}^{1/p}\\ & ={(\mathrm{E}[{\mathit{X}}^p{]}^{q/p})}^{1/q}\\ \text{(convexity)}& & \le {\left(\mathrm{E}\left[{\mathit{X}}^q\right]\right)}^{1/q}& ={\Vert \mathit{X}\Vert }_q,\end{array}$$

and thus also $M_p(a)\le M_q(a)$. In particular, the inequality $M_1(a)\le M_2(a)$ (known as “AM-QM”) is a special case of Cauchy–Schwarz, and the inequality ${\Vert \mathit{X}\Vert }_1\le {\Vert \mathit{X}\Vert }_2$ is a consequence of the definition of variance.

The equality case is when

• $\mathit{X}$ is constant: it’s “perfectly reasonable”,
• all the $a_i$’s are equal: they are “perfectly spread”.

This is also a robust fact: if the ratio $\frac{{\Vert \mathit{X}\Vert }_q}{{\Vert \mathit{X}\Vert }_p}$ is small, then $\mathit{X}$ must be reasonable: in particular, it can’t be almost always smaller than its $p$-norm. Indeed,

$$\begin{array}{rlrl}& & \mathrm{E}[{\mathit{X}}^p]& \le (t{\Vert \mathit{X}\Vert }_p{)}^p+\mathrm{E}[{\mathit{X}}^p\cdot \mathbb{1}[\mathit{X}\ge t{\Vert \mathit{X}\Vert }_p]]\\ \text{(by Hölder's)}& & & & \le (t{\Vert \mathit{X}\Vert }_p{)}^p+\mathrm{E}[{\mathit{X}}^q{]}^{\frac{p}{q}}\cdot \mathrm{Pr}[\mathit{X}\ge t{\Vert \mathit{X}\Vert }_p{]}^{\frac{q-p}{q}}& \iff & \mathrm{Pr}[\mathit{X}\ge t{\Vert \mathit{X}\Vert }_p{]}^{\frac{q-p}{p}}& \ge \frac{(1-t^p){\Vert \mathit{X}\Vert }_p^p}{{\Vert \mathit{X}\Vert }_q^p}\\ & \iff & \mathrm{Pr}[\mathit{X}\ge t{\Vert \mathit{X}\Vert }_p]& \ge {\left(\frac{1-t^p}{{\left({\Vert \mathit{X}\Vert }_q/{\Vert \mathit{X}\Vert }_p\right)}^p}\right)}^{\frac{q}{q-p}},\end{array}$$

so in particular, when the ratio is constant, $\mathrm{Pr}[\mathit{X}\ge t{\Vert X\Vert }_p]\ge \mathrm{\Omega }(1)$ for any $t<1$.

Note: I’m pretty sure you can also show that when $\frac{{\Vert \mathit{X}\Vert }_q}{{\Vert \mathit{X}\Vert }_p}\to 1$, it’s not only reasonable but actually concentrated:

$$\mathrm{Pr}[\mathit{X}\notin (1\pm o(1)){\Vert \mathit{X}\Vert }_p]\le o(1).$$

For $p=1,q=2$, it is true by Chebyshev since ${\Vert \mathit{X}\Vert }_2^2-{\Vert \mathit{X}\Vert }_1^2$ is precisely the variance of $\mathit{X}$. I suspect you could prove it in general using a quantitative version of Jensen’s inequality and a lot of courage.

Overall picture

Bounding either side

The $p$-length inequalities and the $p$-mean inequalities complement each other. On the one hand, we can use the $p$-mean inequalities to bound how fast the $p$-length decreases:

$${\Vert x\Vert }_q=n^{\frac{1}{q}}\cdot M_q(x)\ge n^{\frac{1}{q}}\cdot M_p(x)=\frac{{\Vert x\Vert }_p}{n^{\frac{1}{p}-\frac{1}{q}}}.$$

And on the other hand, we can use the $p$-length inequalities bound how fast the $p$-means increases:

$$M_q(a)=\frac{{\Vert a\Vert }_q}{n^{\frac{1}{q}}}\le \frac{{\Vert a\Vert }_p}{n^{\frac{1}{q}}}=n^{\frac{1}{p}-\frac{1}{q}}\cdot M_p(a).$$

But on the third hand, you can’t bound how fast the moments of a continuous random variable increase: in fact, it could be that the $p^{\text{th}}$ moment is finite but the $q^{\text{th}}$ moment is infinite.

So we get the following picture (for $1\le p<q\le \mathrm{\infty }$):

• The $q$-norm ${\Vert x\Vert }_q$ is stuck between $\frac{{\Vert x\Vert }_p}{n^{\frac{1}{p}-\frac{1}{q}}}$ (“spread” regime) and ${\Vert x\Vert }_p$ (“sparse” regime).
• The $q$-mean $M_q(a)$ is stuck between $M_p(a)$ (“spread” regime) and $n^{\frac{1}{p}-\frac{1}{q}}\cdot M_p(a)$ (“sparse” regime).
• The $q^{\text{th}}$ moment ${\Vert \mathit{X}\Vert }_q$ is stuck between ${\Vert \mathit{X}\Vert }_p$ (“reasonable/concentrated” regime) and
  • either $n^{\frac{1}{p}-\frac{1}{q}}{\Vert \mathit{X}\Vert }_p$ if $\mathit{X}$ is discrete (“sparse” regime),
  • or $\mathrm{\infty }$ if $\mathit{X}$ is continuous (“spiky” regime).

TODO: change “concentrated” to “spread” in this graph #figure TODO: also make a “table” #figure

Qualities being tracked

We can use ratios between norms to track different qualitative behaviors (the ratios below are $\ge 1$, with $1$ indicating perfection):

• for a vector $x\in {\mathbb{R}}^n$, the length ratios $\frac{{\Vert x\Vert }_p}{{\Vert x\Vert }_q}$ track its sparsity;
• for a sequence $a\in {\mathbb{R}}_{\ge 0}^n$, the mean ratios $\frac{M_q(a)}{M_p(a)}$ track its spreadness;
• for a random variable $\mathit{X}$, the moment ratios $\frac{{\Vert \mathit{X}\Vert }_q}{{\Vert \mathit{X}\Vert }_p}$ track its reasonableness;
  • by extension, so do the norm ratios $\frac{{\Vert f\Vert }_q}{{\Vert f\Vert }_p}$ for a function $f$ (by considering its value $f(\mathit{X})$ over a random input $\mathit{X}$);
• for a discrete random variable $\mathit{X}$, the power entropy ratios $\frac{H_{\alpha }[\mathit{X}]}{H_{\beta }[\mathit{X}]}$ (for $0\le \alpha <\beta \le \mathrm{\infty }$ ) track its flatness.

TODO: add something about Density functions (are inner products like $⟨f,f^p⟩$ the right notion?)

See also

• Hölder’s inequality

1. In fact, $p$-means can be defined for any $-\mathrm{\infty }\le p\le \mathrm{\infty }$, but they’re only norms for $p\ge 1$ (in the sense of satisfying the triangle inequality). ↩

2. at least, assuming $\mathit{X}$ is either discrete or its pdf is continuous ↩