l^p space inequality related to compressed sensing

Question

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?

Answer 1

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

Answer 2

Regarding the last part of the question, I haven't looked at either of the following books myself, but I've seen them referred to for systematic presentations of the theory of quasinormed spaces (which includes $\ell^p$ with $0<p<1$):

An F-Space Sampler by Kalton, Peck, and Roberts.

Metric Linear Spaces by Rolewicz.

Answer 3

I suggest to take a look at the excellent survey "nonlinear approximation" by ron devore, available at http://pages.cs.wisc.edu/~deboor/887_98/nonlinear.ps.