It's said that $\delta_{2k} < \sqrt{2} -1$ , the solution of the $l_{1}$ problem is that of $l_{0}$ problem.

I checked the proof of $||x^{*}-x||_{l_{2}}\leq C_{0}s^{-1/2}||x-x_{s}||_{l_{1}}+C_{1}\epsilon$

in this file but I haven't found out where the $\sqrt{2}-1$ works.

So it will be very helpful if anyone could tell me if I missed something in that paper or direct me to some relevant literature or give me some tips.

  • $\begingroup$ Welcome. Could you please share how far you did check the proof? $\endgroup$ Jun 4 '19 at 22:19
  • $\begingroup$ Thanks very much, I tried to write the proof briefly and found that the inequality implicitly requires $1-\frac{\sqrt{2}\delta_{2k}}{1-\delta_{2k}}>0$ which is excatly $\delta_{2k}<\sqrt{2}-1$. $\endgroup$
    – Jue Wu
    Jun 5 '19 at 6:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.