Sampling Theorems for Unsupervised Learning in Linear Inverse Problems
  Solving a linear inverse problem requires knowledge about the underlying
signal model. In many applications, this model is a priori unknown and has to
be learned from data. However, it is impossible to learn the model using
observations obtained via a single incomplete measurement operator, as there is
no information outside the range of the inverse operator, resulting in a
chicken-and-egg problem: to learn the model we need reconstructed signals, but
to reconstruct the signals we need to know the model. Two ways to overcome this
limitation are using multiple measurement operators or assuming that the signal
model is invariant to a certain group action. In this paper, we present
necessary and sufficient sampling conditions for learning the signal model from
partial measurements which only depend on the dimension of the model, and the
number of operators or properties of the group action that the model is
invariant to. As our results are agnostic of the learning algorithm, they shed
light into the fundamental limitations of learning from incomplete data and
have implications in a wide range set of practical algorithms, such as
dictionary learning, matrix completion and deep neural networks.
