Coherence and sufficient sampling densities for reconstruction in compressed sensing

We introduce a concept called coherence for signals and constraints in compressed sensing. In our setting, we assume that the signal can be observed in finitely many features, and the set of possibly observable feature combinations forms an analytic variety which models the compression constraints. We study the question how many random measurements of the feature components suffice to identify all features. We show that the asymptotics of the sufficient number of measurements is determined by the coherence of the signal; furthermore, if the constraints are algebraic, we show that in general the asymptotics depend only on the coherence of the constraints, and not on the true signal, and derive results which explain the form of known bounds in compressed sensing. 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.