9
$\begingroup$

For every $u\in \mathbb{R}^n$, $\textbf{Card}(u)=q$ implies ${\lVert u \rVert}_1 \leq \sqrt{q} {\lVert u \rVert}_2$

where $\textbf{Card}(u)$ is the number of non-zero element (so the L0-norm).

Why does the condition ${\lVert u \rVert}_1 \leq \sqrt{q} {\lVert u \rVert}_2$ hold? Is there any place I can find proof for this?

$\endgroup$
0

1 Answer 1

11
$\begingroup$

This is an example of the Cauchy-Schwarz inequality:

\begin{align*} \|u\|_1 &=\sum_{i = 1}^n |u_i|\\ &= \sum_{i = 1}^n |u_i\cdot 1| \\ &\le \left(\sum_{i = 1}^n |u_i|^2\right)^{1/2} \left(\sum_{i = 1}^n 1 \right)^{1/2} \\ &= \|u\|_2 \sqrt{n} \end{align*}

To improve the result to $\sqrt{q}$, use a mix of $1$'s and $0$'s rather than a constant sequence $1$ in the second sum. I'll leave it to you to work out the details.

$\endgroup$
1
  • $\begingroup$ Thank you! Cauchy-Schwarz inequality is in my text and this is exactly. $\endgroup$
    – user26767
    Commented Dec 9, 2015 at 21:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .