1
$\begingroup$

I was wondering which proof method can be used best to show that the $\ell_1$-norm of a unit vector is larger equal the $\ell_2$-norm of it?

$\endgroup$
  • $\begingroup$ What do you mean by unit vector? In what norm? (Anyway, this is irrelevant). $\endgroup$ – Crostul May 18 '17 at 11:50
1
$\begingroup$

Since you are dealing with a unit vector, $u$ each of the components $u_i$ must be at most one. Hence, for each $i$, $u_i^2 \le \lvert u_i\rvert$. So

$$ \lVert u\rVert_2^2 = \sum_i u_i^2 \le \sum_i \lvert u_i\rvert = \lVert u\rVert_1 $$

$\endgroup$
  • $\begingroup$ Not that it matters too much since $u$ is of unit norm (in either $\ell_1$ or $\ell_2$, the OP didn't specify), but to conclude the last step you may want to comment on the fact that the inequlity you show is between squared $\ell_2$ and $\ell_1$ norm. $\endgroup$ – Clement C. May 18 '17 at 12:05
3
$\begingroup$

More generally, this is true even without requiring that the vectors be unit, and for other $\ell_p$ norms: we have monotonicity of the $\ell_p$ norms: for any sequence $x=(x_1,\dots,x_n)\in\mathbb{R}^n$, $p > 0 \mapsto \lVert{x}\rVert_p$ is non-increasing.

In particular, for $0 < p \leq q <\infty$, $$ \left(\sum_i \lvert{x_i}\rvert^q\right)^{1/q} = \lVert{x}\rVert_q \leq \lVert{x}\rVert_p = \left(\sum_i \lvert{x_i}\rvert^p\right)^{1/p}\;. $$ To see why, one can easily prove that if $\lVert{x}\rVert_p = 1$, then $\lVert{x}\rVert_q^q \leq 1$ (bounding each term $\lvert{x_i}\rvert^q \leq \lvert{x_i}\rvert^p$), and therefore $\lVert{x}\rVert_q \leq 1 = \lVert{x}\rVert_p$. Next, for the general case, apply this to $y = x/\lVert{x}\rVert_p$, which has unit $\ell_p$ norm, and conclude by homogeneity of the norm.

$\endgroup$
  • $\begingroup$ Note that the result also holds for $\ell_\infty$ (and is easy to prove as well in that case as well): $\ell_\infty \leq \ell_{72}\leq \ell_2\leq \ell_1$. $\endgroup$ – Clement C. May 18 '17 at 11:59
2
$\begingroup$

Consider $$ \sum_{k=1}^n|x_n| = \left|\sum_{k=1}^n|x_n|\right| = \left(\left(\sum_{k=1}^n |x_n|\right)^2\right)^{1/2} \geq \left(\sum_{k=1}^n |x_n|^2\right)^{1/2} = \left(\sum_{k=1}^n x_n^2\right)^{1/2}, $$ because $y^2 = |y|^2$. If you expand the expression for $\left(\sum_{k=1}^n |x_n|\right)^2$ you get all of $\sum_{k=1}^n |x_n|^2$ plus some additional nonnegative terms. Also, the square root function $t\mapsto t^{1/2}$ is monotonic increasing.

$\endgroup$
  • $\begingroup$ Your answer is nice, hence vote up, but dt688 is more concise in notation, hence accepted his one $\endgroup$ – LeoW. May 18 '17 at 11:57
  • 1
    $\begingroup$ Well, this time I went for as much as explanation in detail that I could :) $\endgroup$ – Wauzl May 18 '17 at 11:58

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.