Blog (mostly math)

Minkowski Inequality (Weak)

[This is a weaker version, but the proof comes naturally]

Consider $ \mathbb{R}^n $. We know $\lVert x\rVert_2 := \sqrt{\sum x^2_i} $ is a norm (ie “behaves like length”, especially $ \lVert x+y\rVert_2 \leq \lVert x\rVert_2 + \lVert y\rVert_2 $). So we can ask ourselves :
$ \color{goldenrod}{\text{Q}} $) For integer $ p\geq 1$, taking $ \lVert x\rVert_p := (\sum |x_i|^p)^{\frac{1}{p}} $, is $ \lVert x+y\rVert_p \leq \lVert x\rVert_p + \lVert y\rVert_p $ ?
[$ p=1,2 $ cases check out]

We want $ (\lVert x+y \rVert_p)^p \leq (\lVert x\rVert_p + \lVert y\rVert_p)^p $, that is $ \sum_{i=1}^{n} \vert x_i + y_i\vert^p \leq \sum_{k=0}^{p} \binom{p}{k} \lVert x\rVert_p ^k \lVert y\rVert_p ^{p-k} $.
As $ \vert x_i + y_i\vert^p \leq (\vert x_i\vert + \vert y_i\vert)^p $, it suffices to show $ \sum_{i=1}^{n} (\vert x_i\vert + \vert y_i\vert )^p \leq \sum_{k=0}^{p} \binom{p}{k} \lVert x\rVert_p ^k \lVert y\rVert_p ^{p-k} $, that is $ \sum_{i=1}^{n} ( \sum_{k=0}^{p} \binom{p}{k} \vert x_i\vert ^{k} \vert y_i\vert ^{p-k} ) \leq \sum_{k=0}^{p} \binom{p}{k} \lVert x\rVert_p ^k \lVert y\rVert_p ^{p-k} $, that is $ \sum_{k=0}^{p} \binom{p}{k} \underline{( \sum_{i=1}^{n} \vert x_i\vert^{k} \vert y_i\vert^{p-k} )} \leq \sum_{k=0}^{p} \binom{p}{k} \underline{\lVert x\rVert_p ^k \lVert y\rVert_p ^{p-k}} $.

So it suffices to show $ \sum_{i=1}^{n} \vert x_i\vert^{k} \vert y_i\vert^{p-k} \leq \lVert x\rVert_p ^k \lVert y\rVert_p ^{p-k} $ for $ 0 < k < p $.

If even one of $ x,y $ is $ 0$ it holds trivially, so we’ll take $ x,y $ to be nonzero. We now want $ \sum_{i=1}^{n} \left( \frac{\vert x_i\vert}{\lVert x\rVert_p} \right)^k \left( \frac{\vert y_i\vert}{\lVert y\rVert_p} \right)^{p-k} \leq 1 $.
Taking $u:= ( (\frac{\vert x_1\vert}{\lVert x\rVert_p})^k , \ldots, (\frac{\vert x_n\vert}{\lVert x\rVert_p})^k ) $ and $ v := ( (\frac{\vert y_1\vert}{\lVert y\rVert_p})^{p-k}, \ldots, (\frac{\vert y_n\vert}{\lVert y\rVert_p})^{p-k} )$, we need to prove $ \sum_{i} u_i v_i \leq 1 $ (i.e that $ \langle u, v \rangle \leq 1$).

Notice $ u,v$ have “size contraints” $ \sum_{i} (u_i)^{\frac{p}{k}} = 1 $ (i.e $ \lVert u\rVert_{\frac{p}{k}} = 1 $) and $ \sum_{i} (v_i)^{\frac{p}{p-k}} = 1 $ (i.e $ \lVert v\rVert_{\frac{p}{p-k}} = 1$).
Looking at the contraints $ \lVert u \rVert_{\frac{p}{k}} = \lVert v \rVert_{\frac{p}{p-k}} = 1 $, the crucial relation between $ \alpha := \frac{p}{k} $ and $ \beta := \frac{p}{p-k} $ is that $ \beta = \frac{1}{1 - \frac{1}{\alpha}} $, that is $ \frac{1}{\alpha} + \frac{1}{\beta} = 1 $.
So… we’ll be done if we can establish the following lemma.

$ \color{goldenrod}{\text{Lem}} $: Consider reals $\alpha, \beta > 1 $ with $ \frac{1}{\alpha} + \frac{1}{\beta} = 1 $, and $ u,v \in \mathbb{R}^n $ with $ \lVert u \rVert_{\alpha} = \lVert v \rVert_{\beta} = 1 $ (i.e $\sum \vert u_i\vert^{\alpha} = \sum \vert v_i\vert^{\beta} = 1$).
Then $ |\langle u, v \rangle| \leq 1 $.
$\color{goldenrod}{\text{Pf}} $: $ \vert \langle u,v \rangle\vert = \vert \sum u_i v_i \vert $ $ \leq \sum \vert u_i\vert \vert v_i \vert$.
For indices where $ u_i, v_i $ are both nonzero, $ \vert u_i\vert \vert v_i\vert = (\vert u_i\vert^{\alpha})^{\frac{1}{\alpha}} (\vert v_i\vert^{\beta})^{\frac{1}{\beta}} $ $ = e^{\frac{1}{\alpha}\log(|u_i|^{\alpha}) + \frac{1}{\beta} \log(\vert v_i\vert^{\beta})}$ $\leq e^{\log(\frac{1}{\alpha} \vert u_i\vert^{\alpha} + \frac{1}{\beta} \vert v_i\vert^{\beta})}$ $ = \frac{1}{\alpha} \vert u_i\vert ^{\alpha} + \frac{1}{\beta} \vert v_i\vert^{\beta} $, that is $ \vert u_i\vert \vert v_i\vert \leq \frac{1}{\alpha} \vert u_i\vert^{\alpha} + \frac{1}{\beta} \vert v_i\vert^{\beta} $.
Even for indices where one of $u_i, v_i $ is $ 0$, we have $\vert u_i\vert \vert v_i\vert \leq \frac{1}{\alpha} \vert u_i\vert^{\alpha} + \frac{1}{\beta} \vert v_i\vert^{\beta} $.
So $ \vert \langle u, v \rangle\vert \leq \sum \vert u_i\vert \vert v_i\vert $ $\leq \sum (\frac{1}{\alpha} \vert u_i\vert^{\alpha} + \frac{1}{\beta} \vert v_i\vert^{\beta}) = 1 $, as needed.

comments powered by Disqus