Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
add comment

3 Answers 3

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|improve this answer
    
Exactly what I needed. Thanks. –  Martin Leslie Jan 26 '10 at 2:33
add comment

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|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

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.