L1-L2 norm inequality

Theorem: For all $x \in R^{d}$ ,

‖ x ‖_{2} \leq ‖ x ‖_{1} \leq \sqrt{d} ‖ x ‖_{2}

Proof:

\begin{aligned} ‖ x ‖_{2}^{2} & = \sum_{i} x_{i}^{2} \\ \leq \sum_{i} | x_{i} | \sum_{i} | x_{i} | & \sum_{i} | x_{i} | \sum_{i} | x_{i} | = \sum_{i} x_{i}^{2} + \sum_{i \neq j} | x_{i} | | x_{j} | \\ = ‖ x ‖_{1} ‖ x ‖_{1} \\ ⟹ & ‖ x ‖_{2} \leq ‖ x ‖_{1} & \sqrt{\cdot} is monotone \end{aligned}

ii)

\begin{aligned} ‖ x ‖_{1} & = a^{⊤} b & Let a_{i} = 1, b_{i} = | x_{i} | \\ \leq ‖ a ‖_{2} ‖ b ‖_{2} & Cauchy-Schwarz \\ = \sqrt{d} ‖ x ‖_{2} \end{aligned}