Coherence and sufficient sampling densities for reconstruction in compressed sensing
This work provides a general theoretical framework for compressed sensing, which is incremental as it builds on existing coherence-based approaches to derive new bounds applicable to problems like matrix completion.
The paper tackles the compressed sensing problem by formulating it in terms of coordinate projections of an analytic variety, deriving sufficient sampling rates for signal reconstruction that are linear in coherence and logarithmic in ambient dimension, with examples applied to low-rank and distance matrix completion.
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.