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.