Coherence and sufficient sampling densities for reconstruction in
  compressed sensing
  We give a new, very general, formulation of the compressed sensing problem in
terms of coordinate projections of an analytic variety, and derive sufficient
sampling rates for signal reconstruction. Our bounds are linear in the
coherence of the signal space, a geometric parameter independent of the
specific signal and measurement, and logarithmic in the ambient dimension where
the signal is presented. We exemplify our approach by deriving sufficient
sampling densities for low-rank matrix completion and distance matrix
completion which are independent of the true matrix.
