inequality in compressed sensing Let $h\in R^n$ is a k-sparse vector, then how can i prove this inequality $$||h||_p\leq k^{1/p-1/q}||h||_q\ \ ,\forall p\in[1,q]$$ where $q\geq 1.$ please help.
 A: This proof goes in 5 steps; there may be a shorter proof.
Proposition 1: If $\{a_i\} i = 1 \ldots n$ are positive reals, and $1 \leq p < q$, then for a fixed value of $\sum_{j=1}^k a_j^q = R$, the expression
$$
L = \left( \sum_{j=1}^k a_j^p \right) ^{\frac{1}{p}}
$$
is maximized when $a_1 = a_2 = \cdots = a_n = (R/k)^{\frac{1}{q}}$.
Proof: Let $ a=(R/k)^{\frac{1}{q}}$. Consider a small change vector $\delta a_i$ 
from the point at $a_1 = a_2 = \cdots = a_n = a$.  Then 
$$
\delta\left(  \sum_{j=1}^k a_j^q \right) = q\sum_i a^{q-1}\delta a_i
$$
and in order that $\sum_{j=1}^k a_j^q $ remain constant along a short step in some direction we must have 
$$
\sum_i \delta a_i = 0.
$$
Then when we make the change with $\sum_i \delta a_i = 0$ to expression $L$ we find
$$
\delta L = \left( \sum_j a_k^p \right) ^{\frac1p -1} a^{p-1} \sum_i \delta a_i
$$
which is zero, so the point $a_1 = a_2 = \cdots = a_n = (R/k)^{\frac{1}{q}}$ is an extremmum.  It is also easy to check that given $q>p\geq 1$ this extremmum is a maximum.  
Corrolary 2: If $\{a_i\} i = 1 \ldots n$ are positive reals, and $1 \leq p < q$, then for a fixed value of 
$$\left( \sum_{j=1}^k a_j^q \right)^{\frac{1}{q}}$$
the expression
$$
L = \left( \sum_{j=1}^k a_j^p \right) ^{\frac{1}{p}}
$$
is maximized when $a_1 = a_2 = \cdots = a_n = a$.
This is true because $\left( \sum_{j=1}^k a_j^q \right)^{\frac{1}{q}}$ is a monotonic increasing function of $\sum_{j=1}^k a_j^q $.
Proposition 3:  For any given $\{a_i\}$ and $q>1$ there exist a value $a$ such that 
$$
R = \left( \sum_{j=1}^k a_j^q \right)^{\frac{1}{q}} = \left( \sum_{j=1}^k a^q \right)^{\frac{1}{q}}
$$ 
In particular, since $$\left( \sum_{j=1}^k a^q \right)^{\frac{1}{q}} = 
\left( ka^q \right)^{\frac{1}{q}} = k^{\frac1q}a
$$
the value $a = R/k^{\frac1q}$ satisfies proposition 3.
Proposition 4:  For all $k \in \Bbb{Z}^+$, positive $\{a_i\}$ and $1\leq p \leq q$
$$
\left( \sum_{j=1}^k a_j^p \right) ^{\frac{1}{p}} \leq k^{\frac1q-\frac1p} \left( \sum_{j=1}^k a_j^q \right) ^{\frac{1}{q}}
$$
Proof: Choose $a = R/k^{\frac1q}$, where
$$R = \left( \sum_{j=1}^k a_j^q \right) ^{\frac{1}{q}}
$$
By corrolary 2 we have
$$\left( \sum_{j=1}^k a_j^p \right) ^{\frac{1}{p}} \leq \left( \sum_{j=1}^k a^p \right) ^{\frac{1}{p}} = \left( k a^p \right) ^{\frac{1}{p}} = k^{\frac1p}a 
= k^{\frac1p-\frac1q}\left(k^{\frac1q}\right) a 
= k^{\frac1p-\frac1q}\left(ka^q\right)^{\frac1q} 
$$
and since $$ka^q=R^q = \left( \sum_{j=1}^k a_j^q \right) 
$$
we have 
$$\left( \sum_{j=1}^k a_j^p \right) ^{\frac{1}{p}} \leq k^{\frac1p-\frac1q}\left( \sum_{j=1}^k a_j^q \right)^{\frac1q} 
$$ demonstrating proposition 4.
Theorem 5: 
Let $h\in R^n$ be a k-sparse vector (that is, having precisely $k$ non-zero elements), and let $1\leq p \leq q.  Then 
$$||h||_p\leq k^{1/p-1/q}||h||_q$$
Proof:
For $i = 1 \ldots k$ let $a_i$ be the absolute value of the $i$-th non-zero element of $h$.  Then theorem 5 becomes proposition 4.
