inequality in compressed sensing

Question

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.

Answer 1

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.