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.



Properties of $l_q$-balls
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}. $$


