Desigualdad de la norma 1 y 2

Question

Mientras revisaba mis notas, mi profesor mencionó la siguiente desigualdad; $$\|x\|_2 \leq \|x\|_1 \leq \sqrt{n}\|x\|_2$$ donde $x \in \mathbb{R^n}.$ No se dio ninguna prueba, y he estado tratando de probarlo desde hace un tiempo. Conozco las definiciones de la norma $1$ y $2$, y, numéricamente la desigualdad parece obvia, aunque no sé por dónde empezar rigurosamente.

Gracias.

Answer 1

Mostraremos el caso más general, es decir:

$\| \cdot \|_1$, $\| \cdot \|_2$, y $\| \cdot \|_{\infty}$ son equivalentes en $\mathbb{R}^{n}$. Y tenemos $$\| x \|_{\infty} \leq \| x \|_{2} \leq \| x \|_{1} \leq n \| x \|_{\infty}\ $$

Cada $x \in \mathbb{R}^{n}$ tiene la representación $x = ( x_1 , x_2 , \dots , x_n )$. Usando la base canónica de $\mathbb{R}^{n}$, es decir, $e_{i}$, donde $e_i = (0, \dots , 0 , 1 , 0 , \dots , 0 )$ para $1$ en la posición $i^{\text{th}}$ y de lo contrario $0$, tenemos que $$\| 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$$ Además, $$ \| 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$$ Finalmente, $$ \| x \|_1\ = \sum_{i=1}^{n} |x_i| \leq \sum_{i=1}^{n} | \max_{1 \leq j \leq n} x_j | = n \max_{1 \leq j \leq n} | x_j | = n \| x \|_{\infty}$$ mostrando la cadena de desigualdades como se deseaba. Además, para cualquier norma en $\mathbb{R}^{n}$ tenemos que: $$\| x - x_{n} \|\ \to 0 \hspace{1cm} \text{a medida que}\space\ n \to \infty$$ por lo que son equivalentes, ya que esto se cumple para cualquier $x \in \mathbb{R}^{n}$ bajo cualquier norma.

Answer 2

La desigualdad $ \|x\|_1 \leq \sqrt{n} \,\|x\|_2 $ es una consecuencia de Cauchy-Schwarz. Para ver esto

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

Para el primero, la función $f(x)=\sqrt{x}$ es cóncava y $f(0)=0$, por lo tanto $f$ es subaditiva

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

Answer 3

Otra forma de mostrar que $||x||_1 \leq \sqrt{n}||x||_2$ es la siguiente:

\begin{align*} \begin{array}{c} \displaystyle 0\leq \sum_{i\neq j}\big(|x_i|-|x_j|\big)^2 = (n-1)\sum_{i=1}^{n} |x_i|^2 - 2\sum_{i\neq j}|x_i||x_j| \\ \displaystyle\Rightarrow\quad 2\sum_{i\neq j}|x_i||x_j|\leq (n-1)\sum_{i=1}^{n} |x_i|^2 \\ \displaystyle\Rightarrow\quad \sum_{i=1}^{n} |x_i|^2 + 2\sum_{i\neq j}|x_i||x_j|\leq n\sum_{i=1}^{n} |x_i|^2 \\ \displaystyle\Rightarrow\quad \left( \sum_{i=1}^n |x_i| \right)^2 \leq n\sum_{i=1}^{n} |x_i|^2 \\ \displaystyle\Rightarrow \quad ||x||_1\leq \sqrt{n}||x||_2 \end{array} \end{align*}

Answer 4

$\lVert x \rVert_2 \le \lVert x \rVert_1$ es equivalente a $\lVert x \rVert_2^2 \le \lVert x \rVert_1^2$ (las normas son no negativas) lo cual se puede demostrar de manera elemental:

$$\lVert x \rVert_2^2 = \sum_i \lvert x_i\rvert^2 \le \left( \sum_i \lvert x_i \rvert \right)^2 = \lVert x \rVert_1^2$$

Expandiendo el producto $\left(\sum_i |x_i| \right)^2 = \sum_i |x_i|^2 + \sum_{i \neq j} |x_i| |x_j| $ donde todos los términos cruzados $|z_i| |z_j| \ge 0$.

---

Intuición para límites en la norma 2: si $x$ tiene un componente $x_i$ mucho más grande (en magnitud) que el resto, los otros componentes se vuelven despreciables, por lo tanto $\lVert x \rVert_2 \approx \sqrt{x_i^2} = |x_i| \approx \lVert x \rVert_1$.

Por otro lado, si los componentes de $x$ son aproximadamente iguales (en magnitud), $\lVert x \rVert_2 \approx \sqrt{n x_i^2} = \sqrt n \lvert x_i \rvert$ mientras que $\lVert x \rVert_1 \approx n \lvert x_i \rvert$, por lo que $\lVert x \rVert_1 \approx \sqrt n \lVert x \rVert_2 $.

---

En general, por la desigualdad de Hölder, para $1 \le p \le q$, $$\lVert x \rVert_q \le \lVert x \rVert_p \le n^{1/p - 1/q} \lVert x \rVert_q $$

Ver Inequalities in $l_p$ norm

Answer 5

Pista: Acota $\left \lVert x\right \rVert_2$ por $\left \lVert x'\right \rVert_2$ donde $x'$ es el vector con todos sus componentes iguales al máximo de los componentes de $x$.