Monday 17 September 2007

ca.analysis and odes - l^p space inequality related to compressed sensing

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|_pleq 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 $midtheta_imid 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?

No comments:

Post a Comment