Properties of $l_q$-balls

Question

For a given $q\in (0,1]$, define the $l_q$-ball as $$\mathbb{B}_q(R_q)\mathrel{:=}\left\{\theta\in\mathbb{R}^d\,\middle\vert\,\sum_{j=1}^d \lvert\theta_j\rvert^q\leq R_q \right\}. $$ For a given integer $s\in\{1,2,\dotsc,d\}$, the best $s$-term approximation to a vector $\theta^*\in\mathbb{R}^d$ is defined as $$\Pi_s(\theta^*)\mathrel{:=}\arg\min_{\|\theta\|_0\leq s} \|\theta-\theta^*\|_2^2.$$ Show that the best $s$-term approximation satisfies $$\|\Pi_s(\theta^*)-\theta^*\|_2^2\leq(R_q)^{2/q}s^{1-2/q}.$$

I can see that $\Pi_s(\theta^*)$ has a closed-form, which takes the largest absolute value from $\theta^*$ and sets the remaining positions as $0$. I guess it is useful to consider the fact that for $0<p<q$, $\|x\|_p\geq \|x\|_q$. But I can only get $(R_q/s)^{2/q}(d-s)^{2/q}$, not $s(R_q/s)^{2/q}$ as in the conclusion.

Answer 1

WLOG, let $\theta^*=(\theta^*_1,...,\theta^*_d)$ with $|\theta^*_1|\geq |\theta^*_2| \geq\cdots\geq |\theta^*_d|$. Then we have $$\|\Pi_s(\theta^*)-\theta^*\|_2^2 = \sum_{j=s+1}^d |\theta^*_j|^2 \leq |\theta^*_s|^{2-q} \sum_{j=s+1}^d |\theta^*_j|^q = \left(\frac{1}{s} \sum_{i=1}^s |\theta^*_s|^q \right)^{\frac{2-q}{q}} \sum_{j=s+1}^d |\theta^*_j|^q \leq \left(\frac{1}{s} \sum_{i=1}^s |\theta^*_i|^q \right)^{\frac{2-q}{q}} \sum_{j=s+1}^d |\theta^*_j|^q = \left(\frac{1}{s} \right)^{\frac{2-q}{q}} \left(\sum_{i=1}^s |\theta^*_i|^q \right)^{\frac{2-q}{q}} \sum_{j=s+1}^d |\theta^*_j|^q \\ \leq \left(\frac{1}{s} \right)^{\frac{2-q}{q}} \left(\sum_{i=1}^d |\theta^*_i|^q \right)^{\frac{2-q}{q}} \sum_{j=1}^d |\theta^*_j|^q = \left(\frac{1}{s} \right)^{\frac{2-q}{q}} \left(\sum_{i=1}^d |\theta^*_i|^q \right)^{\frac{2}{q}} \leq (R_q)^{2/q}s^{1-2/q}. $$