Sensing Theorems for Unsupervised Learning in Linear Inverse Problems

Julián Tachella, Dongdong Chen, Mike Davies; 24(39):1−45, 2023.

Abstract

Learning the underlying signal model in an ill-posed linear inverse problem is necessary for solving it. However, when the model is unknown a priori, it needs to be learned from data. Unfortunately, learning the model using observations from a single incomplete measurement operator is not possible as there is no information about the signal model in the nullspace of the operator. This creates a chicken-and-egg problem: we need reconstructed signals to learn the model, but we need to know the model to reconstruct the signals. To overcome this limitation, two approaches can be taken: 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 sensing conditions for learning the signal model solely from measurement data. These conditions depend only on the dimension of the model and the number of operators or properties of the group action that the model is invariant to. By being agnostic to the learning algorithm, our results shed light on the fundamental limitations of learning from incomplete data and have implications for various practical algorithms, including dictionary learning, matrix completion, and deep neural networks.

[abs]

[pdf][bib]