# Properties of $l_q$-balls

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, $$\|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.

• Since your question is phrased as "show that ..." could you give us a little bit more information about where the question arose? In other words, is the desired conclusion something claimed in a paper you are reading, or a text you are following? Jan 19, 2021 at 22:17
• @YemonChoi It is from the book High-Dimensional Statistics: A Non-Asymptotic Viewpoint by Martin J. Wainwright. It is actually the last question in Exercise 7.2 (Page 230). I hope to solve this problem because in Page 196 it says Exercise 7.2 can help understand the interpretations of the membership in the $l_q$ ball. Jan 20, 2021 at 0:14
• Hepdrey, you may find more luck getting a response on maths.stackexchange.com. Questions on exercises from textbooks are probably best there. I just asked such a question myself and got a response quickly! :-) Jan 20, 2021 at 10:10

## 1 Answer

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}.$$

• How to derive the first inequality? Thanks.
– Tan
May 28, 2021 at 19:19