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 suﬃcient 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.


Introduction
Inverse problems are ubiquitous in science and engineering applications such as computed tomography (CT) [1], depth ranging [2] and non-line-of-sight imaging [3]. In this paper, we consider linear inverse problems that consist of reconstructing a signal x ∈ X ⊂ R n from incomplete and noisy measurements y ∈ R m , that is y = Ax + (1) where denotes the noise affecting the measurements. This is generally an ill-posed task due to the incomplete forward operator A with m < n and the noise affecting the measurements. Classical approaches assume a signal distribution p(x) using some prior knowledge about the underlying signals. For example, the well-known total variation model [4] is built on the prior belief that natural images are approximately piecewise smooth. This approach often yields a loose description of the true model, providing biased and/or suboptimal reconstructions. In recent years, this approach has been replaced by learning p(x) directly from the data. For example, a common approach is to learn a model consisting of a dictionary of image patches using a dataset of natural images [5]. In a similar vein, it is possible to learn directly the reconstruction function y → x via deep neural networks using multiple training pairs (x i , y i ) [1]. Table 1: Examples of applications where a low-dimensional signal model is learned via multiple measurement operators or assuming that the model is invariant to a group action.
Despite the appeal and better performance of the learning-based approach, in many sensing applications we can only access incomplete measurements y i , resulting in a chicken-and-egg problem: in order to reconstruct x we need the signal model p(x), but to learn this model we require some ground truth training data x i . Moreover, if the measurement process A is incomplete, it is fundamentally impossible to learn p(x) only through measurements y i , as there is no information about the set of signals X (and thus about p(x)) in the nullspace of A. Here we show that this fundamental limitation can be overcome either by using information from multiple incomplete forward operators A 1 , . . . , A |G| or by having a single operator A and exploiting weak prior information associated with group invariance properties the signal model.
Multiple measurement operators can provide additional information about the model if the operators have different nullspaces. This idea was used in various inverse problems such as image inpainting [5], magnetic resonance imaging (MRI) [6] and hyperspectral imaging [7]. Recently, the equivariant imaging framework [8] empirically showed that learning the signal model with a single operator A is also possible if the signal model is invariant to a certain group of transformations 1 T 1 , . . . , T |G| , as they give access to multiple virtual operators AT 1 , . . . , AT |G| with possibly different nullspaces. This strategy offers an appealing way to learn the model, as most real-world signal sets present certain invariances, such as invariance to translations and rotations in images. Table 1 presents various inverse problems and related reconstruction algorithms where information in the nullspace of A is obtained using multiple measurement operators or exploiting invariance to the action of a group. Despite the empirical successes of these methods, theoretical guarantees for model identification are still lacking. What are the requirements on the measurement operators or model invariance properties? When is it possible learn the model and reconstruct the signals?
The two fundamental problems of signal and model identification can be summarised as follows: Signal Recovery Is there a unique signal x ∈ X which verifies the measurements y = Ax?
Model Identification Can we uniquely identify the signal set X and data distribution p(x) from 1 Formally, these transformations constitute the action of a group (also called the representation of a group). In general, there can be a unique solution for none of the problems, just one or both. There might be a unique solution for signal recovery if the model is known, but it might be impossible to learn the model in the first place. For example, this is the case of blind compressed sensing [14]. The converse is also possible, that is, uniquely identifying a model without having enough measurements per sample to uniquely identify the associated signal. For example, multiple rank-1 measurements y i = a gi x i (m = 1) are sufficient to identify a low-dimensional signal subspace [15,16], however it is not possible to recover the x i linked to each sample y i .
It is well-known from generalized compressed sensing theory that unique signal recovery is possible if the nullspace of A does not contain any vector in the difference set of X [17]. This condition can be achieved by low-dimensional models, i.e., where the dimension of the signal set X is both smaller than the ambient dimension n and observed measurements m. On the other hand, to the best of our knowledge, the model identification problem has been mostly analysed in the context of matrix completion [18], where X consists of a low-dimensional subspace (or union of subspaces [19]) and there are multiple A gi corresponding to different permutations of a binary mask.
In this paper, we study necessary and sufficient conditions to guarantee a unique solution to both problems for general signal models and measurement operators, only relying on their intrinsic dimension and weak prior information induced by invariance properties.

Summary of Contributions
We consider general signal models, only relying on their dimension k (the definition of dimension is made clear in Section 3.2), and study model identifiability from incomplete measurements y i associated with a finite number of measurement operators y i = A gi x i + i with g i ∈ {1, . . . , |G|}, i = 1, . . . , N , where A g ∈ R m×n and m < n. We also consider the case where we have a single operator A, i.e., y i = Ax i + i , but the signal set is invariant to the action of a group G. Our main results are: • When the dimension of the model is large, i.e., k ≈ n, the signal model cannot be uniquely identified if m < n.
• When the dimension of the model is small, k < n, model uniqueness is possible.
-We first consider the case where we obtain measurements via a set of |G| different operators A 1 , . . . , A |G| . * A necessary condition for model identification is m ≥ n/|G|. * Model identification is possible with almost every set of |G| operators A 1 , . . . , A |G| ∈ R m×n when m > k + n/|G|. -Secondly, we consider the case where we have a single operator A but the signal set is invariant to a group G. Our results are stated as a function of max j c j /s j , where c j and s j are the dimension and multiplicity of the jth irreducible representations of the group 2 . * A necessary condition for model identification for a compact group is m ≥ max j c j /s j . * We show that, if G is a cyclic group, unique model identification is possible by almost every operator A ∈ R n×m with m > 2k + max j c j + 1. As cyclic groups have all irreducibles with dimension s j = 1, the bound is equivalent to m > 2k+max j c j /s j +1. We conjecture that this last bound holds for more general groups with s j ≥ 1. * We characterize the subset of operators that fail to provide model uniqueness: If the forward operator A is itself equivariant to the action of the group, it is impossible to uniquely identify the model if m < n, even for arbitrarily small k and large number of group actions |G|.
• We experimentally show that our bounds accurately characterize the performance of popular learning algorithms on synthetic and real datasets.
As summarized in Figure 1, our results characterize the sampling regimes for model identification, complementing the existing results for signal recovery. In particular, we provide necessary and sufficient conditions for identifying a low-dimensional invariant signal model from incomplete measurements of a single operator as a function of the properties of the group. For example, consider 1D signals defined on a discrete grid of length n. We can uniquely identify a k dimensional model with invariance to cyclic shifts using m > 2k + 2 measurements, whereas for a model with invariance to reflection we can only guarantee indentifiability if m > 2k + n/2 + 1 measurements.

Related Work
Some preliminary results of this work appear in an earlier manuscript [20], which only covers the case of learning from multiple independent operators. This section discusses other related work by topic, from blind compressed sensing to deep neural networks for inverse problems.
Blind Compressed Sensing The fundamental limitation of failing to learn a signal model from compressed data goes back to blind compressed sensing [14] for the specific case of models exploiting sparsity on an orthogonal dictionary. In order to learn the dictionary from compressed observations, [14] imposed additional constraints on the dictionary, while some subsequent papers [21,22] removed these assumptions by proposing to use multiple operators A g as studied here. This paper can be seen as a generalization of such results to a much wider class of signal models.
Matrix Completion Matrix completion consists of inferring missing entries of a data matrix Y = [y 1 , . . . , y N ], whose columns can be seen as partial observations of signals x i , i.e., y i = A gi x i where the operators A gi select a random subset of m entries of the signal x i . In order to recover the missing entries, it is generally assumed that the signals x i (the columns of X = [x 1 , . . . , x N ]) belong to a k-dimensional subspace with k n. This problem can be viewed as the combination of model identification, i.e., identifying the k-dimensional subspace, and signal recovery, i.e., reconstructing 2 A detailed explanation of these concepts from linear representation theory can be found in Section 4. the individual columns. If the columns are observed via |G| sufficiently different patterns A gi with the same number of entries m, a sufficient condition [23] for uniquely recovering almost every subspace model is 3 m ≥ (1 − 1/|G|)k + n/|G|. A similar necessary condition was shown in [24] for the case of high-rank matrix completion [19], which arises when the samples x i belong to a union of k-dimensional subspaces. We show that unique recovery is possible for almost every set of |G| operators with m > k + n/|G| measurements, however the theory presented here goes beyond linear subspaces, being also valid for general low-dimensional models.
Multireference Alignment and Electron Microscopy In the multireference alignment problem [25], the goal is to reconstruct a signal x from shifted and compressed samples, i.e., (2) for i = 1, . . . , N , where the shifts T gi are a priori unknown. This problem can be generalized beyond shifts by considering transformations related to the action of a group G. This is the case of electron-microcopy imaging, where G is the group of rotations and translations of a particle [11].
The multireference alignment problem can be seen as a special case of our framework with a single operator A and a G-invariant signal set which consists of all transformations of a single signal, which has dimension 4 k = 0. If G is cyclic (e.g., shifts), our results guarantee model identification for almost every A with m > max j c j + 1 measurements.
Deep Nets for Inverse Problems Despite providing very competitive results, most deep learning based solvers require measurements and signal pairs (x i , y i ) in order to learn the reconstruction function y → x. A first step to overcome this limitation is due to Noise2Noise [26], where the authors show that it is possible to learn from only noisy data. However, their ideas only apply to denoising settings where there is a trivial nullspace, as the operator A is the identity matrix. In Artifact2Artifact [6], it was empirically shown that it is possible to exploit different measurement operators to learn the reconstruction function in the context of MRI. AmbientGAN [27] proposed to learn a signal distribution from incomplete measurements of multiple forward operators, however they only provide reconstruction guarantees for the case where an infinite number of operators is available 5 , |G| = ∞, a condition that is not met in practice. Finally, the equivariant imaging framework [8] showed empirically that learning the reconstruction function using a single operator A is possible in various imaging inverse problems when the signal model presents some group invariance.
Here we provide a theoretical framework to support all of these findings.

Signal Recovery Preliminaries
Let A † ∈ R n×m be the linear pseudo-inverse of A. We denote the range space of A † as R A . Its complement, the nullspace of A, is denoted as N A , where R A ⊕ N A = R n and ⊕ denotes the direct sum. Throughout the paper, we assume that the signals are associated with a distribution p(x) 3 A larger number of measurements m = O(k log n) is required to guarantee a stable recovery when the number of patterns |G| is large [18]. 4 For infinite but compact groups, k = dim(G). 5 Their result relies on the Cramér-Wold theorem, which is discussed in Section 3.1 supported on the signal set X ⊂ R n . Signal recovery has a unique solution if and only if the forward operator x → y is one-to-one, i.e., if for every pair of signals x 1 , x 2 ∈ X where x 1 = x 2 we have that In other words, there is no vector x 1 − x 2 = 0 in the nullspace of A. It is well-known that this is only possible if the signal set X is low-dimensional. There are multiple ways to define the notion of dimensionality of a set in R n . In this paper, we focus on the upper box-counting dimension [28,Chapter 2] which is defined for a compact subset S ⊂ R n as boxdim (S) = lim sup →0 log N (S, ) − log (6) where N (S, ) is the minimum number of closed balls of radius with respect to the norm · that are required to cover S. This definition of dimension covers both well-behaved models such as compact manifolds and more general low-dimensional sets 6 . The mapping x → y is one-to-one for almost every forward operator A ∈ R m×n if [29] m > boxdim (∆X ) where ∆X denotes the difference set defined as The term almost every means that the complement has Lebesgue measure 0 in the space of linear measurement operators R m×n . The difference set of models of dimension k generally has dimension 2k, requiring m > 2k measurements to ensure signal recovery. For example, the union of k-dimensional subspaces requires at least 2k measurements to guarantee one-to-oneness [30]. This includes well-known models such as k-sparse models (e.g., convolutional sparse coding [31]) and co-sparse models (e.g., total variation [4]). In the regime k < m ≤ 2k, the subset of signals where one-to-oneness fails is typically at most (2k − m)-dimensional [29]. While the bound in (7) guarantees unique signal recovery, more measurements are typically necessary in order to have a stable inverse f : y → x, i.e., possessing a certain Lipschitz constant. A detailed discussion can be found for example in [32].

Learning via Multiple Operators
We first focus on the noiseless case to study the intrinsic identifiability problems associated to having only incomplete measurement data. The effect of noise will be discussed in Section 5. In this section, we assume that we observe a set of N training measurement data y i , where the ith signal is observed via A gi ∈ R m×n , one of |G| linear operators with m < n, i.e., where g i ∈ {1, . . . , |G|} and i = 1, . . . , N . While we assume that the measurement operator A gi is known for all observed signals, it is important to note that we do not know a priori if two observations (y i , A gi ) and (y i , A g i ) are related to the same 7 signal x i . We assume that all operators have the same number of measurements m throughout most of this section, however we also discuss the case of different number of measurements in Section 3.3. We begin with a simple toy example illustrating this observation model: Example 3.1 (One-dimensional toy model). Consider a one-dimensional linear subspace spanned by a triangular signal φ ∈ R n , i.e., x i = c i φ ∈ X ⊂ R n with c i ∈ R, which is only partially observed through a simple masking operator, as illustrated in Figure 2. The single sensing operator does not provide information outside the observed part, thus there are infinitely many one-dimensional models that fit the observed measurements. However, if we also obtain measurements through multiple masks A gi , then identifying the model becomes feasible. In this case, solving both model identification and signal recovery problem boils down to low rank matrix completion of the measurement matrix [y 1 , . . . , y N ].

Uniqueness of Any Model?
A natural first question when considering uniqueness of the signal model is: can we recover any model p(x) observed via a finite number of forward operators A g , even in the case where X is the full ambient space R n ? We show that, in general, the answer is no. Uniqueness can be analysed from the point of view of the characteristic function of p(x), defined as ϕ(w) = E{e iw x } where the expectation is taken with respect to p(x) and i = √ −1 is the imaginary unit. If two distributions have the same characteristic function, then they are necessarily the same almost everywhere. Each forward operator provides information about a subspace of the characteristic function as Given that m < n, the characteristic function is only observed in the subspaces R Ag for all g ∈ {1, . . . , |G|}. For any finite number of operators, the union of these subspaces does not cover the whole R n , and hence there is loss of information, as the signal model is not uniquely defined.
In the case of an infinite number of operators, |G| = ∞, there is a well-known case where model uniqueness is possible: the Cramér-Wold theorem guarantees uniqueness of the signal distribution if all possible one dimensional projections (m = 1) are available [33,27]. However, in most practical settings we can only access a finite set of operators and many distributions are non-identifiable.

Uniqueness of Low-Dimensional Models
Most models appearing in signal processing and machine learning are assumed to be approximately low-dimensional, with a dimension k which is much lower than the ambient dimension n. For example, the low-dimensional property is fundamental to obtain stable reconstructions in ill-posed problems with m < n [17]. In the rest of paper, we impose the following assumption on the model:

A1
The signal set X is either (a) A bounded set with box-counting dimension k.
(b) An unbounded conic set whose intersection with the unit sphere has box-counting dimension k − 1.
This assumption has been widely adopted in the inverse problems literature, as it is necessary to guarantee signal recovery. Our definition of dimension covers most models used in practice, such as union of subspaces (simple subspace models, convolutional sparse coding models, k-sparse models), low-rank matrices and compact manifolds. The analysis in this section focuses on unique recovery of the low-dimensional support X . Even though we only focus on the support, if there is a one-to-one reconstruction function, uniqueness of the support necessarily implies uniqueness of the distribution p(x): Proposition 1. Assume there is a measurable one-to-one mapping between measurements and signals. Then it is possible to uniquely recovery the signal distribution p(x) if its support X is known.
Proof. If X is known and there is a measurable one-to-one mapping from each observed signal y i to X , then it is possible to obtain p(x) as the push-forward of the measurement distribution.
We begin with a simple example which provides important geometrical intuition of how a lowdimensional model can be learned via multiple projections A g : Consider a toy signal model with support X ⊂ R 3 which consists of a one-dimensional linear subspace spanned by φ = [1, 1, 1] , and |G| = 3 measurement operators A 1 , A 2 , A 3 ∈ R 2×3 which project the signals into the x(3) = 0, x(2) = 0 and x(1) = 0 planes respectively, where x(i) denotes the ith entry of the vector x. The example is illustrated in Figure 3. The first operator A 1 imposes a constraint on X , that is, every x ∈ X should verify x(1) − x(2) = 0. Without more operators providing additional information about X , this constraint yields a plane containing X , and there are infinitely many one-dimensional models that would fit the training data perfectly. However, the additional operator A 2 adds the constraint x(2) − x(3) = 0, which is sufficient to uniquely identify X as is the desired 1-dimensional subspace. Finally, note that in this case the operator A 3 does not restrict the signal set further, as the constraint x(1) − x(3) = 0 is verified by the other two constraints.

Bounds for Independent Operators
The ideas from Example 3.2 can be generalized and formalized as follows: for each projection A g , we can constrain the signal space by considering the set which has dimension at most n − (m − k). Note that the true signal model support is a subset of X g . The inferred signal set belongs to the intersection of these setŝ which can be expressed concisely aŝ Even though we have derived the setX from a purely geometrical argument, the constraints in (15) also offer a simple algebraic intuition: the inferred signal set consists of the points v ∈ R n which verify the following system of equations for all possible choices of |G| points x 1 , . . . , x |G| in X . In other words, given a dataset of N compressed , it is possible to buildX by trying all the possible combinations of |G| samples 8 and keeping only the points v which are the solutions of (16).
It is trivial to see that X ⊆X , but when can we guarantee X =X ? As in the previous toy example, if there are not enough constraints, e.g., if we have a single A and no additional transformations, the inferred set will have a dimension larger than k, containing undesired aliases. In particular, we have the following lower bound on the minimum number of measurements: . A necessary condition for model uniqueness is that m ≥ n/|G|.

Proof.
In order to have model uniqueness, the system in (16) should only admit a solution if v = x 1 = · · · = x |G| . If m < n/|G| there is more than one solution for any choice of x 1 , . . . , x |G| ∈ X as the matrix on the left hand side of (16) has rank smaller than n.
Note that this necessary condition does not take into account the dimension of the model. As discussed in Section 3.1, a sufficient condition for model uniqueness must depend on the dimension of the signal set k. The next theorem shows that k additional measurements per operator are sufficient for model identification: Theorem 3. For almost every set of |G| mappings A 1 , . . . , A |G| ∈ R m×n , the signal model X can be uniquely identified if the number of measurements verify m > k + n/|G|.
The proof is included in Appendix B. If we have a large number of independent operators |G| ≥ n, Theorem 3 states that only m > k + 1 measurements are sufficient for model identification, which is slightly smaller (if the model is not trivial, i.e., k > 1) than the number of measurements typically needed for signal recovery m > 2k. In this case, it is possible to uniquely identify the model, without necessarily having a perfect reconstruction of each observed signal. However, as discussed in Section 2, for k < m ≤ 2k, the subset of signals which cannot be uniquely recovered is for almost all A g at most (2k − m)-dimensional.
Operators Sharing the Same Nullspace Theorem 3 applies to almost every choice of |G| measurement operators in R m×n . However, there is a particular choice of operators where it is impossible to uniquely identify the model. Despite having measure zero in the space of |G| linear operators, it is useful to characterize this worst case scenario: Proposition 4. A necessary condition for the identifiability of the model X is that the range R Ag is not equal for all g ∈ {1, . . . , |G|}.
Proof. If R Ag = R A g for all g = g , then the system in (16) will have multiple solutions for any choice of x 1 , . . . , x G ∈ X as the matrix on the left hand side of (16) has rank m < n.

Operators with Different Number of Measurements
The results of the previous subsections can be easily extended to the setting where each measurement operator has a different number of measurements, i.e. A 1 ∈ R m1×n , . . . , A |G| ∈ R m |G| ×n . In this case, the necessary condition in Proposition 2 is |G| g=1 m g ≥ n, and the sufficient condition in Theorem 3 is 1 |G| |G| g=1 m g > k +n/|G|. As the proofs mirror the ones of Proposition 2 and Theorem 3, we leave the details to the reader.

Learning with a Single Operator and Group Symmetry
We begin with some notation on groups and their associated linear representations. A group G with multiplication denoted by · is a set of |G| elements g, such that the product of two elements is equal to another element in G (g 1 · g 2 ∈ G), G contains the identity element 1 G and the inverse of every element is contained in G, i.e., g −1 ∈ G and g · g −1 = 1 G . The action of a group in a vector space V (e.g., R n or C n ) can be represented by invertible transformations T g acting on V , where the · operation is just matrix multiplication, and the transformations are compatible with the group multiplication, i.e., T g T g = T g·g .
In this section, we assume that we observe a set of N training measurement data y i via a single A ∈ R m×n , i.e., for i = 1, . . . , N , and that the signal set X is invariant to the action of a group G, that is T g X = X for all transformations T 1 , . . . , T |G| ∈ R n×n . We do not assume that p(x) is also G-invariant, which is a more stringent condition, although this setting is still covered here as a special case. As with the multiple operator case, we first focus on the noiseless case, leaving the discussion of the effect of noise for Section 5. The invariance property provides us with a simple but powerful way learning the model with incomplete measurements [8]: for all group elements the following holds where both x i and x i belong to the signal set due to the invariance property. Equation (20) tells us that we can implicitly access |G| different measurement operators A g = AT g , each one associated with a nullspace N Ag which might differ from N A . Thus, we have a similar setting as in Section 3, with the additional constraint that the operators A g are related by some transform A g = AT g , where the transforms {T g } g∈G can be seen as the action of some group G. As the virtual forward operators A g are related by the group action, we cannot directly apply the results in Section 3, which assume that the operators are independent, and we require further analysis. The following toy example provides intuition of how the invariance can help in learning the model: Consider again the one-dimensional subspace model presented in Example 3.1. We now assume that the model is shift invariant, including all shifts of every signal, but we only partially observe signals through a fixed masking operator. While the original non-invariant set X 0 is a one-dimensional linear subspace, the full set X is now a union of linear one-dimensional subspaces g∈G T g X 0 . While X is much larger than X 0 , the intrinsic degrees of freedom are the same, i.e., the triangular wave φ. Despite having a single sampling mask, we can access to multiple virtual operators AT g via (20), as illustrated in Figure 4. Solving both model identification and signal recovery problem reduces to high rank (union of subspaces) matrix completion [19] of the measurement matrix [y 1 , . . . , y N ]. Before delving into the main results of this section, we briefly introduce some fundamental concepts of linear representation theory and discuss some common group actions.

Linear Representation Theory Preliminaries
A classical result in linear representation theory states that C n admits a unique decomposition into invariant 9 subspaces [34]: Theorem 5 (Canonical decomposition of a representation, adapted from [34]). Let G be a compact group acting on C n , whose action is represented by the invertible linear mappings T g . There is a unique canonical decomposition of C n into J invariant subspaces as where each subspace has dimension s j c j with s j the dimension of the jth irreducible representation and c j its multiplicity. Moreover, any linear representation admits a block-diagonal form where F is a basis for (21) and The matrices ρ j (g) are unique (independent of the basis F ) and correspond to the jth irreducible representation of G.
In words, a group is linked to a unique set of J irreducible representations of dimension s 1 , . . . , s J , which serve as fundamental building blocks of any linear group action. A linear group action on C n consists of a specific basis F and a set of multiplicities c j such that J j=1 s j c j = n. The vector space on which the group acts admits a decomposition into J invariant subspaces of dimension s 1 c 1 , . . . , s J c J , each associated with a different irreducible representation. To build some intuition about Theorem 5, we discuss its implications for common group actions such as shifts, reflection, rotations and permutations on 1D (e.g., audio) or 2D discretely sampled signals (e.g., images):

Finite Groups
Shifts The cyclic group of n elements associated with circulant matrices T gi which shift the signal by i taps/pixels, with i ∈ {0, . . . , n − 1}. In this case, we have |G| = J = n and c 1 = · · · = c J = 1 and s j = 1, where the subspaces are the Fourier modes. Here, F is the discrete Fourier transform and Λ is a diagonal matrix containing the Fourier transform of the discrete shift operation.
Reflection The cyclic group of 2 elements, the identity and a reflection of a 1D signal about its central entry (|G| = 2). For even 10 n, we have J = 2, where T 1 ∈ R n/2×n/2 is a reflection matrix with entries [T 1 ] i,j = 1 if i + j = n/2 + 1 and 0 otherwise, andF ∈ C n/2×n/2 is any unitary matrix.
Rotations To simplify the exposition, here we consider a 2D circular sampling pattern with n 1 pixels of diameter and angle sampled every 360/n 2 degrees (hence n = n 1 n 2 ). The cyclic group G is then represented as the set of all |G| = n 2 possible rotations. In this case, we have J = n 2 , s 1 = · · · = s J = 1 and c 1 = · · · = c J = n 1 . The matrix F is given by the Kronecker product between a 1D discrete Fourier transform along the angular dimension F 1 ∈ C n2×n2 and any unitary matrix along the radial dimension Permutations Full set of permutations of the n entries of the signal with |G| = n! elements. This group can model permutations of a masking operator, exchangeable distributions [35] or patches in an image. This is a significantly larger group (it contains all the rest as subgroups), where J = 2, s 1 = c 1 = 1 for the subspace spanned by [1, . . . , 1] and its complement s 2 = n − 1 with c 2 = 1.
Here, F is given by any unitary matrix whose first column is the constant vector [ 1 √ n , . . . , 1 √ n ] .

Infinite Groups
Natural signals are often described as continuous functions x : S → R p , where S is a compact domain and R p is the range. For example, an RGB image can be defined using S = (0, 1] 2 and p = 3. In this description, the ambient space is generally an infinite-dimensional Hilbert space H and group actions are generally continuous, such as translations or arbitrary rotations. Formally, the linear representation of a group acting on H is given by a mapping from G to the space of unitary linear mappings T g : H → H. The decomposition into invariant subspaces of Theorem 5 also holds in this setting, where the number of irreducible representations with nonzero multiplicity J can be infinite [34,Chapter 4]. However, in practice, we generally assume that the signals of interest are bandlimited and, according to Nyquist theorem, can be represented on a discrete grid associated with R n . Restricted to the bandlimited subspace, the group action 11 has a finite number of non-zero multiplicities c j and Theorem 5 holds despite the infinite number of group elements (|G| = ∞). As Nyquist theorem guarantees a one-to-one mapping between the discrete and continuous representations, we only need to prove model identifiability using signals and (possibly continuous) group actions on R n in order to prove the general case. We illustrate these concepts with two simple examples: Translations Consider the space L 2 (0, 1] of square integrable signals taking values in the (0, 1] interval where the group of translations is represented via the left action with g ∈ (0, 1], where t − g is modulo 1. This representation has s j = c j = 1 for all j ∈ Z, where each invariant subspace corresponds to the complex exponential e −i2πjt . Assuming that the signals of interest have a maximum frequency J max ∈ N, we can represent them on a grid as a vectorx ∈ R n , n = 2J max + 1, with entries given byx for r = 1, . . . , n where k(t) = sin(πtn) sin(πt) is the periodic sinc kernel (the ideal 12 anti-aliasing filter). On R n , the group action is given by diagonal matrices where j 1 < · · · < j n are the integers in [−J max , J max ], F is the discrete Fourier transform and g ∈ (0, 1]. This representation has s j = c j = 1 for all j = 1, . . . , n. It is worth noting that, restricted to a subgroup of n equispaced elements, this group action is equivalent to the discrete shifts example in Section 4.1.1.

Continuous Rotations
Consider the set of continuous signals whose domain S is the unit circle and the range is R. The signals can be written as x(r, θ) with radius r ∈ (0, 1] and angle θ ∈ (0, 2π]. The left action of the group of rotations is given by with g ∈ (0, 2π], where θ − g is modulo 2π. Assuming that the signals of interest have a maximum frequency J max1 , n 1 = 2J max1 + 1, on the radial axis and a maximum frequency J max2 , n 2 = 2J max2 + 1, on the angular axis, we can represent them as vectorsx ∈ R n1n2 on a discrete grid by sampling the convolution with the periodic sinc kernel every ∆r = 1/n 1 and ∆θ = 2π/n 2 . The action of rotations in R n1n2 has s 1 = · · · = s J = 1 and c 1 = · · · = c J = n 1 . Restricted to the subgroup of rotations by 360/n 2 degrees, the representation is equivalent to the discrete rotations example in Section 4.1.1.

Uniqueness of Any G-Invariant Model?
As with the case of multiple independent operators, we first ask the question of whether it is possible to uniquely identify any G-invariant model from measurements of a single operator with m < n, regardless of the dimension of the signal set. We show that even under the more stringent assumption that p(x) is also G-invariant (i.e., not only the support X ), uniqueness is not possible if the support has dimension close to the ambient dimension. If p(x) is G-invariant, all points in the same orbit, O x , defined as will necessarily have the same probability. Hence, the distribution is uniquely identified by the distribution over the orbits O x , instead of the whole space C n . This notion is made precise by a fundamental theorem of invariant statistics: Theorem 6 (Decomposable measures [35]). A G-invariant distribution on C n can be decomposed into a uniform distribution over the elements in G and a distribution over the quotient space C n /G.
The theorem tells us that we can potentially design a measurement operator with m < n which is one-to-one with respect to the quotient space (having model uniqueness) but not necessarily oneto-one with respect to the signal space (failing to have signal recovery). For infinite compact groups, the quotient space might be significantly smaller than the full signal space. For example, consider distributions which are invariant to the action of the orthogonal group O n composed of all orthogonal matrices. These are necessarily isotropic distributions only dependent on the radius x . In this case, the full space is n-dimensional, but the quotient space is only one-dimensional (the sufficient statistics are functions of x ), and (non-linear) one-dimensional measurements A(x) = x are sufficient to identify any G-invariant distribution. On the other hand, the orbits of finite groups 13 , which are the main focus of this paper, are sets of a finite number of signals, and the quotient space is intrinsically n-dimensional: Theorem 7 (Dimension of quotient space [36]). The quotient space C n /G of any finite group acting on C n is n-dimensional.
As C n /G is n-dimensional for any finite group, any forward operator A ∈ C m×n with m < n cannot be one-to-one on C n /G, hence some invariant distributions will not be unique. Despite not being able to learn any model, we show that, as in Section 3, uniqueness among low-dimensional models is possible.

Low-Dimensional G-Invariant Models
The observation in (20) tells us that G-invariant models provide access to |G| (virtual) operators AT g with g ∈ G. Thus, we can apply similar ideas to those used in Theorem 3 to analyze the problem of learning a G-invariant model, with the additional constraint that the operators are G-related. Instead of depending on the ratio between ambient dimension n and the number of transformations |G|, the bounds depend on the largest ratio of multiplicity and dimension of the irreducible components of the group action (as defined in Theorem 5), that is With this definition in mind, we begin by reformulating the necessary condition in Proposition 2: Proposition 8. Let G be a compact group. A necessary condition for model uniqueness with oper- The proof is detailed in Appendix C, and similarly to the proof of Proposition 2, requires analysing the rank of the matrix (or its infinite dimensional equivalent for infinite groups) with the additional constraint that A g = AT g . Note that for any group action n/|G| ≤ max j c j /s j ≤ n, hence this is always a more restrictive bound than the one in Proposition 2. The following two examples present group actions where max j c j /s j n/|G|:  We now study a sufficient condition for unique model identification. As we have that max j c j /s j ≥ n/|G|, one might be tempted to extrapolate the bound in Theorem 3, and expect that m > k + max j c j /s j measurements are sufficient for model identification. However, the following counterexample shows that this is not always sufficient: Example 4.4. Let G be the group of reflection with 2 elements {e, r} of a signal with even length n (see Section 4.1.1). Consider the representation given by T e = I n where I n is the n × n identity matrix and Note that the representation has J = 2 invariant subspaces with s 1 = s 2 = 1 and c 1 = c 2 = n/2. Let X be the set of d-sparse signals where n > 2d. This conic set has dimension k = d − 1 according to the definition in Section 3.2. In order to have model uniqueness, we require that the inferred signal setX defined in (15) equals the true set X , or equivalently that their differencê is empty. This condition can be written in matrix form as wherex 1 = T e x 1 andx 2 = T r x 2 are d-sparse and thus also belong to the signal set X . Let Setting a i = 2v n/2+i , b i = −2v n/2+d+i for i = 1, . . . , d and v j = 0 for j = n/2 + 2d + 1, . . . , n, we have that [ . . , v n/2+2d , 0, . . . , 0] . Hence, condition (34) can be simplified toÃ whereÃ is a m × (n/2 + 2d) submatrix of A. Thus, the condition in (36) can only hold for all [v 1 , . . . , v n/2+2d ] ∈ R n/2+2d − {0} if m ≥ n/2 + 2d. As this linear representation has max j c j /s j = n/2, and k = d − 1, we have m ≥ max j c j /s j + 2k − 2.
Our main theorem shows that, for a cyclic group, 2k + 1 additional measurements are actually sufficient to guarantee model uniqueness for almost every A: Theorem 9. Let G be a compact cyclic group acting on R n . For almost every A ∈ R m×n , the signal model X can be uniquely identified from measurements {AT g } g∈G if the number of measurements verify m > 2k + max j c j + 1. In particular, a G-invariant signal model can be learned from measurements of almost any operator A ∈ R m×n if m > 2k + max j c j + 1.
The proof is detailed in Appendix C. As all the irreducibles of a cyclic group have dimension s j = 1 [34], the bound can also be expressed as m > 2k + max j c j /s j + 1. Unlike the case of multiple independent operators, having enough measurements to guarantee model identification also guarantees unique signal recovery due to the additional k measurements. However, the experiments in Section 7 suggest that m > 2k+max j c j /s j measurements are only required in worst-case scenarios such as Example 4.4, whereas m > k + max j c j /s j are required for typical models.
Although Theorem 9 is specific to actions of cyclic groups, it can be applied to any group action, as all groups contain at least one cyclic subgroup. For example, if the group action consists of the composition of rotations and reflection, which is not cyclic nor abelian, we can apply Theorem 9 by only considering rotations or reflection, which are cyclic when considered separately. However, if the cyclic subgroup is significantly smaller than the full group, Theorem 9 might not be tight. Nonetheless, we conjecture that the bound in Theorem 9 holds for any compact group: Conjecture 10. Let G be any compact group acting on R n . For almost every A ∈ R m×n , the signal model X can be uniquely recovered from measurements {AT g } g∈G if the number of measurements verify m > 2k + max j c j /s j + 1. In particular, a G-invariant signal model can be learned from measurements of almost any operator A ∈ R m×n if m > 2k + max j c j /s j + 1.
The almost every property can be hard to interpret in practical scenarios. A simple example of matrices that will hold this property with probability 1 are compressive sensing matrices (e.g., iid random Gaussian entries). However, there is an important subset of measurement operators of measure zero in R m×n that do not verify this property and are treated in the next subsection.

Equivariant Measurement Operators
In order to obtain additional information in the nullspace of A, Proposition 4 requires that the measurements operators AT 1 , . . . , AT |G| do not share the same nullspace. Operators which fail to bring information in the nullspace of A possess the property of being G-equivariant: Theorem 11. The set of forward operators {AT g } g∈G share the same nullspace for all g ∈ G if and only if A is an equivariant map, i.e., it verifies for all g ∈ G, whereT g : G → C m×m is a linear representation of G acting on C m . Moreover, any equivariant linear operator can be decomposed as A =F ΛF −1 , where F is the basis associated to the group representation in Theorem 5,F is any basis of C m and Λ ∈ C m×n has the following  Figure 5: Identification of models with continuous signals and group actions. Continuous signals are well described as points in an infinite dimensional Hilbert space H, and symmetries in the model are described as a (continuous) group acting on H. As discussed in Section 4.1.2, if the signals are bandlimited, we can represent them on a discrete grid R n . Nyquist theorem ensures equivariant mapping is one-to-one and we have a valid group action on R n . Theorem 9 guarantees that we can uniquely identify the model from measurement data alone via almost every (thus non-equivariant) mapping A with m > 2k + max j c j + 1 measurements if |G| is a cyclic group.

block-diagonal structure
wherec j are the multiplicities of the representationT g , such that m = J j=1 s jcj . The proof is detailed in Appendix C. This necessary condition has important practical implications, as equivariant operators appear often in real-world settings which are discussed in next subsection.
We end this subsection with a remark concerning continuous signals and groups actions (see Figure 5) defined in an infinite-dimensional Hilbert space. As discussed in Section 4.1.2, bandlimited signals x can be represented in R n on a discrete grid after an anti-aliasing filter. This procedure is an equivariant mapping, as we have a valid linear representation of the group acting on R n . Contrary to the grid sampling step, the measurement process A should be non-equivariant in order to be able to uniquely identify the model from measurement data alone.

Consequences for Common Group Actions
We discuss the implications of Theorem 9 and Theorem 11 for the group actions introduced in Section 4.1. Reflection As this is a small group, in order to guarantee model identification our theory requires m > 2k + n/2 + 1 measurements, significantly more than those needed for signal recovery.

Translations/Shifts
Rotations If we consider signals defined on the unit circle and a 2D radial sampling pattern with n 1 pixels of diameter and angle sampled every 360/n 2 degrees (hence n = n 1 n 2 ), we have max j c j /s j = n 1 and thus need m > 2k + n 1 + 1 for model identification, which is also more than measurements required for signal recovery. General rotations of a Cartesian grid require some degree of interpolation for off-of-grid values. Thus, this set of transformations do not form an exact group action in general. However, if the signals are sufficiently band-limited and supported within a radius from the center, the Cartesian grid can be approximated by the radial grid, and thus we need m > 2k + n 1 + 1 measurements.
Rotations are useful for learning the signal model in inverse problems which depend on Fourier measurements, as long as these measurements are not of circular stripes of Fourier space, as illustrated in Figure 6. Two important examples where learning is possible are limited angle CT [8] and accelerated MRI [9], as the Fourier patterns are generally not rotationally invariant.

Rotations by 90 degrees and Reflection
Consider the non-commutative group of 8 elements whose action is composed of 90 degree rotations and reflection of a 2D signal defined on a regular grid. The action of this group can always be represented by permutation matrices. This group action has max j c j /s j ≈ n/8 for large n. We conjecture that m > 2k + n/8 + 1 measurements are sufficient for model identification, significantly more than the case of rotations of a radial grid.
Permutations Group of all permutations of n entries which has max j c j /s j = 1. Note that the previous examples are subgroups of this group. In this case, signal recovery also guarantees model identification. The only equivariant measurement operator which does not provide additional information is the constant vector A = α[1, . . . , 1] with α ∈ R.

Noisy Measurement Data
Surprisingly, the results of this paper are also theoretically valid if the measurements are corrupted by independent additive noise , i.e., y = A g x + , as long as the noise distribution is known and has a nowhere zero characteristic function (e.g., Gaussian noise): Proposition 12. For a fixed noise distribution, if its characteristic function is nowhere zero, then there is a one-to-one mapping between the space of clean measurement distributions and noise measurement distributions.
Proof. Consider the noisy measurements associated to the gth operator A g , as z = y + , where z are the observed noisy measurements, y are the clean measurements and is additive noise (independent of y). The characteristic function of the sum of two independent random variables is given by the multiplication of their characteristic functions, i.e., ϕ z (w) = ϕ y (w)ϕ (w) (39) where ϕ z , ϕ y and ϕ are the characteristic functions the noisy measurement, clean measurements and noise distributions, respectively. If the characteristic function of the noise distribution is nowhere zero, we can uniquely identify the characteristic function of the clean measurement distribution as The clean measurement distribution is fully characterized by its characteristic function ϕ y (w). We end the proof by noting that the same reasoning applies to the measurements of every operator A g with g ∈ {1, . . . , |G|}.
If the clean measurement distribution can be uniquely identified, we can then apply Theorem 3 and Propositions 2 and 4 for the case of independent operators, and Theorems 9 and 11 and Proposition 8 for the case of G-related operators. Note that this only guarantees model identifiability and makes no claims on the sample complexity of any learning process.

Algorithms
In this section, we summarize some different approaches for solving (one or both) model identification and signal recovery problems. We recall the learning settings:

Multiple operators
We observe N measurement vectors y i , each associated with one out of |G| operators, y i = A gi x i + i , where A gi is known and x i ∈ X .
Single operator, G-invariant model We observe N measurement vectors y i , associated with a single (known) operator, y i = Ax i + i , and assume that the support of the signals X is G-invariant.

Learning a Generative Model
One approach is to first learn the low-dimensional support X and then reconstruct the signals. This can be done in practice by estimating a low-dimensional semi-parametric modelX , while satisfying measurement consistency: arg min For example, low-rank matrix completion algorithms [37,18] assume that the signal set (columns of the matrix) consists of a k-dimensional linear subspace. Sparse subspace clustering with missing entries methods [12,38] assume that the signal set is a union of low-dimensional subspaces. These approaches are closely related to k-sparse dictionary learning approaches [5], which can also be trained using only incomplete measurements. These union of subspace models are also closely related to a mixture of Gaussians with low-rank covariances, which can also be used to learn from incomplete measurements [7].
In some inverse problems, a direct inversion y → x might be hard to obtain due to large amounts of noise affecting the measurements. In this setting, it might be possible to identify the signal distribution from incomplete data, without recovering each individual signal. For example, the signal distributionp(x) can be modelled with a generative deep network. This strategy can be applied in learning problems with independent operators, G-structured operators or G-invariant signal sets with a single operator.
The case of multiple operators is summarized as follows. Let q data g (y) be the empirical measurement distribution of observations linked to the gth operator. The learning strategy can be written as arg min where (y|A g x) denotes the distribution of measurements given A g x (i.e., the likelihood), and d(·, ·) is a (pseudo) divergence, which is also generally learned using generative adversarial networks (GANs). This approach has been adopted by AmbientGAN [27] for various imaging problems. The case of a single operator and a G-invariant model follows a similar learning strategy: arg min s.t.q(y) = (y|Ax)p(x)dx (46) p(x) is G-invariant (47) where q data denotes the empirical distribution of the observations. This approach has been adopted by Cryo-GAN [11] for the cryo electron-microscopy problem.

Learning to Invert
If we observe signals through multiple forward operators, an alternative approach consists of directly learning the reconstruction function f : (g, y) → x without explicitly learning the signal model. To this end, we can use the following training loss: The family of functions F is some parameterized function space which captures the low-dimensionality of the signal set X (e.g., a deep neural network with an autoencoder architecture). Without the low-dimensional constraint on F, we can have f (g, y) = A † g y which is a minimizer of (48) but fails to learn the signal set. For example, we can choose f (g, y) = φ(A † g y) where φ(·) plays the role of a denoiser function (independent of the forward operator) which projects A † g y to a low-dimensional set X . More generally, the network architecture can be an unrolled optimization algorithm [39] which incorporates the forward operator A g and a denoiser subnetwork which is operator independent, e.g., acting as a (low-dimensional) proximal operator in the unrolled algorithm.
In cases where the model is assumed to be G-invariant, the reconstruction function f : y → x can be learned by enforcing that the composition of the forward operator and reconstruction f • A yields a G-equivariant mapping on X . To this end, we can enforce approximate equivariance via the following training loss: This strategy was proposed in the equivariant imaging framework [8]. In [8], the authors also consider adding an adversarial network to try to impose similarity between the estimated sample signal model X and its transforms T gX . The equivariant imaging loss in (49) can be extended to handle noisy measurements [9] using Stein's unbiased risk estimator [40].

Experiments
We perform a series of numerical experiments to illustrate the theoretical bounds presented in Sections 3 and 4.

Low-Dimensional Subspace Model
We consider the problem of learning a k-dimensional subspace model from compressed observations, where the signals x i are generated from a standard Gaussian distribution on the low-dimensional subspace. We first evaluate the case where each observation y i is obtained by randomly choosing one out of |G| operators A 1 , . . . , A |G| ∈ R m×n , each composed of iid Gaussian entries of mean 0 and standard deviation n −1/2 . In order to recover the signal matrix X = [x 1 , . . . , x N ], we solve the following matrix completion problem arg min X X * (51) where · * denotes the nuclear norm. A recovery is considered successful if i xi−xi 2 i xi 2 < 10 −1 , wherê x i is the estimated signal for the ith sample. We use a standard matrix completion algorithm [37] to solve (51). The ambient dimension is fixed at n = 50, and the experiment is repeated for k = 1, 10, 40. For each experiment we set N = 150k in order to have enough samples to estimate the subspaces. Figure 7 shows the probability of recovery over 25 Monte Carlo trials for different numbers of measurements m and operators |G|. The reconstruction probability exhibits a sharp transition which follows the generic sufficient condition m > k + n/|G| of Theorem 3.
Second, we perform the same experiment using the G-related operators A g = AT g . Figure 8a shows the probability of correct recovery for the group of shifts, where max j c j /s j = 1, whereas Figure 8b shows the recovery probability for the reflection group where max j c j /s j = n/2. In both cases,  Figure 7: Reconstruction probability of a k-dimensional subspace using compressed measurements arising from |G| independent operators for different k. The curve in red shows the bound of Theorem 3, m > k + n/|G|. the transition in probability of recovery follows m ≈ k + max c j /s j , i.e., requiring approximately k less measurements than the sufficient condition of Theorem 9. As discussed in Section 4.3, it is likely that these additional k measurements are only required in worst-case scenarios such as Example 4.4.

MNIST via Multiple Operators
We next consider the problem of directly learning the reconstruction function f θ : (g, y) → x using measurements from multiple compressed sensing operators, as described in Section 6.2. We train a network that aims to achieve data consistency for all the training data via the unsupervised loss in (48). We use the standard MNIST dataset which has an approximate box-counting dimension k = 12 [41]. The dataset contains N = 60000 training samples, and these are partitioned such that N/|G| different samples are observed via each operator. The entries of the forward operators are sampled from a Gaussian distribution with zero mean and variance n −1 . The test set consists of 10000 samples, which are also randomly divided into |G| parts, one per operator. We define f θ (g, y) = φ θ • A † g where φ θ : R n → R n is a trainable network whose aim is to map A † g y to the signal set X . The networks are trained using the Adam optimizer.
When evaluating the ability of neural networks to perform unsupervised learning from incomplete data it is necessary to ensure that we are not just observing the inductive bias of the network, which has been shown can provide a powerful image model without any training [42,43]. In order to  Table 2: Average PSNR in dB achieved by a residual network and a non-residual network for the MNIST reconstruction task with |G| = 40 operators, each with m = 100 measurements.
minimize the impact of the inductive bias of the networks' architecture, we use fully connected layers which do not exploit any spatial image prior. It is easy to see that a valid solution to the optimization problem in (48) is just the identity φ θ (x) = x. This reflects the fact from the theory that in general the problem is not solvable and that we need to impose a low dimensional prior on the signal. To avoid learning the identity, we require that φ θ (x) exploits the low-dimensionality of the signal set, so we use an autoencoder architecture with 3 hidden layers with 1000, 32 and 1000 neurons, as shown in Figure 9. We use relu non-linearities between layers, except at the output of the last layer.  Table 2 shows the performance for the case of |G| = 40 operators with m = 100 measurements each for φ θ (x) being (i) the identity, (ii) the autoencoder with a residual connection which allows it to learn the identity mapping and (iii) the autoencoder with no residual connection which enforces a low-dimensional representation. The network with residual connection fails to learn, obtaining a similar performance to the simple pseudo-inverse, whereas the autoencoder without residual obtains a significant improvement of more than 10 dB. This is in line with our theory where we have seen that a requirement for unsupervised learning from incomplete measurements is that the model is low dimensional. We next explore the ability of the autoencoder without residual connection to perform unsupervised learning as a function of the number of operators |G| and measurements m. Figure 10a shows the average test peak-signal-to-noise ratio (PSNR) achieved by the trained model for |G| = 1, 10, 20, 30, 40 and m = 1, 100, 200, 300, 400. The results follow closely the bound presented in Section 3.2 which is indicated by the red dashed line, as the network is only able to learn the reconstruction mapping when the sufficient condition m > k +n/|G| is verified. In sampling regimes below this condition, the performance is similar to simply applying the pseudo-inverse A † g . Figure 10b shows examples of reconstructed images for networks trained with different number of operators and measurements.
Second, we replace Gaussian operators for |G| different random inpainting masks. The inpainting operators have a diagonal structure which has zero measure in R m×n , however our sufficient condition still provides a reasonable lower bound on predicting the performance, as shown in Figure 11a. It is likely that due to the coherence between measurement operators and images (both operators and MNIST images are sparse), more measurements are required to obtain good reconstructions than in the case of Gaussian operators. Figure 11b shows examples of reconstructed images for different number of operators and measurements.

G-Invariant MNIST
Lastly, we consider the problem of learning a G-invariant version of the MNIST dataset from compressed measurements using deep convolutional neural networks. In this setting, the goal is to learn the reconstruction function x i = f (y i ) where f is a trainable network. In order to learn from measurement data alone, we leverage the equivariant imaging approach of Section 6.2. This technique has been very successfully applied to large scale CT and MRI imaging problems [8,9]. Here we demonstrate on a simple example that it also respects the measurement bounds presented in this paper. As in [8,9], we compare 4 learning algorithms: • Pseudo-inverse: Reconstruction by applying the pseudo-inverse to the observed measurements y i = A † x i (baseline of no learning).
• Supervised: Standard training using ground truth pairs (x i , y i ).
• Unsupervised equivariant: Training from only compressed measurements y i . In order to enforce G-invariance of the reconstructed signal set, we use the equivariant training loss of (49).
• Unsupervised: Training from only compressed measurements y i without enforcing G-invariance of the reconstructed signal set.
In order to generate a G-invariant dataset, we augment the standard MNIST dataset by applying the transformations associated with the group action. In all cases, we use a single forward operator A with iid Gaussian entries, and the U-Net network of [8].
First, we evaluate the group of horizontal and vertical shifts. This is an abelian group with irreducibles of dimension s j = 1, however it is not cyclic. As max j c j /s j = 1 for this group action, assuming Conjecture 10 holds, we expect that both supervised and unsupervised methods are able to reconstruct as long as m > 2k + 1. Figure 12 shows the reconstructed images and test peakto-signal ratio (PSNR) for different compression ratios m/n. The unsupervised method with no equivariance fails to learn for all m, converging to the linear pseudo-inverse. When the number of measurements is not enough for reconstruction, i.e., m/n < 2k/n ≈ 0.03, both supervised and unsupervised methods fail. For m/n > 0.07, the unsupervised equivariant method is able to perform as well as the fully supervised one as expected. There is an intermediate regime 0.03 < m/n < 0.07 where the supervised method performs better than the unsupervised equivariant. While there are enough measurements for model uniqueness, this discrepancy might be attributed to not having enough measurements for stable model identification. Secondly, we evaluate the group of 90 degree rotations and reflection, which has |G| = 8 elements. This is a not a cyclic group (nor abelian) which is not covered by Theorem 9. However, we can obtain a bound from Theorem 9 by considering the cyclic subgroup of 90 degree rotations. The full group action has max j c j /s j = 0.134n, whereas the (biggest) cyclic subgroup has max j c j /s j = 0.25n. In both cases, the unsupervised equivariant method cannot achieve the same performance as the supervised one for small m. Figure 13 shows the reconstructed images and test PSNR for different compression ratios m/n. As expected, the unsupervised method with no equivariance fails to learn for all m, converging to the linear pseudo-inverse. For m ≥ 0.2n, both supervised and unsupervised equivariant perform equally well. This result is aligned with Conjecture 10, as the full group action offers a tighter sufficient condition of m > 0.16n, in comparison to the condition associated with the biggest cyclic subgroup, m > 0.28n.

Conclusions and Future Work
We have presented fundamental bounds for learning models from incomplete measurements, either by using multiple measurement operators, or by exploiting a group symmetries of the signal set. Our bounds characterize the interplay between the fundamental properties of the inverse problem: the ambient dimension, the signal model dimension, and the number of measurement operators or symmetry of the model. Moreover, the bounds are agnostic of the learning algorithms and provide useful necessary and sufficient conditions for designing principled sensing strategies.
We leave the study of robustness to noise as well as the extension of the theory for future work. Another interesting avenue of research is to extend our results to more general semigroups, whose elements do not necessarily have an inverse, but can be useful to capture certain symmetries in the signal model such as invariance to scale [44,45].
where G α maps z ∈ S ⊂ R n(|G|+1) to R m|G| . Let α = [vec(A 1 ) , . . . , vec(A |G| ) ] ∈ R mn|G| , then as a function of α we can also write (55) as where we used the 'vec trick' in (52). As v does not belong to the signal set, the matrix on the left hand side of (57) has rank m|G| for all z ∈ S. We treat the cases of bounded and conic signal sets separately, showing in both cases that, for almost every α ∈ R mn|G| , the condition in (57) holds for all z ∈ S if m > k + n/|G|: Bounded signal set Decompose S into a countable union of bounded subsets S = ρ≥1 S ρ defined as where boxdim (S ρ ) ≤ k|G| + n. Thus, Lemma 13 states that for almost every α all z ∈ S verifies (57) if m > k + n/|G|.

Conic signal set
If the signal set is conic, then S is also conic. Let B be a bounded set B containing an open neighbourhood of 0. As boxdim (S ∩ B) ≤ |G|k + n, Lemma 13 states that for almost every α, all z ∈ S verifies (57) as long as m > k + n|G|.

C Proofs for G-invariant models
We next present a lemma which will be useful for the proofs of Proposition 8 and Theorem 9.

Lemma 14.
Let v ∈ C n and let the decomposition of v into the J invariant subspaces of a G-action can be written as: where v j ∈ C sj corresponds to the th copy out of c j multiplicities of the jth invariant subspace. We The result also holds for infinite compact groups by replacing the sum over the group with an integral.
Proof. Without loss of generality, we assume that the linear representation of G is block-diagonalized in the canonical basis (F in Theorem 5 equals the identity). Using the 'vec trick' in (52) and the decomposition of v into invariant subspaces, we have .
where the last line defines R j := [v 1 j , v 2 j , . . . , v cj 1 ] ⊗ I sj ∈ C sj cj ×s 2 j for j = 1, . . . , J. Using this decomposition, we can compute the (j, j ) block of g∈G T g vv T g as where the middle term can be evaluated using the orthogonality relations of irreducible representations [34, Chapter 2]: Considering all blocks, we have 14 1 For infinite compact groups acting on C n , we can obtain the same result by replacing the sum over the group by an integral [34,Chapter 4], where the orthogonality relations are given by Proof of Proposition 8.
14 For complex matrices M , M denotes the conjugate transpose.
Proof. We begin with the case of finite groups, and then extend it to infinite (but compact) groups.
In order to have model uniqueness it is necessary that the matrix has rank n. This matrix contains the orbits of the measurement vectors {a i } m i=1 (the rows of A). Letting R = 1 |G| M M and using Lemma 14, we have where M ai ∈ C n× j s 2 j is the block-diagonal matrix in (61) associated to a i . Note that rank(M ) = rank(R) = rank([M a1 , . . . , M am ]). Furthermore, due to the block-diagonal structure of the submatrices M ai , [M a1 , . . . , M am ] can also be rearranged in block diagonal form with blocks of size s j c j × ms 2 j . Thus, M has rank n only if all the blocks verify ms 2 j ≥ s j c j , which yields the bound If the group has infinite elements, the matrix in (69) is not well-defined as it would have infinite entries. However, as the decomposition into finite invariant subspaces and Lemma 14 still hold, we can compute the dimension of the subspace spanned by {T g a i } g∈G,i=1,...,m with (70) by replacing the finite sum over group elements by an integral and obtain the bound m ≥ max j c j /s j .
We now present two useful technical lemmas for proving Theorem 9.
Lemma 15. Let T ∈ R n×n be the linear representation of the generator of a finite cyclic group of order |G|. Let v ∈ R n and B ∈ R n×r+1 with r + 1 ≤ n, such that M = B − [T v, . . . , T r+1 v] has rank r and the first r columns are linearly independent. The set Ω ⊂ R n of v verifying the rank assumption is contained in an affine variety of dimension at most r + j∈J c j where c j denotes the multiplicity of the jth irreducible representation of the group action and J is a subset of r out of |G| irreducibles.
Proof. By assumption, M = B − [T v, . . . , T r+1 v] has rank r. All (r + 1) × (r + 1) minors of matrices with rank at most r are necessarily zero. Minors are given by polynomial equations on the entries of M . Thus, the (at most) rank-r condition on M can be translated into a set of polynomial equations on v which must equal zero. As the zero set of polynomial equations, the subset of v ∈ R n which verify this constraint is a variety [46]. We will use these polynomial equations to show that this set has dimension at most r + j∈J c j where J is a subset of r out of |G| irreducibles. The polynomials depend on both B and v, thus the v-variety will vary smoothly as a function of B. In order to simplify the analysis, we study the set of complex v ∈ C n that verify the rank condition, noting that the set of real v ∈ R n is just a subset of the complex setting.
Using Theorem 5, the matrix M can be written as where we use the index j i to indicate the irreducible representation associated with the ith row. For example, if J = 2 and c 1 = c 2 = 2, we have that j 1 = j 2 = 1 and j 3 = j 4 = 2. Moreover, as we are dealing with cyclic groups, we have that ρ j (g) = e −i2πjg/|G| [34,Chapter 5].
By assumption, there is at least one r×r invertible submatrix within the first r columns. Without loss of generality, we assume that this submatrix is given by the first r rows. For any other choice of rows, the results are identical with a re-indexing. We then consider the n − r minors of size (r + 1) × (r + 1) corresponding to the first r + 1 columns together with the first r rows and the ith row: for i = r + 1, . . . , n. Applying Laplace's expansion on the last row of each minor, we have that r+1 g=1 where µ 1 , . . . , µ r+1 are the determinants of r × r matrices which only depend on the first r + 1 columns of B and v 1 , . . . , v r . Let µ = [µ 1 , . . . , µ r+1 , 0, . . . , 0] ∈ C |G| , where µ g = 0 for all g > r + 1. Note that µ cannot be identically zero, as µ r+1 = 0 is the determinant of the submatrix with the first r columns and rows, which is invertible. The equations can be rewritten as whereμ j = |G| g=1 ρ j (g)µ g are the jth coefficient of the discrete Fourier transform of the vector µ (which has at most r + 1 consecutive nonzero elements) and d i = r+1 g=1 B i,g µ g . For all i ∈ {r + 1, . . . , n} whereμ ji = 0, we have v i = d i /μ ji in order to satisfy the rank-r constraint. As the Fourier transform of a vector with at most r + 1 non-zero elements which are consecutive has at most r zero coefficients [47,Lemma 5], we have that at most r coefficientsμ j = 0. As eachμ j is repeated at most c j times in (77), there are at most j∈J c j zeros along the diagonal in (77), where J is a subset of r out of |G| irreducibles. Locally, we are free to vary the first r components v 1 , . . . , v r without changing the rank of the submatrix. From (77), we are also free to locally vary at most j∈J c j components of the remaining v i associated with the zero set ofμ ji . Hence, the set of v that verifies the rank-r constraint has a dimension equal or smaller than r + j∈J c j .
Lemma 16. For any infinite compact cyclic group G 1 acting on R n , there is a finite cyclic subgroup G 2 ⊂ G 1 such that the restriction of the linear representation of G 1 to G 2 has the same multiplicities of the irreducible representations.
As the v-variety has a smooth dependence on x 1 , . . . , x r+1 by Lemma 15, for each subset S 2,r, ,i , we can build a smooth locally Lipschitz mapping f : S 2,r, ,i ⊂ R n(r+2) → R n(r+2) such that f (S 2,r, ,i ) has a simple product structure {0} n−d × (0, 1) d × (W ∩ X r+1 ) where W is local neighborhood of R n(r+1) (see [28,Chapter 7]). As a Lipschitz mapping does not increase the box-counting dimension of a set [48], we have boxdim (S 2,r, ,i ) ≤ boxdim {0} n−d + boxdim (0, 1) d + boxdim W ∩ X r+1 (91) ≤ r + j∈J c j + k(r + 1) for both bounded and conic signal sets X . As we have rank(Φ z,r ) = r, according to Lemma 13, for almost every A ∈ R m×n there is no z ∈ S 2,r, ,i which verifies AΦ z,r = 0 as long as m verifies mr > k(r + 1) + where the last inequality is obtained by using r ≥ 1 and uses the fact that |J | = r. As the countable union of events of measure zero have measure zero, then for almost every A ∈ R m×n with m > 2k + max j c j + 1, all z ∈ S 2,r verifies AΦ z = 0 for all possible ranks r.
Proof of Theorem 11.
Proof. We need to show that the following statements are equivalent: (i) The range space of (AT g ) † is the same for all g ∈ G.
(ii) A is a G-equivariant map.
(iii) A can be decomposed as A =F ΣF −1 where Σ has the block-structure in Theorem 5.
We first prove (i) =⇒ (ii). Let V ∈ R m×n be an orthogonal basis for the range space of A † , such that A = M V where M ∈ R m×m is an invertible matrix. Due to (i), we have where Q g ∈ R m×m is an orthogonal matrix and U g = M Q g M −1 ∈ R m×m is invertible. The mapping g → U g is a valid linear representation (e.g., see [34, Chapter 1]) as we have that for any two group elements g and g , U g·g A = AT g·g = AT g T g = U g AT g = U g U g A and thus U g·g = U g U g . As we have U g A = AT g where U g and T g are two linear representations of G, A is an equivariant map.
We now prove (ii) =⇒ (i). Using the decomposition A = M V and (ii) we have whereŨ g =T g M is an invertible matrix. As A and AT g share the same right singular vectors given by the matrix V , they have the same range space for all g ∈ G.
The proof of (ii) ⇐⇒ (iii) follows from Theorem 5 and is a standard result of linear representation theory which can be found in, for example, [49] and [50].