I'm trying to read Donoho's 2004 paper Compressed Sensing and am having trouble with a supposedly trivial statement (equation 1.2 on page 3).


He makes the sparsity assumption on $\theta \in \mathbb{R}^m$ that for some $0<p<2$ and $R>0$ we have $\|\theta\|\_p\leq R$. Then if $\theta\_N$ denotes $\theta$ with everything except the $N$ largest coefficients set to $0$ he claims that $\| \theta-\theta\_N \|\_2 \leq \zeta\_{2,p} \cdot \| \theta \|\_p \cdot (N+1)^{1/2-1/p}$ for $N=0,1,2,\ldots$ where $\zeta\_{2,p}$ depends only on $p$.


I've tried writing out the definitions of various things. I've noticed that the $N$th largest coefficient must satisfy $\mid\theta\_i\mid \leq RN^{-1/p}$ but I can't figure out how the result above follows.


I'm also having some difficulty thinking about $\ell^p$ spaces with $0<p<1$, in particular knowing what results from the $p>1$ theory apply. Does anyone know some good notes or a book that covers this?



l^p space inequality related to compressed sensing
Suppose that $\|\theta\|\_p=1$. Then, as you correctly observed, if we drop $N$ largest coefficients, we'll have $|\theta\_i|\le N^{-1/p}$ for all the remaining ones, whence $|\theta\_i|^2\le N^{-(2-p)/p}|\theta\_i|^p$. Now just add those inequalities up, use the fact that $\sum\_i|\theta\_i|^p\le\|\theta\|\_p^p=1$ and raise both parts to the power $1/2$.


