Compressed sensing (CS) guarantees exact object recovery (or with high probability) given a) sufficient measurements are taken in a sparse basis which is b) incoherent vis-a-vis a given object representation basis.

Does CS theory state anything about reconstruction of successively less sparse signals? That is, if I don't meet the requirements of a) can I say anything about what the reconstruction will look like? I think the answer is No from watching Candes's lectures. But I haven't read this specifically yet. I would appreciate any pointers/references.

EDIT: I think the answer, at least empirically, is shown here for Matrix Completion (long paper), where the x axis shows the sampling ratio and the y axis shows the ratio of degrees of freedom to the number of samples taken. The saw-tooth pattern between black and white areas seems interesting - perhaps suggesting that there are some sample ratios which do better at higher ranks. enter image description here

  • $\begingroup$ To be clear- are you asking if the probability of reconstruction degrades gracefully as the number of samples decreases? Or that the reconstruction quality degrades gracefully? Note that the phase transition plots represent the former. $\endgroup$ – lp251 Feb 14 '14 at 22:47
  • $\begingroup$ @LukeP Thank you for pointing out the difference. I mean to see if there is anything stated about the reconstruction quality as the sparsity decreases. $\endgroup$ – val Feb 16 '14 at 5:09

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.