Monotonicity of $\ell_p$ norm

Consider a $n$ dimensional space, it is known (Wikipedia) that for $p>r>0$, we have

$$ \|x\|_p\leq\|x\|_r\leq n^{(1/r-1/p)}\|x\|_p. $$

I have two questions about the above inequality.

$(\bf 1)$. The first is how to show $\|x\|_p\leq\|x\|_r$ when $p,r\leq1$. When $p>r\geq1$, we can define $$f(s)=\|x\|_s,\,\,s\geq1$$ and find out that $$f'(s)=\|x\|_s\left\{-\frac{1}{s^2}\log(\sum_i|x_i|^s)+\frac{1}{s}\frac{\sum_i|x_i|^s\log(|x_i|)}{\sum_i|x_i|^s}\right\}.$$

Then by the concavity of the $\log$ function, we can see that $$\frac{\sum_i|x_i|^s\log(|x_i|)}{\sum_i|x_i|^s}\leq \log\left(\sum_i\frac{|x_i|^s}{\sum_j|x_j|^s}\cdot|x_i|\right).$$ Let $$y_i=\frac{|x_i|^s}{\sum_j|x_j|^s},$$ it is easy to see $\|y\|_{s^*}\leq1$, where $s^*\geq1$ and $1/s+1/s^*=1$. Then, the Hölder's inequality leads to $$\frac{\sum_i|x_i|^s\log(|x_i|)}{\sum_i|x_i|^s}\leq \log\left(\sum_i\frac{|x_i|^s}{\sum_j|x_j|^s}\cdot|x_i|\right)= \log\left(\sum_iy_i\cdot|x_i|\right)\leq\log(\|x\|_s\|y\|_{s^*})\leq\log\|x\|_s.$$ Therefore, we can conclude $f'(s)\leq0$ and $\|x\|_p\leq\|x\|_r$ is satisfied. However, when $p,r<1$, we do not have $s^*\geq1$ and $\|y\|_{s^*}\leq1$. The last step does not work any more.

(${\bf 2}$). My second question is how to show $\|x\|_r\leq n^{(1/r-1/p)}\|x\|_p.$ In fact, I was trying to show this by solving the following optimization problem:

$$ \max_{\|x\|_p\leq1} \|x\|_r. $$ But seems it is difficult to derive a closed form solution. The objective function is non-smooth. Is there any elegant way to solve the above optimization problem?

Can anyone give me a hint? Thanks a lot.

Solution 1:

This answers your first question

As for the second question. Consider Holder inequality $$ \sum\limits_{i=1}^n |a_ib_i|\leq \left(\sum\limits_{i=1}^n |a_i|^{s/(s-1)}\right)^{1-1/s}\left(\sum\limits_{i=1}^n |b_i|^s\right)^{1/s} $$ with $a_i=1$, $b_i=|x_i|^r$, $s=p/r$.

Solution 2:

For (i): Let $p>r>0$ and define $\|x\|_p = (\sum_{i} |x_i|^p)^{1/p}$.

First suppose that $\|x\|_p=1$. Then $\|x\|_p^p=1$ and $|x_i|\le 1$ for all $i$. Since $p>r$, we obtain $|x_i|^p \le |x_i|^r$ for all $i$ and, therefore,

$$1=\|x\|_p^p = \sum_{i} |x_i|^p \le \sum_{i} |x_i|^r = \|x\|_r^r.$$

Hence, $\|x\|_r \ge 1 = \|x\|_p$.

In the general case, set $y_i=x_i/\|x\|_p$, $y$ the vector with components $y_i$. Then $\|y\|_p=1$ and we can use the first part of the proof to obtain

$$ 1=\|y\|_p \le \|y\|_r= \frac{\|x\|_r}{\|x\|_p}. $$

This works for all $p>r>0$ when we define $\|x\|_p = (\sum_{i} |x_i|^p)^{1/p}$. However, for $p<1$, this does not define a norm since it is not sub-additive. See the lines after the formula you quote from Wikipedia. Sometimes the formula $\|x\|_p=\sum_{i} |x_i|^p$ is used in the case $p<1$.