Unsupervised Learning From Incomplete Measurements for Inverse Problems
Authors: Julián Tachella
Dongdong Chen
Mike Davies
Venue: NeurIPS 2022 Accept (2022)
Keywords: inverse problems
unsupervised learning
sensing theorems

Abstract: In many real-world inverse problems, only incomplete measurement data are available for training which can pose a problem for learning a reconstruction function. Indeed, unsupervised learning using a fixed incomplete measurement process is impossible in general, as there is no information in the nullspace of the measurement operator. This limitation can be overcome by using measurements from multiple operators. While this idea has been successfully applied in various applications, a precise characterization of the conditions for learning is still lacking. In this paper, we fill this gap by presenting necessary and sufficient conditions for learning the underlying signal model needed for reconstruction which indicate the interplay between the number of distinct measurement operators, the number of measurements per operator, the dimension of the model and the dimension of the signals. Furthermore, we propose a novel and conceptually simple unsupervised learning loss which only requires access to incomplete measurement data and achieves a performance on par with supervised learning when the sufficient condition is verified. We validate our theoretical bounds and demonstrate the advantages of the proposed unsupervised loss compared to previous methods via a series of experiments on various imaging inverse problems, such as accelerated magnetic resonance imaging, compressed sensing and image inpainting.

Unsupervised Learning From Incomplete Measurements for Inverse Problems
Julián Tachella
Dongdong Chen School of Engineering University of Edinburgh Edinburgh, UK chen@ed. ac
Mike Davies School of Engineering University Edinburgh Edinburgh, UK mike davies@ed.
Laboratoire de Physique
CNRS & ENSL
Lyon, France tesiianttchellaaeneee
Abstract
In many real-world inverse problems, only incomplete measurement data are avail- able for training which can pose problem for learning a reconstruction function. Indeed, unsupervised learning using a fixed incomplete mcasurement process is im- possible in general, as there is information in the nullspace of the measurement operator. This limitation can overcome by using measurements from multiple operators. While this idea has been successfully applied in various applications, precise characterization of the conditions for learning is still lacking. In this paper, fill this gap by presenting necessary and sufficient conditions for learning the underlying signal model needed for reconstruction which indicate the interplay between the number of distinct measurement operators, the number of measure- ments per operator, the dimension the model and the dimension of the signals. Furthermore, we propose novel and conceptually simple unsupervised learning loss which only requires access to incomplete measurement data and achieves a performance on par with supervised learning when the sufficient condition verified. We validate our theoretical bounds and demonstrate the advantages of the proposed unsupervised loss compared previous methods via series experiments various imaging inverse problems, such as accelerated magnetic resonance imaging, compressed sensing and image inpainting.
Introduction
In multiple sensing applications, observe measurements y E R" associated with signal x E X' C IR", through the forward process
= Ax +
(1)
where A E _ a linear measurement operator and denotes the noise affecting the measurements. This is the case of computed tomography (I]. depth ranging [2] and non-line-of-sine imaging [ to name a few. Estimating x from is generally an ill-posed inverse problem due to the incomplete
operator A with m and the presence of noise. Knowledge of the signal model is required to make this problem well-posed.
In many cases, obtaining ground-truth reconstructions x to learn the reconstruction function + might be very expensive or even impossible. For example, medical imaging, it is not always possible to obtain fully sampled images of patients they require long acquisition times. In astronomical imaging, it is impossible to obtain ground-trun truth references due to physical limitations. In electron- electron-microsse microscopy imaging [4, we can only measure 2D projections of molecule. In these settings, we can only access measurements for learning. Moreover, if the measurement process A incomplete, it is fundamentally impossible to learn the model with only measurements y, there
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

is no information about the model in the nullspace of A. Thus, we end up with a chicken-anp -ad---nd-egg problem: in order to reconstruct a we need the reconstruction function, but learn this function we require some reconstructed samples
This fundamental limitation be overcome by using information from multiple incomplete sensing operators , Ac, the general principle being that each operator can provide additional infor- mation about the signal model if has different nullspace. For example, in the image inpainting problem, Studer and Baraniuk [ used the fact that the set of missing pixels may vary between observed images to learn a sparse dictionary model and reconstruct the images. Yang et al. [ used multiple operators to learn a Gaussian mixture model in the context of hyperspectral imaging and high-speed video. Bora et al. 7 exploited this idea for learning a generative model in various imaging problems such as deblurring and compressed sensing. Matrix completion methods [8] exploit a similar principle, as the missing entries of each column (i.e., signal) are generally different. Ideally we would like to learn the reconstruction function and signal model from only a small number of different measurement operators. We are thus motivated to determine typically how many such operators are required.
The problem can be formalized as follows. We first focus on the noiseless case study the intrinsic identifiability problems associated to having only incomplete measurement data. The effect of noise will be discussed in Section 4 We assume that we observe a set of N training samples y/s where the ith signal is observed via Ag. E Rm*x one of G linear operators, i.c.,
yi = Ag. 24
where Ji E (1,.... G) and i = 1,...,,, N. While we assume that the measurement operator Ag. is known for all observed signals, it important to note that we do not know priori if two observations (yi, Ag.) ) and (yv,, Ag.:) are related to the same signal as in Noise2Noise [ There are two natural questions regarding this learning problem:
Q1. Signal Recovery Is there a unique signal x E X which verifies the measurements y Agg+? ? In
other words, is the reconstruction function f (y, Ag) + x one-to-one?
Q2. Model Identification Can we uniquely identify the signal model from measurement data alone obtained via the incomplete operators Ai....,Ac?
In general, there can be a unique solution for neither problem, just one or both. There might a unique solution for signal recovery if the model is known, but it might be impossible to learn the model in the first place (e.g., blind compressed sensing [T]). The converse is also possible, that is, uniquely identifying model without having enough measurements per sample to uniquely identify the associated signal (c.g., subspace learning from rank-1 I projections [II).
The answer to Q1 is well-known from generalized compressed sensing theory, see for example 12 Unique signal recovery is possible if the signal model is -ineenensi,nal, i.e., if Ag has m > 2h measurements, where k is the model dimension. On the other hand, Q2 has been mostly studied in the context of matrix completion, where the set of signals is assumed to lie in a low-dimensional 7 presented some results in the general setting, but only for the case where = oo which is quite restrictive. this paper, we provide sharp necessary and sufficient conditions which hold for any low-dimensional distribution (beyond línear subspaces) and only require a finite number of operators G.
subspace of R² Bora et al.
If the conditions for signal recovery and model identification are satisfied, we can expect to learn the reconstruction function from measurement data alone. We introduce a new unsupervised learning objective which can be used to learn the reconstruction function f Ag) + x, and provides performances on par with supervised learning when the sufficient conditions are met. The main contributions of this paper are as follows:
We show that unsupervised learning from a finite number of incomplete measurement operators is only possible if the model is low-dimensional. More precisely, we show that m 2 n/G measurements per operator are necessary for learning, and that for almost every set of G operators, m k + n/G measurements per operator are sufficient.
We propose a new unsupervised loss for learning the reconstruction function that only requires incomplete measurement data, which empirically obtains a performance on par with fully supervised methods when the sufficient condition > k + n/G is met.

---

A series of experiments demonstrate that our bounds accurately characterize the perfor- mance of unsupervised approaches on synthetic and real datasets, and that the proposed unsupervised approach outperforms previous methods in various inverse problems.
1.1 Related Work
Blind Compressed Sensing The fundamental limitation of failing learn signal model from incomplete (compressed) measurements data goes back to blind compressed sensing [IO] for the specific case of models exploiting sparsity on orthogonal dictionary. In order to learn the dictionary from incomplete data, [0] imposed additional constraints on the dictionary, while some subsequent papers [3 14] removed these assumptions by proposing to use multiple operators Ag as studied here. This paper can be seen as generalization of such results to more general signal models.
Matrix Completion Matrix completion consists of inferring missing entries of data matrix Y whose columns are generally inpainted samples from a fow-dimensional distribution, i.e. y/ Ag where the operators Ag. randomly select a subset of m entries of the signal z;. This problem can be viewed as the combination of model identification, i.e., identifying the low-rank subspace that the columns of [zi....., ,..,,' N] belong to, and signal recovery, i.e., reconstructing the individual columns. Assuming that the samples belong to k-dimensional subspace can be imposed by recovering rank-k signal matrix X from Y. If the columns are sampled via G sufficiently
different patterns Ag. with the same number of entries m, a sufficient condition 15 for uniquely recovering almost every subspace model
is m 2 (1-11 1/G)k + n/G.
A similar condition was shown in [16] for the of high-rank matrix completion [17. which arises when the samples T; belong to a union of k-dimensional subspaces. We show that model identification 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.
Despite providing very competitive results, most deep learning based solvers require measurements and signal pairs (2,, 9i) (or at least clean signals xι₂) in order to learn the reconstruction function y + from incomplete measurements. A first step overcome this limitation is due to Noise2Noise [9]. where the authors show that it is possible to learn from only noisy samples. However, their ideas only apply to denoising settings where there is trivial nullspace, as the operator A is the identity matrix. This approach was extended in [18] to the case where two measurements are observed per signal, each associated with a different operator. Yaman et al. [19] and Artifact2Artifact [20] empirically showed that it is possible to exploit different measurement operators learn the reconstruction function in the context of magnetic resonance imaging (MRI). AmbientGAN 7 proposed to learn a signal distribution from only incomplete measurements using multiple forward operators, however they only provide reconstruction guarantees for the case where an infinite number of operators Ag is available a condition that is not met in practice.
Deep Nets for Inverse Problems
Another line of work focuses learning using measurements from single incomplete operator. The works in 21 22 use the large system limit properties of random compressed sensing operators to learn from measurements alone. The equivariant imaging approach 23 24] leverages invariance of the signal set to a group of transformations to learn from general incomplete operators.
2 Signal Recovery Preliminaries
We denote the nullspace of A as .N. Its complement, the range space of the pseudo- pseudo-inverse At, is denoted as RA, where R, () NN = R and @ denotes the direct sum. Throughout the paper, we assume that the signals are sampled from measure μ supported on the signal set A' C R 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 x1, x2 X where 1 + x2 we have that
Ax 7 Ar
(3)
A(z x2) +
(4)
'A larger number measurements m O(k log n) is required to guarantee stable recovery when the number of patterns G is large [ Their result relies the Cramér-Wan theorem, which is discussed in Section
3

---

In other words, there is no vector 22 * 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 define the notion of dimensionality of set in IR.. In this paper, we focus on the upper box-counting dimension which is defined for a compact subset IR as
log N(,,))
boxdim( limsup sup
(5)
log
c-0
where ((S, ) is the minimum number of closed balls of radius e with respect to the norm || that are required to cover S. This definition of dimension covers both well-hehaved models such as compact manifolds and more general low-dimensional sets. The mapping x + y is one-to-one for almost every forward operator | if 25
m > boxdim (AX)
(6)
where A'' denotes the normalized secant which is defined
T2 21
AX'
{Ar E R
I1, 22 E X,
x2 # z1}.
I x1ll
The term almost every means that the complement has Lebesgue measure 0 in the space of linear measurement operators Rmxx The normalized secant set of models of dimension k generally has dimension 2k, requiring >> 2k measurements to ensure signal recovery. For example, the union of k-dimensional subspaces requires at least 2k measurements to guarantee one-to-oneness [26]. This includes well-known models such as k-sparse models (e.g., convolutional sparse coding (27)) and co-sparse models (e.g., total variation (28).. In the regime < m S 2k, the subset of signals where one-to-oneness fails is at most (2k- dimeennsiona [25]
3 Uniqueness of Any Model?
natural first question when considering uniqueness of the model is: can we recover any probability measure μ observed via forward operators . even in the case where its support X' is the full ? We show that, general, the answer is no.
Uniqueness can be analysed from the point of view of the characteristic function of μa, defined as ( (e 2) where the expectation is taken with respect to J and i = V-T is the imaginary unit. two distributions have the same characteristic function, then they are necessarily the same almost everywhere. Each forward operator provides information about subspace of the characteristic function as
Efel" Alv3 Bfelw AAAA22
(8)
=B(el(AAAwW) T3
(9)
=((AAAgw)
(10)
where Ag is a linear projection onto the subspace RA,, Given that m < n, the characteristic function only observed in the subspaces R.,, for all g E {l...., G... For any finite number of operators, the union of these subspaces does not cover the whole IR", and hence there is loss of information, i.c., the signal model cannot be uniquely identified.
In the case of an infinite number of operators G = oo, the Cramér- Wold theorem guarantees unique- ness of the signal distribution if all possible one dimensional projections (m 1) are available 29 7 However, in most practical settings we can only access a finite number of operators and many distributions will be non-identifiable.
4 Uniqueness of Low-Dimensional Models
Most models appearing signal processing and machine learning are assumed to be approximately -ww-dimeniiona, with dimension & which is much lower than the ambient dimension n. As discussed in Section 2 the low-dimensional property is the key to obtain stable reconstructions, e.g., in compressed sensing. In the rest of the paper, we impose the following assumptions on the model:
*While the bound in (6) guarantees unique signal recovery, more measurements (e.g., an additional factor of (log nı) measurements) are typically necessary in order to have siable inverse f + æ, i.e., possessing certain Lipschitz constant. A detailed discussion can be found for example in [1]

---

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 h 1.
This assumption has been widely adopted in the inverse problems literature, it is a necessary assumption to guarantee signal recovery. Our definition of dimension covers most models used in practice, such simple subspace models, union of subspaces (convolutional sparse coding models, k-sparse models), low-rank matrices and compact manifolds. It worth noting that dimension is a property of the dataset and thus independent of the specific algorithm used for learning.
In the rest of the paper, we focus on conditions for the identification of the support X instead of the signal distribution μ., due to the following observation: if there is one-to-one reconstruction function (which happens for almost every A with m > 2k as explained in Section 2 uniqueness of the support implies uniqueness of μ.. If X' is known and there is measurable one-to-one mapping from each observed measurement y to X. then it is possible to obtain as the push-forward of the measurement distribution.
Before delving into the main theorem, we present a simple example which provides intuition of how Now-dimensional model can be learned via multiple projections Ag:
Learning a one-dimensional subspace Consider a toy signal model with support X' C R which
consists of a one-dimensional linear subspace spanned by Φ [1, 1] and G 3 measurement
operators A1, A2, A3 E 2x2 which project the signals into the x(3) = 0, xx(2) = 0 and x<1)=
planes respectively, where sr(i) denotes the ith entry of the vector ær The example is illustrated
in Figure [] The first operator A₁ imposes a constraint on X, that is, every x E X' should verify (1) x(2) O. Without more operators providing additional information about X' this constraint yields plane containing X' and there are infinitely many one-dimensional models that would fit the training data perfectly. However, the additional operator A2 adds the constraint x2) xx3) which is sufficient to uniquely identify X' as
== (u E R u(1) v(2) = u(2) v(3 = 0}
is the desired I- I-dimensional subspace. Finally, note that in this case the operator Aa does not restrict the signal set further, as the constraint sr1) - xx3) = 0 is verified by the other two constraints.
&
2;
P
x - x nxn
0
x(2)
0 (=11
1
x(2)
0
(2)
0
0
x(1)
1
0 0
x(1)
Figure 1: Toy example of 1-dimensional subspace embedded in R If we only observe the projection of the signal set into the plane x=(3) = 0, then there are infinite possible lines that are consistent with the measurements (red plane). Adding the projection into the s(1) = 0 plane, allows us to uniquely identify the signal model.
The ideas from the one-dimensional subspace example can be generalized and formalized follows: for each projection Ag. we can constrain the model support X' by considering the set
X fo R
i. + u. ig E X, u E NA,3
(11)
which has dimension at most (m k). Note that the true signal model is subset of &z. The inferred signal set belongs to the intersection of these sets
x n X
(12)
gEG
which can be expressed concisely as x= {u "vER" R"I Ag -) 0, g I,.... G. G.I,,..,, X}
(13)
5

---

Even though we have derived the set X' from a purely geometrical argument, the constraints in 13 also offer simple algebraic intuition: the inferred signal set consists of the points R which verify the following system of equations
A1
A
: v
(14)
Ag
ACtC
for all possible choices of G points Ti,..., 2G in X. In other words, given dataset of N incomplete measurements {Ag.2i J it is possible to build &' by trying all the possible combinations of G sample and keeping only the points v which are the solutions of (14).
is trivial to see that X S &, but when can we guarantee X = X? As in the previous toy example, there enough constraints, e.g., if we have single A and no additional measurement operators, the inferred set will have a dimension larger than k, containing undesired aliases. In particular, we have the following lower bound the minimum number of measurements:
Proposition 4.1 (Theorem in 23 A necessary condition for model uniqueness from the measure- ment sets (Agx g=1 is that
A1
rank(
:
=
(15)
Ag
and thus 2 n/G.
Proof. In order have model uniqueness. the system in (4)) should only admit solution v= = Iι =... TG. If the rank condition in (15) is not satisfied, there is more than one solution for any choice of 21...,, IG E X.
Note that this necessary condition does not take into account the dimension of the model. As discussed in Section 3] a sufficient condition for model uniqueness must depend on the dimension of the signal set ls. Our main theorem shows that &o additional measurements per operator are sufficient for model identification:
Theorem 4.2. For almost every set of G mappings A Ag E Rmx" under assumption Al the signal model X can be uniquely recovered from the measurement sets {AgX) if the number of measurements per operator verifies m k + n/G.
The proof is included in the supplementary material. If we have large number of independent measurements are sufficient for model
operators G 2 n, Theorem 4.2 states that only m identification, which is slightly smaller (if the model is not trivial, i..., A 1) than the number of measurements typically needed for signal recovery m > 2k. this case, is possible to uniquely identify the model, without necessarily having unique reconstruction of each observed signal. However, as discussed in Section for lo < m I 2k, the subset of signals which cannot be uniquely recovered is at most (2k- m) dimeensiii.
2
Operators with Different Number of Measurements The results of the previous subsections can be easily extended the setting where each measurement operator has a different number of measurements, i.c. A E mR Xx , Ag E x In this case, the necessary condition in Proposition 4.1 > mg 2 n, and the sufficient condition in Theorem 4.2 is & E mg > k + n/G. As the proofs mirror the ones of Proposition 4.1 and Theorem 4.2 leave the details to the reader.
Noisy measurement data Surprisingly, the results of this section are also theoretically valid if the measurements are corrupted by independent additive noise i.e., = Ay + as long as the noise distribution is known and has nowhere zero characteristic function (c.g. g.,, Gaussian noise):
'Despite providing a good intuition, this procedure for estimating X' is far from being practical as it would require infinite number of observed samples if the dimension of the signal set is not trivial & 0.

---

Proposition 4.3. For fixed noise distribution, if its characteristic function there is one-to-one mapping between the space of clean measurement distributions and noise measurement distributions.
nowhere zero, then is functioo
The proof is included in the supplementary material. If the clean measurement distribution can be uniquely identified from the noisy distribution, the results in Theorem 4.2 and Proposition all also carry over to the noisy setting. Note that this only guarantees model identifiability and makes no claims on the sample complexity of any learning process.
5 Algorithms
Unsupervised algorithms mainly come two flavours: we can first learn a model X' then reconstruct by projecting measurements into this set, can attempt to directly learn the reconstruction function parameterized by a deep network.
5.1 Learn the Model and Reconstruct
Dictionary and Subspace Learning If is (approximately) union of subspaces 10 or a single we can learn a model by
subspace 8
arg min (gg A,D (i p2(z) s.D
(16)
where 01 (D) and (2(=) are regularisation terms that promote low-dimensional solutions, e-g. sparse codes if X' is union of subspaces. At test time, the dictionary is fixed and the optimization is performed over the codes only.
AmbientGAN Complex datasets are often better modelled by a generative network f R + IR" whose input is low-dimensional latent code R² The generative model can be learned using adversarial strategy, i.e.,
arg min max E (. E( E, (1-
(17)
where d : R R is the discriminator network which compares measurements in the image domain, is usually sampled from a Gaussian distribution, and (t) = log(t) for standard GANs and (t)) for Wasserstein GANs. At time, the reconstruction can be obtained by finding the latent code that best fits the measurements s(arg min, ||y A [=) 22), as in (30
5.2 Learn to Reconstruct
Another approach consists in learning directly the reconstruction function f : R x Rm*x R" whose inputs are the measurement and the associated operator Ag. and the output the reconstructed signal x. The reconstruction function can have either a denoiser form, f(y, Ag) = f(Aty) where is independent of Ag [1, steps 311.
complex unrolled structure with many denoising and gradient
Measurement Splitting Inspired by the Noise2Noise approaches 9 18]
some self-supervised
methods [19 20 split each measurement into two parts, y [y] y2 J. such that the input is yı and the target is V2- These methods can be summarised as minimising the following loss
arg min Eyy. 1B32 Ag Ag.1)l1 f
(18)
where /1 = 1g 61 and y2 Ag.2 c2. This approach suffers from the fact that f does not use all the available information in given measurement, as attempts to solve harder reconstruction problem associated with yı = Ag, + éj. As reconstruction networks often fail to generalise to operators with more measurements 32 this method can suffer from suboptimal reconstructions at test time.

---

Proposed Method The analysis in Section shows that model identifiability necessarily requires that reconstructed signals are consistent with all operators Al..... Ag. Thus, we propose an unsupervised loss that ensures consistency across all projections Ag. that is
arg (y.s) {1yy - Agf(y. A,) E. l f(A, A.)1
(19)
where a fly, Ay). The first ensures measurement consistency y Ay, Ag). whereas the second term enforces consistency across operators, i.e., [y. Ag) [v., Ag), A,) for all g o s. Crucially, the second term prevents the network from learning the trivial pseudo-inverse [V, Ag) = Aly. In practice, we choose an operator A, uniformly at random per minibatch. Thus, compared the supervised case, we only require an additional evaluation of and A, per minibatch. We coin this approach multi-operator imaging (MOI). This loss overcomes the main disadvantages of previous approaches: doesn't t require training a discriminator network, and learns to reconstruct using all the available information in each measurement
Experiments
In this section, present series of experiments where the goal is learn the reconstruction function with deep networks using real datasets. Experiments on low-dimensional subspace learning using synthetic datasets are presented in the supplementary material. All our experiments were performed using an internal cluster of 4 NVIDIA RTX 3090 GPUs with a total compute time of approximately 48 hs.
Compressed Sensing and Inpainting with MNIST We evaluate the theoretical bounds the MNIST dataset, based on the well known approximation of its box-counting dimension & ss 12 (33] The dataset contains N 60000 training samples, and these partitioned such that N/G different samples are observed via each operator. The forward operators are compressed sensing (CS) matrices with entries sampled from Gaussian distribution with zero mean and variance -1 The test set consists of 10000 samples, which are also randomly divided into G' parts, one per operator. To evaluate the theoretical bounds, we attempt minimize the impact of the inductive bias of the networks' by using a network with 5 fully connected layers and relu non-linearities.
architecture
34
35
Figure 2a shows the average test peak-signal-te cer---ignnlltt-oniiiiie noise ratio (PSNR) achieved by the model trained using the proposed MOI loss for G = 1. 10, 20, 30, 40 and m = 50, 100, 200, 300, 400. The results follow the bound presented Section 4 (indicated by the red dashed line), as the network is only able to learn the reconstruction mapping when the sufficient condition m > + n/G is verified. In sensing regimes below this condition, the performance similar to the pseudo-inverse 43.
We also evaluate the reconstruction for different number G of random inpainting masks and different rates m. The inpainting operators have diagonal structure which has zero measure in Rm*,, however our sufficient condition still provides reasonable lower bound on predicting the performance, as shown in Figure 2b is likely that due to the coherence between measurement operators and images (both operators and MNIST images sparse), more measurements are required to obtain good reconstructions than in the CS case.
40
30
3 20
20
100
200
300
400
100
200
300
400
m
(a) Compressed Sensing
(b) Inpainting
Figure Average test PSNR improvement in dB over the pseudo-inverse for the MNIST dataset using the proposed training loss, for different number of CS operators or inpainting masks and measurements per operator. The curve in red shows the necessary condition of Theorem 4.2 m > k + nn/..

---

Inpainting/CelchA
A
AmbientGAN
MOI (ours)
Supervised
9.05+1.66
19.5
34.05:13.77
36.21+3.76
Acc. MRIFastMRI
ATy
Meas. Splitting
MOI (ours)
Supervised
Denoiser f
25.77:12.71
28.72.11.64
29.51 1: 1.85
31,4511.99
Unrolled f
25.77422.71
29.47
31.39--2.17
32.42++2444
Table 1: Comparison of supervised and unsupervised learning methods for inpainting and accelerated MRI. Reported values correspond to average PSNR in dB on the testing set.
Inpainting with CelebA We evaluate the unsupervised methods in Section the CelebA dataset (36], which is split into 32556 images for training and 32556 images for testing. We use the same U-Net (see the supplementary material for more details) for MOI and supervised learning, and the DCGAN architecture 37 for AmbientGAN as in 77. We observed that using the U-Net for AmbientGAN's generator achieves worse results than the DCGAN architecture. Reconstructed test images are shown in Figure 3 and average test PSNR is presented in Table The proposed method obtains improvement of more than 4 dB with respect AmbientGAN and falls only 2.1 dB behind supervised learning.
Accelerated MRI with FastMRI Finally, consider the FastMRI dataset 38 where the set of forward operators Ag consist of different sets of single-coil k-space measurements, with 4x acceleration, i.e., m/n 0.25. We used 900 images for training and 74 for testing, which split across G = 40 operators. We compare measurement splitting, MOI and supervised learning, all using the same denoiser or unrolled architecture (see the supplementary material for details). For measurement splitting, we follow the strategy in [19], and choose to assign random subset representing 60% of the measurements Ag Ag,1 and the remaining to Ag.2. We observed that model trained with measurement splitting obtained less test error using reduced measurements associated with A instead of the full measurements Ag. so we report the best besf results using Ag, As observed in 32. the network fails to generalize to operators with more measurements. Average test PSNR is presented in T Reconstructed test images with the unrolled architecture are shown in Figure The proposed method performs better than measurement splitting while obtaining results close to the supervised setting. All training approaches obtain a better performance with the unrolled architecture than using the denoising network due to the architectural improvements.
29.05
Figure 3:
Reconstructed test images for the inpainting task using the CelebA dataset. From left to right: pseudo-inverse Aty, AmbientGAN, MOI, supervised and ground-truth. PSNR values reported in yellow.
7 Limitations
Theorem 4.2 does not cover cases where the operators Ag present some problem specific constraints (e.g., they inpainting matrices) well cases where the signal model only approximately low dimensional. Note however that Proposition 4.1 applies to constrained operators. We leave the study of sufficient conditions for these particular cases for future work. The proposed loss might be effective in problems where learning the reconstruction function is impossible, e.g., due to very high noise affecting the measurements In this particular case, it might be possible to learn a generative model as in AmbientGAN ZZ
Ussin the full measurements with the denoiser architecture obtains average test PSNR of 27.3 dB, i.e., decrease of 1.4 dB with respect the performance using Ag.1 presented in Table

---

24.13
.334
33.00
34.47
Figure 4: Examples of reconstructed test images for the accelerated MRI task using an unrolled network architecture (PGD-3). From left to right: pseudo-inved inverse ATg, measurement splitting, MOI, supervised and ground-truth. PSNR values are reported in yellow.
Conclusions
We presented sensing theorems for the unsupervised learning of signal models from incomplete measurements using multiple measurement operators. Our bounds characterize the interplay between the fundamental properties of the problem: the ambient dimension, the data dimension and the number measurement operators. The bounds are agnostic of the learning algorithms and provide useful necessary and sufficient conditions for designing principled sensing strategies.
Furthermore, we presented new practical unsupervised learning loss which learns to reconstruct incomplete measurement data from multiple operators, outperforming previously proposed unsuper- vised methods. The proposed strategy avoids the adversarial training AmbientGAN, which can suffer from mode collapse [39], and, contrary to measurement splitting, is trained using full operators Ag. Our results shed light into the setting where access to ground truth data cannot be guaranteed which is of extreme importance in various applications.
Acknowledgements
This work is supported by the ERC C-SENSE project (ERCADG-2015-64488)
References
[1] Kyong Hwan Jin, Michael T McCann, Emmanuel Froustey, and Michael Unser. Deep convolu- tional neural network for inverse problems in imaging. IEEE Transactions on Image Processing, (6(9):4509-452 2017.
[2] Joshua Rapp. Julian Tachella, Yoann Altmann, Stephen McLaughlin, and Vivek K Goyal. Advances in recent advances. IEEE Signal Processing Magazine, 37(4):62-71, 2020.
lidar for autonomous vehicles: Working principles, challenges, and
[3] Matthew O' O'Toole, David B Lindell, and Gordon Wetzstein. Confocal non-line-of-sight imaging based on the light-cone transform. Nature, 555(7696);338-31) 2018.
[4] Harshit Gupta, Thong Phan, Jaejun Yoo, and Michael Unser: Multi-CryoGAN: Reconstruction of continuous conformations in cryo-em using generative adversarial networks. In European Conference on Computer Vision, pages 429 444. Springer, 2020.
[5] Christoph Studer and Richard G Baraniuk. Dictionary learning from sparsely corrupted or compressed signals. In 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3341-3344. IEEE, 2012.
[6] Jianbo Yang, Xuejun Liao, Xin Yuan, Patrick Llull, David J. Brady, Guillermo Sapiro, and Lawrence Carin. Compressive sensing by learning gaussian mixture model from measurements. IEEE Transactions on Image Processing, 24(1): 106-1009 19, 2015.
[7] Ashish Bora, Eric Price, and Alexandros G. Dimakis. AmbientGAN: Generative models from lossy measurements. In International Conference on Learning Representations, 2018.
[8] Emmanuel J Candès and Benjamin Recht. Exact matrix completion via convex optimization. Foundations of Computational mathematics, 96))7177, 2009.
10

---

[9] Jaakko Lehtinen, Jacob Munkberg, Jon Hasselgren, Samuli Laine, Tero Karras, Mila Aittala, Timo Aila, et Noise2noise. In International Conference on Machine Learning. PMLR, 2018.
[10] Sivan Gleichman and Yonina C Eldar. Blind compressed sensing. IEEE Transactions on Information Theory, 57(10))958-6977) 2011.
[11] Y. Chen, Y. Chi, and A. J. Goldsmith. Exact and stable covariance estimation from quadratic sampling via convex programming. IEEE Trunsactions on Information Theory, 61(7):4034- 4059, 2015.
[12] Anthony Bourrier, Mike E. Davies, Tomer Peleg, Patrick Pérez, and Rémi Gribonval. Fundamen- tal performance limits for ideal decoders in high-dimensional linear inverse problems. IEEE Transactions Information Theory, 60(12):7928-794) 2014.
[13] Jorge Silva, Minhua Chen, Yonina C Eldar, Guillermo Sapiro, and Lawrence Carin. Blind compressed sensing over a structured union of subspaces. arXiv preprint arXiv:1103.2469, 2011.
[14] Mohammad Aghagolzadeh and Hayder Radha. New guarantees for blind compressed sensing. In 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1227-1234. IEEE, 2015.
[15] Daniel L Fimentel-Alarcón Nigel Boston, and Robert D Nowak. A characterization of deter- ministic sampling patterns for low-rank matrix completion. IEEE Journal of Selected Topics in Signal Processing, 10(4):623-634 636, 2016.
[16] Daniel Pimentel-Alarcon and Robert Nowak. The information- theorretcc requirements of sub- space clustering with missing data. In International Conference Machine Learning, pages 802-810. PMLR, 2016.
[17] Brian Eriksson, Laura Balzano, and Robert Nowak. High-rank matrix completion. In Artificial Intelligence and Statistics, pages 373-381 PMLR, 2012.
[18) Zhihao Xia and Ayan Chakrabarti. Training image estimators without image ground truth, In Advances in Neural Information Processing Systems, volume 32, 2019.
[19] Burhaneddin Yaman, Seyed Amir Hossein Hosseini, Steen Moeller, Jutta Ellermann, Kâmil Uğurbil, and Mehmet Akçakaya. Self-supervised learning of physics- guided reconstruction neural networks without fully sampled reference data. Magnetic Resonance in Medicine, 84(6))3172-3191, 2020.
[20] Jiaming Liu, Sun, Cihat Eldeniz, Weijie Gan, Hongyu An, and Ulugbek S Kamilov. Rare: Image reconstruction using deep priors learned without groundtruth. IEEE Journal of Selected Topics Signal Processing, 14(6): 1088-1099, 2020.
[21] Christopher Metzler, Ali Mousavi, Reinhard Heckel, and Richard Baraniuk. Unsupervised learning with stein's 's unbiased risk estimator. arXiv preprint 18055 10531, 2018.
[22] Magauiya Zhussip, Shakarim Soltanayev, and Se Young Chun. Training deep learning based image denoisers from undersampled measurements without ground truth and without image prior. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 10255-10264, 2019.
[23] Dongdong Chen, Julián Tachella, and Mike E Davies. Equivariant imaging: Learning beyond the range space. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), pages 4379-4388, October 2021.
[24] Dongdong Chen, Julián Tachella, and Mike E Davies. Robust equivariant imaging: fully unsupervised framework for learning to image from noisy and partial measurements. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 5647-5656, 2022.
[25] Tim Sauer, James Yorke, and Martin Casdagli. Embedology. Journal of statistical Physics, 65(3):579-66 616, 1991.

---

[26] T. Blumensath and M. E. Davies. Sampling theorems for signals from the union of finite- dimensional linear subspaces. IEEE Transactions on Information Theory. 55(4):1872-1882. 2009.
[27] Hilton Bristow, Anders Eriksson, and Simon Lucey. Fast convolutional sparse coding. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 391-398, 2013.
[28] Leonid Rudin, Stanley Osher, and Emad Fatemi. Nonlinear total variation based noise removal algorithms. Physica D: nonlinear phenomena, 60(1-4):259-22 268, 1992.
[29] Harald Cramér and Herman Wold. Some theorems on distribution functions. Journal of the London Mathematical Society, 1(4):290-294, 1936.
[30] Ashish Bora, Ajil Jalal, Eric Price, and Alexandros G Dimakis. Compressed sensing using generative models. In International Conference on Machine Learning, pages 537-546. PMLR, 2017.
[31] Vishal Monga, Yuelong Li, and Yonina C. Eldar. Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing. IEEE Signal Processing Magazine, 38(2):18-44 2021.
[32] Vegard Antun. Francesco Renna, Clarice Poon, Ben Adcock, and Anders C. Hansen. On instabilities of deep learning in image reconstruction and the potential costs of ai. Proceedings of the National Academy of Sciences, 117(48):0088833009 2020.
[33] Matthias Hein and Jean-Y Yves Audibert. Intrinsic dimensionality estimation of submanifolds in rd. In Proceedings of the 22nd international conference Machine learning, pages 289-296,
2005.
[34] Dmitry Ulyanov, Andrea Vedaldi, and Victor Lempitsky. Deep image prior. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 9446-9454, 2018.
[35] Julian Tachella, Junqi Tang, and Mike Davies. The neural tangent link between CNN denoisers and non-local filters. In Proceedings of the IEEF/CVF Conference on Computer Vision and Puttern Recognition (CVPR), pages 8618-8627, June 2021.
[36] Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In Proceedings of International Conference on Computer Vision (ICCV), December 2015.
[37] Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation learning with deep convolutional generative adversarial networks. arXiv preprint 1511v655 2015.
[38] Florian Knoll, Jure Zbontar, Anuroop Sriram, Matthew J. Muckley, Mary Bruno, Aaron Defazio, Marc Parente, Krzysztof J. Geras, Joe Katsnelson, Hersh Chandarana, Zizhao Zhang, Michal Drozdzalv, Adriana Romero, Michael Rabbat, Pascal Vincent, James Pinkerton, Duo Wang, Nafissa Yakubova, Erich Owens, C. Lawrence Zitnick, Michael P. Recht, Daniel K. Sodickson, and Yvonne W. Lui. fastMRI: A publicly available k-space and DICOM dataset of knee images for accelerated mr image reconstruction using machine learning. Radiology: Artificial Intelligence, 2(1 ): 190007, 2020. PMID: 32076662.
[39] Sanjeev Arora, Andrej Risteski, and Yi Zhang. Do GANs learn the distribution? some theory and empirics. In International Conference on Learning Representations, 2018.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
12

---

(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
We used existing models and datasets.
(d) Did you discuss whether and how consent obtained from people whose data you're using/curating? [Yes] All datasets considered in the paper are publicly available.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [Yes]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A] We did not use any crowdsourcing or conducted research with human subjects.
(b) Did you deseribe any potential participant risks, with links Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "mwZl0F5PI77", "reviewer": "Reviewer_AEvj", "summary": "This paper studies unsupervised learning from multiple incomplete measurements for linear inverse problems. It formulates an interesting and sound problem where observed samples $y_i$ come from multiple measurement operators but are not necessarily related to the same signal $x$. Such a problem setting is practical and widely occurred in many real-world applications such as medical, biological and scientific imaging tasks. This paper first established a theoretical framework to identify the necessary and sufficient conditions for unsupervised signal recovery, which could be viewed as a generalized results for blind compressed sensing. Then it introduces an unsupervised loss for learning from incomplete measurements, inspired from the presented theoretical results. The experiments on compressed sensing and inpainting of natural images as well as accelerated MRI consistently demonstrate the superiority of the proposed method against baselines. \n", "questions": "[Theory part]  \nThe problem formulation assumes signals are observed via G linear operators, but I don't find any claims of characterization of this set of operators. Are there any restrictions on these G operators, e.g., linear independency?\n\n[Experiment part]  \nCould the authors provide a toy example in which the proposed unsupervised learning approach can compete with the supervised one, If the sufficient conditions in theory are meet. This would make the theory more convincing. \n\n[Related work]  \nThere are more related works studying unsupervised learning scheme for inverse problems [A,B,C]. Though the formulated problem settings are different, It would be very helpful to thoughly discuss the similarities and differences. Particularly, the loss function in [A] is very similar to the proposed one. Conducting ablation study with different unsupervised settings ([A] and this paper) and same reconstruction method (UNet) would be highly attractive. \n\n[A] Training Image Estimators without Image Ground-Truth, NeurIPS 2019  \n[B] Unsupervised Learning with Stein’s Unbiased Risk Estimator, arxiv 2020  \n[C] Training deep learning based image denoisers from undersampled measurements without ground truth and without image prior, CVPR 2019  \n\nOverall it's a promising work from my perspective, and I would raise my score if the above issues could be addressed sufficiently.\n***\n**The rebuttal addresses my concerns, thus I raise my score to Accept**", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "In my sense, this is a high-quality paper with both theoretical and empirical strengths. The studied problem setting is quite attractive and promising, which should be able to be applicable to a range of inverse problems in reality. The paper itself is nicely written and organized, even in the case fueled with mathematical details. I don't see severe weaknesses, though I do have questions/suggestion which might make the paper clearer and stronger [See Questions].", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "lzruDWAtRIv", "reviewer": "Reviewer_YiZK", "summary": "This submission claims to characterize a sufficient condition (\"model\" being low dimensional) for the linear signal reconstruction problem to have the unique solution (?) in the unsupervised learning setting.", "questions": "- What is the setting of the unsupervised learning problem? There is no specification given in the submitted manuscript that clarifies this.\n\n- Can authors elaborate what 'low-dimensional models' mean in this manuscript? This is unclear in theorem 4.2.\n\n- In numerical experiment, line 288, what are the theoretical bounds authors are referring to?", "limitations": "N/A", "rating": 3, "confidence": 5, "soundness": 1, "presentation": 1, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- The narrative is unclear as there is no clear statement on the setup of the main problem under consideration.\n- It is likely that the authors mistake the term \"model\" with \"signal\".\n- The statement of main results is vague.\n- Numerical evidence is unconvincing.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "YPeEJcG8Lb", "reviewer": "Reviewer_GLHG", "summary": "This paper presents a framework for unsupervised learning for inverse problems using multiple incomplete measurement models. The authors present theoretical results on number of measurements per model and number of models required for recovery assuming low-dimensional structure on the inputs. A training loss based on cycle consistency across different operators is suggested as a practical way to train these models. Experiments are performed to validate the theory and demonstrate on applications.", "questions": "Could you use the same network architecture for AmbientGAN as you use for MOI and supervised learning? This would aid the comparison.\n\nIt would also be instructive to experimentally see the impact of noise on recovery, as well as for different numbers of measurements per operator.\n", "limitations": "The authors describe the limitations of their work sufficiently.\n", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThis paper builds off of prior work in low-dimensional signal recovery and very cleanly extends the results to fixed number of measurement operators and general low-dimensional structure. It also matches other known results like AmbientGAN for infinite measurement operators. In addition to developing a highly principled theory, the authors propose a novel and intutitive loss function that enforces a type of cycle consistency across operators. They show that this has a real effect on the result, compared to other schemes like SSDU that enforce cycle consistency across emeasurements. The paper is well written, the theory is well described, and the experimental results are strong. The \n\n\nWeakness:\nThere appears to be a disconnect between the proposed training method and the theory. In other words, no analysis, intutition, or experimental verification is provided on the multi-operator learning. The authors do not discuss or show any type of convergence results for the training method.\n\nThe authors appear to use different network architectures for AmbientGAN and MOI in the Inpainting CelebA section. This makes direct comparison difficult.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept