MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 5 down vote accepted

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

share|cite|improve this answer
Exactly what I needed. Thanks. – Martin Leslie Jan 26 '10 at 2:33

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.

share|cite|improve this answer

I suggest to take a look at the excellent survey "nonlinear approximation" by ron devore, available at

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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