5
$\begingroup$

While looking over my notes, my lecturer stated the following inequality; $$\|x\|_2 \leq \|x\|_1 \leq \sqrt{n}\|x\|_2$$ where $x \in \mathbb{R^n}.$ There was no proof given, and I've been trying to prove it for a while now. I know the definitions of the $1$ and $2$ norm, and, numerically the inequality seems obvious, although I don't know where to start rigorously.

Thank you.

$\endgroup$
6
$\begingroup$

We will show the more general case:

$\|\ \cdot \|_1$ , $\|\ \cdot \|_2$, and $\|\ \cdot \|_{\infty}$ are all equivalent on $\mathbb{R}^{n}$. And we have $$\|\ x \|_{\infty} \leq \|\ x \|_{2} \leq \|\ x \|_{1} \leq n \|\ x \|_{\infty}\ $$

Every $x \in \mathbb{R}^{n}$ has the representation $x = ( x_1 , x_2 , \dots , x_n )$. Using the canonical basis of $\mathbb{R}^{n}$, namely $e_{i}$, where $e_i = (0, \dots , 0 , 1 , 0 , \dots , 0 )$ for $1$ in the $i^{\text{th}}$ position and otherwise $0$, we have that $$\|\ x \|_{\infty} = \max_{1\leq i \leq n} | x_i | = \max_{1\leq i \leq n} \sqrt{ | x_i |^{2} } \leq \sqrt{ \sum_{i=1}^{n} | x_ i |^{2} } = \|\ x \|_2 $$ Additionally, $$ \|\ x \|_2 = \sqrt{ \sum_{i=1}^{n} | x_i |^{2} } \leq \sum_{i=1}^{n} \sqrt{ | x_ i |^{2} } = \sum_{i=1}^{n} |x_i| = \|\ x \|_1$$ Finally, $$ \|\ x_1 \|\ = \sum_{i=1}^{n} |x_i| \leq \sum_{i=1}^{n} | \max_{1 \leq j \leq n} x_j | = n \max_{i \leq j \leq n} | x_j | = n \|\ x \|_{\infty}$$ showing the chain of inequalities as desired. Moreover for any norm on $\mathbb{R}^{n}$ we have that $$\|\ x - x_{n} \|\ \to 0 \hspace{1cm} \text{as} \space\ \space\ n \to \infty $$ so that they are equivalent as this holds for any $x \in \mathbb{R}^{n}$ under any norm actually.

$\endgroup$
  • 1
    $\begingroup$ If I wanted to more explicitly show that $\|\cdot\|_1$ was equivalent to $\|\cdot\|_2$ could I use the fact that $\|x\|_1\le\ n|x\|_\infty\iff\frac1n \|x\|_1\le\|x\|_\infty$ to deduce that $\frac1n \|x\|_1\le \|x\|_2\le \|x\|_1$? Or would I need to do something more explicit? $\endgroup$ – Jeremy Jeffrey James Mar 13 '18 at 22:05
  • 2
    $\begingroup$ @JeremyJeffreyJames This should work: $$ \|\ x \|_2 = \sqrt{ \sum_{i=1}^{n} | x_i |^{2} } \leq \sum_{i=1}^{n} \sqrt{ | x_ i |^{2} } = \sum_{i=1}^{n} |x_i| = \|\ x \|_1.$$ Then, using the Cauchy–Schwarz inequality we get for all $x\in\mathbb{R}^n$: $$ \Vert x\Vert_1= \sum\limits_{i=1}^n|x_i|= \sum\limits_{i=1}^n|x_i|\cdot 1\leq \left(\sum\limits_{i=1}^n|x_i|^2\right)^{1/2}\left(\sum\limits_{i=1}^n 1^2\right)^{1/2}= \sqrt{n}\Vert x\Vert_2, $$ $\endgroup$ – Dragonite Mar 19 '18 at 12:50
  • $\begingroup$ @Dragonite it is not clear how you get $\sqrt{ \sum_{i=1}^{n} | x_i |^{2} } \leq \sum_{i=1}^{n} \sqrt{ | x_ i |^{2} }$. Could you please offer more details? $\endgroup$ – johnny09 Apr 20 at 23:42
1
$\begingroup$

The inequality $ ||x||_1 \leq \sqrt{n} ||x||_2 $ is a consequence of Cauchy-Schwarz. To see this

$$\sqrt{n} ||x||_2 =\sqrt{1+1+\cdots+1}\sqrt{\sum_{i} x_i^2 }\geq ||x||_1$$

For the first, the function $f(x)=\sqrt{x}$ is concave and $f(0)=0$, hence $f$ is subadditive

Therefore $ f(\sum_{i} x_i^2 )\leq \sum_{i} f(x_i^2) =||x||_1 $

$\endgroup$
0
$\begingroup$

Hint: Bound $\left \lVert x\right \rVert_2$ by $\left \lVert x'\right \rVert_2$ where $x'$ is the vector with all its components equal to the maximum of the components of $x$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.