0
$\begingroup$

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.

$\endgroup$
3
  • 4
    $\begingroup$ 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? $\endgroup$
    – Yemon Choi
    Jan 19 at 22:17
  • 1
    $\begingroup$ @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. $\endgroup$
    – Hepdrey
    Jan 20 at 0:14
  • 2
    $\begingroup$ 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! :-) $\endgroup$
    – Sam OT
    Jan 20 at 10:10
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ How to derive the first inequality? Thanks. $\endgroup$
    – Tan
    May 28 at 19:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.