Where prior learning can and can't work in unsupervised inverse problems
Authors: Benoît Malézieux
Florent Michel
Matthieu Kowalski
Thomas Moreau
Venue: Submitted to ICLR 2023 (2023)
Keywords: Inverse problems
unsupervised learning
dictionary learning
Deep Image Prior
Plug and Play

Abstract: Linear inverse problems consist in recovering a signal from its noisy observation in a lower dimensional space. Many popular resolution methods rely on data-driven algorithms that learn a prior from pairs of signals and observations to overcome the loss of information. However, these approaches are difficult, if not impossible, to adapt to unsupervised contexts -- where no ground truth data are available -- due to the need for learning from clean signals. This paper studies situations that do or do not allow learning a prior in unsupervised inverse problems. First, we focus on dictionary learning and point out that recovering the dictionary is unfeasible without constraints when the signal is observed through only one measurement operator. It can, however, be learned with multiple operators, given that they are diverse enough to span the whole signal space. Then, we study methods where weak priors are made available either through optimization constraints or deep learning architectures. We empirically emphasize that they perform better than hand-crafted priors only if they are adapted to the inverse problem. 

Under review as a conference paper at ICLR 2023
WHERE PRIOR LEARNING CAN AND CAN'T WORK IN UNSUPERVISED INVERSE PROBLEMS
Anonymous authors Paper under double-blind review
ABSTRACT
Linear inverse problems consist in recovering a signal from its noisy observation in lower dimensional space. Many popular resolution methods rely on data-driven algorithms that learn a prior from pairs of signals and observations to overcome the loss of information. However, these approaches are difficult, if not impossible, to adapt to unsupervised contexts - where no ground truth data are available due to the need for learning from clean signals. This paper studies situations that do or do not allow learning prior in unsupervised inverse problems. First, we focus on dictionary learning and point out that recovering the dictionary is unfeasible without constraints when the signal is observed through only one measurement operator. It can, however, be learned with multiple operators, given that they are diverse enough to span the whole signal space. Then, we study methods where weak priors are made available either through optimization constraints or deep learning architectures. We empirically emphasize that they perform better than hand-crafted priors only if they are adapted to the inverse problem.
INTRODUCTION
Linear inverse problems are ubiquitous in observational science such as imaging (Ribes & Schmitt, 2008), neurosciences (Gramfort et al., 2012) or astrophysics (Starck, 2016). They consist in recon- structing signals X E RaxN from remote and noisy measurements Y E R mxx which are obtained as linear transformation dimension m of Y is usually much smaller than the dimension n of X, these problems are ill-posed, and several solutions could lead to a given set of observations. The uncertainty of the measurements, which can be noisy, increases the number of potential solutions. Therefore, practitioners rely on prior knowledge of the data to select a plausible solution among all possible ones.
Rm" of X, corrupted with noise RM=N; Y = AX + B. As the
On the one hand, hand-crafted priors relying sparsity in basis produce satisfying results on specific data, such as wavelets in imaging or Gaborlets audio (Mallat, 2008). However, the complexity and variability of the signals often make ad hoc priors inadequate. On the other hand, the prior can be learned from ground truth data when available. For instance, frameworks based on Plug-and-Play (Brifman et al., 2016) and Deep Learning (Chan et al., 2016; Romano al., 2017; Rick Chang et al., 2017) propose to integrate a pre-trained denoiser in an iterative algorithm to solve the problem. Supervised methods leveraging sparsity also allow summarize the structure of the signal (Elad, 2010). In particular, dictionary learning (Olshausen & Field, 1997; Aharon et al., 2006; Mairal et al., 2009) is efficient on pattern learning tasks such as blood cell detection MEG signals analysis (Yellin et al., 2017; Dupré la Tour et al., 2018). Nevertheless, these methods require clean data, sometimes available in audio and imaging but not in fields like neuroimaging or astrophysics.
While data-driven methods have been extensively studied in the context of supervised inverse problems, recent works have focused on unsupervised scenarios and provided new algorithms to learn from corrupted data only (Lehtinen et al., 2018; 8018; Bora et al., 2018; Liu et al., 2020). Chen et al. (2021) and Tachella et al. (2022) demonstrate that a necessary condition to learn extensive priors from degraded signals is either to measure them with multiple operators which span the whole space, or to introduce weak prior knowledge such as group structures and equivariance in the model when only operator is available. Other works based on Deep Learning have leveraged successful architectures to recover images without access to any ground truth data. In particular, Deep Image Prior shows that CNNs contain enough prior information recover image in several

---

Under review as a conference paper at ICLR 2023
inverse problems, such as denoising or inpainting (Ulyanov et al., 2018). Finally, few works have demonstrated that it is possible to learn dictionaries from incomplete data, especially in the context of missing values inpainting in imaging (Szabó et al., 2011; Studer & Baraniuk, 2012; Naumova & Schnass, 2017). Another line of work studied online factorization of large matrices by aggregating partial information randomly selected from the data at each iteration (Mensch et al., 2016; 2017). This is equivalent to learning dictionary from incomplete data, except that one sample can be looked multiple times from different angles, which is hardly possible in an inverse problem context.
Contributions In this paper, we demonstrate practical limitations of prior learning methods for unsupervised inverse problems. We first provide an analysis of dictionary learning when the data is measured with single multiple operators. As mentioned by Tachella et al. (2022), "seeing the whole space" is a necessary condition to learn a good prior from the data, as nothing can be recovered in the kernel of the operator A. However, we point out that this is not sufficient in the case of dictionary learning. Indeed, the problem is made harder by the measurement operators, and is sometimes unfeasible even with access to the whole space. Then study the practical behavior of methods heavily relying on convolutions in cases where they work well (inpainting) and in cases where they fail because the prior is too weak (deblurring), and provide experiments complementary to the theoretical study of Tachella et al. (2022). We present three examples, namely Convolutional Dictionary Learning. Deep Image Prior, and Plug and Play, and train the prior "as is" in the range space without relying on any data augmentation technique or equivariance. Finally, we show that the difficulty is deeper than the unsupervised setting by studying what happens in self-supervised setting when training on ground truth data. In particular, we emphasize that stronger prior information necessary to link low and high frequencies in deblurring, even in this simpler context.
THE MAIN BOTTLENECK OF PRIOR LEARNING IN INVERSE PROBLEMS
For inverse problems, the dimension of the measurements m often smaller than the dimension of the signal n. This dimension reduction implies that information on the signal contained in the null space of Rmxx lost during the observation process, and needs to be reconstructed from the observed signal. We first aim to study the impact of this degradation on constraint-free prior learning through the lens of dictionary learning.
2.1 DICTIONARY LEARNING WITH A SINGLE MEASUREMENT OPERATOR.
Dictionary learning assumes that the signal can be decomposed into a sparse representation in redundant basis of patterns - also called atoms. In other words, the goal is to recover the signals X E RaxN as DZ where E R are sparse codes and D E RR* L is a dictionary. Taking the example of Lasso-based dictionary learning, recovering X would require solving problem of the form
min ZER DEC
|IADZ - + + 11
where À is regularization hyperparameter and C is set of constraints, typically set so that columns of D have norm smaller than 1. We first aim to see the impact of A on the algorithm ability to recover proper dictionary. In Proposition 2. we focus on inpainting where the measurement operator is a binary mask or equivalently a diagonal matrix with m non-zeros elements.
Proposition 2.1. Let A diag( (A1, (A1,-.. An) Rax be a diagonal measurement matrix where m n. X 2 2 Am > 0 and Am+1 = An = O. Let Do E RRx and D' be such that
[Do.mml T Do.i. On-m
|Pa I
Du,m
D'
where Do (o,n-m)
1SiSL
Then
1 min 2 |AD'Z 21 + + S min 1 | 2
-V12 + |
All proofs deferred Appendix C. In this simple case, our proposition shows that the optimal dictionary must be 0 in the null space of A. The core idea behind the proof is that due to invariances, the optimal solution for dictionary learning is contained in equivalence class (PSD' + V) where
2

---

Under review as a conference paper at ICLR 2023
P is a permutation matrix, S is scaling matrix, D' is matrix of rank and V is matrix of rank n - m such that PSD' E ker(A)) and V E ker(A). Given a dictionary PSD' + V in this equivalence class, the dictionary PSD' is always a better minimizer after proper rescaling. Therefore, the solver puts to O all directions from which A loses the information to maximize the input from the others. Proposition 2.2 generalizes Proposition 2.1 the case of rectangular matrices.
Proposition 2.2. Let E Rm be a measurement matrix where m n, and let Y e RRmx be the observed data. Ifa dictionary D axL minimizes minzERLEK REREEERXX,,DECC DDEC IIADZ - Y + A 11 then D E ker(A)-
Similarly to what happens in inpainting, nothing can be recovered in the null space of A. Thus, we can only expect learn dictionary of rank m with a single measurement matrix. This result relates to the one from Tachella et al. (2022) which says that the signals cannot be recovered where there no information.
Dimension reduction makes dictionary learning harder in the range space. Even in the range space of the signal, good dictionary cannot always be learned reliably. Guarantees of identifiability of the dictionary or local recovery are strongly based on the ability of the sparse coding algorithm to recover an accurate estimation of Z (Arora et al., 2015; Gribonval et al., 2015; Chatterji & Bartlett, 2017). As the dimension of the measurement m becomes smaller than the dimension of the signal n, these conditions are valid anymore. As example, D is a Gaussian random dictionary, the theory of compressed sensing states that 2s In( + where is the sparsity of Z is a sufficient condition to be able to recover Z with high probability (Foucart Rauhut, 2013). When the dictionary degraded by matrix A, this constraint becomes m 2 2s In( L) and the sparsity level s has decrease by ratio close to in to compensate for the loss of information. This implies that recovering the part of the dictionary not contained the null space of A also becomes harder with the corruption of the data.
1.0
0.8
Rec. score
Sparsity
0.03
0.6
0.1
0.4
0.3
0.2
20
40
60
80
100
Dim.
Figure 1: Recovery score for Gaus- sian dictionaries 100 x 100, after degradation by single compressed sensing operator m x 100. When the dimension m decreases. the part of the dictionary not contained in the null space can be recovered only with sparse signals.
Fig. shows the recovery score for data generated with a 100 x 100 random Gaussian dictionary, depending on the size of the measurements and on the sparsity of a Bernoulli Gaussian signal, after degradation by a single compressed sensing operator. We compare it to the perfect score that quality of the dictionary, based on the Pearson correlation of their columns. To make the metric sign and permutation invariant, use best linear assignment S(C) max > (Ca(s)al where G, is the group of permutations of [1, ni] and C' is the cost matrix whose entry i, compares the atom i of the first dictionary and j of the second. is equal to when the dictionary is perfectly recovered. The recovery score drops when the dimension decreases and small values of m require a high sparsity level to recover the dictionary in the range of A.
achieve in the range space of the operator. We evaluate the
2.2 SEEING THE DATA THROUGH MULTIPLE OPERATORS
Even though it not possible to recover the whole dictionary from single measurement operator, the situation changes when the mcasurement matrix is sample dependent. Indeed, several operators may span different parts of the signal space and make possible to recover the missing part of the signal. In this section, focus on cases where the data observed through set of Nm, measurement matrices (At) and consider the task of learning a dictionary with the associated lasso-based (Tibshirani, 1 1996) optimization problem
1 IA,DZA YII A IIZA,
min F(Z)(D), DEC with
2
i=1
1
ZA. (D) = arg min
|A,DZ - x2l + 1211,
7
2
3

---

Under review as a conference paper at ICLR 2023
Compr. sensing
1.0
Weighted score Inpainting
Rec. score
0.9
Dim. m
PSNR (dB)
inpainting
25
observation
reconstruction
0.9
20
0.8
0.8
15
0.7
0.7
100
10
0.6
1
2
3
4
0.1 0.3
0.5 0.7 0.9
0.1 0.3 0.5 0.7 0.9
Number of matrices
Prop. of missing pixels
Prop. of missing pixels
Figure 2: (left) Recovery score for Gaussian dictionaries 100 100, after degradation by Nm. compressed sensing operators m X 100. Nm 2 [ + is necessary, but not sufficient to recover the dictionary when m is too small. In the case of inpainting, PSNR (center) and weighted recovery score (right) depend on the proportion missing values in dictionary learning on patches from a natural image. When the dimension of the measurement space is large enough, the algorithm recovers the image and the supervised dictionary successfully.
Here ZA(D) (D), ANx (D)) denotes the sparse codes related each operator. This problem is non-convex and is usually solved through gradient descent, in order to find a local minimum. In the following, we study the cases when the local minima of Eq. (2) are also local minima for the problem without observation operators and provide an empirical analysis in different scenarios. With multiple measurement operators, the gradient of Eq. (2) is given by
N
V F(A(()))), D) = Σ
-Y)
The main difficulty in studying this quantity is that the sparse codes estimate Z (D) depends on D and A, Each operator provides measurements from a limited number samples in the data-set, and the sparse codes are different with and without A. Thus, we consider the simplest case where Z = AA, (D) is the same for all A,, including = This is an easier problem than the general formulation in Eq. (2). If this is not feasible, then Eq. (2) is not feasible. In this case, we have
(D), D) E At F))
KKT conditions imply that the gradient V (D)(Z D) must vanish local minima. Whenever >; AT A; is injective, Vn FDr D) vanishes if and only if V F(z((z()),)) vanishes. Thus, local minima of Eq. (2) also local minima for the original problem where A; 4 This means that when Σ. Af" A, spans the entire space, the dictionary from the original problem can be recovered. Otherwise local minima of (D), D) are not necessarily local minima of F (D), This case boils down to the case previously studied in Section 2, as Σ, A, A, is full rank whenever the rank of the matrix obtained by stacking the operators (AT ... AT is equal to n. The message from these results essentially the same as the one from Chen et al. al. (2021): a necessary condition for recovery is that the operators span the whole space. It is however important to note that this is only a necessary condition to recover the dictionary, as sparse coding guarantees may not be met when the dimension m is too small. We now present two examples of inverse problems with multiple operators to illustrate what happens in practice.
Compressed sensing (CS). When all A, are random Gaussian matrices, (AT. ... AA, is also random Gaussian matrix of dimension x N.m. Therefore, it is of rank with probability 1 if + 1. Fig. 2 illustrates that it indeed a necessary condition to recover D, but is not sufficient when is too small, because sparse coding becomes inefficient. Multiview compressive dictionary learning has also been studied in Anaraki & Hughes (2013); Pourkamali-Annn Anaraki et al. (2015); Chang et al. (2019).
Nm 2 m
Inpainting. All A, are binary masks with coefficients following Bernoulli distributions of param- eters Pl," ,Pn, i.e. A; diag(a!, a.") where each af is equal to with probability Pj. The rank of (Af, ... AT N..) is equal if for each coordinate j there exists an index such that of =
4

---

Under review as a conference paper at ICLR 2023
This happens with probability (1-p;) Fig. A in appendix shows that similar to CS, this is necessary but insufficient condition to recover proper dictionary. Even when the number of samples compensates for missing values, the sparsity of the data plays a great role in the ability of the algorithm to recover the proper dictionary after heavy dimension reduction. To illustrate what happens on real data, we consider the example of image inpainting. Let A E {0, 1 be a binary mask used to observe image X E [0, 1] 1|<x" and Y A O X be the observed image. While the operator is unique when we consider the whole image at once, learning a dictionary from patches of size n from the image equivalent to learning dictionary with multiple operators in Eq. (2). Denoting the i, j-patch, patch-based
(1
Aij = diag( (ni:m((+1,,nn. dictionary learning solves
and Yig= = vect() Seet(yniinee
min Σ I14, Zzg DEC (,
Yus Yu +
111
(5)
The dictionary should be recovered if the image is large enough and if there are not too many masked pixels. In Fig. 2, we show the PSNR (Peak Signal to Noise ratio) and the recovery score depending on the proportion of missing values in an image of resolution 128 128, from which we extract patches of size 10 x 10. To take into account that some atoms might not be as relevant as others, the score re-weighted by the sum of corresponding activations in the sparse codes Z see Appendix A.3 for details. The recovery score drops when the proportion of missing values is larger than 50%. Otherwise, the image is successfully recovered even when the dictionary learned from the degraded observation. This is why dictionary learning led to good results in unsupervised inpainting in the literature (Szabó et al., 2011; Studer & Baraniuk, 2012; Naumova & Schnass, 2017).
We have demonstrated that dictionary learning won't 't operate in the null space of the measurement matrix. However, the usage of multiple operators allows for mitigating that issue, the whole signal space being seen through different matrices A, Our experiments with synthetic and real data also show that this is only a necessary condition to learn a good dictionary. In some cases, the sparse codes cannot be recovered as the information is too degraded. Reducing the dimension of the observations could then be a hard limit to dictionary learning, and theoretical results on the convergence of classical optimization methods such Alternating Minimization would be of great interest ensure the identifiability of the dictionary with multiple operators. In the following, we show that well chosen weak prior knowledge can lift the problem and allow to recover the information from the kernel space of a single operator through the example of convolutions in imaging.
3 WEAK PRIOR KNOWLEDGE THROUGH CONVOLUTIONS
The usage of convolutions in Deep Learning (LeCun et al., 1998) has encountered tremendous success in broad range of tasks from image classification to reconstruction. Convolutions and convolutional neural networks are efficient to analyze translation invariant data while reducing the number of parameters to be learned. In this section, we provide elements understand the efficiency and the limitations of convolutions used as weak prior knowledge for unsupervised image reconstruction through the study of three methods based on prior learning: Convolutional Dictionary Learning (Grosse et al., 2007), Plug and Play (Chan et al., 2016) and Deep Image Prior (Ulyanov et al., 201 8). All computations have been performed on a GPU NVIDIA Tesla V100-DGXS 32GB using PyTorch (Paszke et al., 2019).'
Convolutional dictionary learning (CDL) consists in learning kernels of relatively small dimensions from a signal Y. Lasso-based CDL solves a problem of the form
1 2
min zy da
Σ
du =k
Y
Σ |
Deep Image Prior (DIP) takes advantage of CNN architectures to project the observed image into a well-suited range space by drawing random code vector in the latent space and optimizing the parameters of the network f as follows
min Y - Afo(=)112
(7)
'Code is available in the supplementary materials.
5

---

Under review as a conference paper at ICLR 2023
PSNR full space
PSNR kernel space
PSNR range space
CDL _op__suee
35
CDL
30
30
TV
25
25
25
Wavelets
20
20
20
15
15
DIP
0.1
0.3
0.5
0.7
0.9
0.1
0.3
0.5
0.7
0.9
0.1
0.3
0.5
0.7
0.9
35
35
30
PSNR
25
25
25
Supervised PnP
20
20
20
Unsupervised PnP
15
15
15
0.3 0.5
0.5
0.5 0.7 0.9
Prop. missing pixels
Prop. missing pixels
Prop. missing pixels
Figure 3: PSNR depending on the proportion of available pixels in the full space, kernel space, and range space of the masking operator for reconstruction methods based on CDL., DIP, TVV, and wavelets for the 256 x 256 grey-level image in Fig. 4 (top), and for PnP based reconstruction on 160 160 grey-level images (bottom) with SNR of 20db. Unsupervised prior learning methods work better than hand-crafted methods even with a lot of lacking information and can recover missing information in the kernel space. Moreover, they perform close supervised methods (CDL supervised and PnP supervised) when the ratio of missing pixels is not too high.
Plug and Play (PnP) an iterative algorithm inspired from proximal gradient descent, which recovers images from an observation Y with steps of the form
X fo (X,, -A" (Y)
Vn 2
(8)
where Xy = 0, is a step size and fo is an image denoiser. CDL and DIP can be applied to a single observation without training data set, the prior being learned directly data without needing other information. In contrast, PnP usually resort to deep denoiser generally pre-trained on clean database. As focus the unsupervised setting, adapt PnP by training the denoiser on degraded data instead. In this case, we consider that we have access to a dataset (Yi) where each Y; AX; + E; is observation of an original image X, degraded by the same operator A and gaussian noise eş. We artificially generate noisy images (siNn from our data-set of observations Y Y,+ c, and we train DnCNN (Zhang al., 2017) recover Y, from Y! in the range space of A by minimizing
piece of degraded
min N
Σ [AAJ))Y))))))))))))))))))))))) XX)
The idea is to check in which case the architecture can compensate for the lack of information in the kernel of A by learning from the information in the range space of A. To point out the limits of these prior learning algorithms, we will compare them two reconstruction methods based Total Variation (TV) (Chambolle et al., 2010) and sparse wavelets (Mallat, 2008).
The purpose highlight the hard limits of unsupervised methods in various contexts. Therefore, we evaluate the performance reached by each algorithm over oracle hyper-parameters, namely irper-parameters leading to the best performances. While evaluating hyper-parameter sensitivity necessary when comparing differentt methods, it is orthogonal our study, which considers the difference between supervised and unsupervised training of similar methods.
3.1 WHY CONVOLUTIONS ARE LIKELY TO WORK ON TASKS LIKE INPAINTING
Works prior learning in unsupervised inverse problems often evaluate the performance of the methods they propose on an inpainting task (Ulyanov et al., 2018; Chen et al., 2021) and achieve very good performance compared supervised learning techniques. Here, we provide elements to understand why this problem, in particular, is feasible with the help convolutional dictionaries or neural networks without access ground truth data.

---

Under review as a conference paper at ICLR 2023
Original
Observation
CDL
DIP
Wavelets
TV
Figure 4: Reconstruction and PSD of 256 x 256 RGB image with 50% missing pixels in noiseless scenario. PSNR: CDL 34,8dB, DIP 34. IdB, Wavelets 34.7dB, TV 34.3dB. The PSD reveals the presence of ringing artifacts in the reconstruction by CDL. Otherwise, unsupervised algorithms recover the whole spectrum of the original image and do as well as hand-crafted methods.
Learning convolutional dictionaries from incomplete data. To understand what happens in inpainting, let's consider simple one-dimensional signal example. Let X, be wide sense stationary (WSS) random process, and let A, be an i.i.d Bernoulli process of mean p. The observed signal Y, A,X, is also WSS random process and its auto-correlation function Ry (T)
(T) X = Rx(+)E[AAA+++)
(10)
[x) + pfx())
(11)
Then, the density of X and Y are proportional. This shows that with sufficient samples in the signal, the masking process won't affect the spectrum of the original signal X, and translation invariant priors can take advantage the information from all frequencies.
theorem assures that the power spectral
6 8
4
4 0
3
7
7
4
8
8
7
7
Digits recovery
We illustrate the practical implication of this observation on the ability of CDL to recover 10 digits from an image, depending on the size of the image and the rate of available pixels p in Fig. 5. As expected, the performance increases with the size when is not too low. It is essential to note that having access all frequencies only sparse coding
0.9
Score
0.8
tho
necessary condition to learn good dictionary, assumptions are not met when there are too many missing values. Of course, these results do not stand for non-stationary signals.
0.7
100
200
Image size
Unsupervised reconstruction. Similar effects can be observed for reconstruction. Natural images are stable enough to allow convolution-basele algorithms to learn from all frequencies that are present in the signal. Fig. 3 presents natural image is degraded by a random binary mask and gaussian noise and reports the PSNR of the reconstruction in the mask kernel space and range space for CDL, DIP, and methods based on TV and sparse wavelets for different rates missing pixels with SNR of 20dB. Other experiments with different values of SNR are available in appendix in Fig. C. Supervised means the algorithm learns a prior on the clean signal and uses for reconstruction after degradation, whereas unsupervised means that the prior is learned directly on the observation. The experiments highlight that unsupervised methods work as well as supervised CDL and are better than hand-crafted priors in the kernel of A when the noise level is not too high (SNR > 20). They succeed in learning in the range space of A and generalizing in the kernel space. The PSNR drops in favor of TV and wavelets when the noise increases, it becomes more challenging to lear the structure of the signal. Fig. 4 provides a visual example the noiseless case. Unsupervised algorithms successfully recover the original image after degradation by binary mask with 50% pixels missing. The PSD shows that
Figure 5: The recovery score of CDL depends on the image size and the pixels p. Increasing the size improves the quality at high enough rates.
example where single
of available
7

---

Under review as a conference paper at ICLR 2023
SNR full space
SNR kernel space
SNR range space
CDL _op__siee
35
35
35
CDL
25
25
25
TV
SNP
20
20
Wavelets
DIP
10
10
10
0.1
0,3
0.5
0.7
0.9
0.1
0.3
0.5
0.7
0.9
0.1
0.3
0.5
0.7
0.9
35
35
35
5NR (dB)
30
30
30
25
25
25
Supervised PnP
15
15
15
Unsupervised PnP
10
10
10
0.5 Sigma blurr
0.5
0.7
Sigma blurr
Sigma blur
Figure 6: SNR depending on the size of the blur in the full space, kernel space, and range space of the blur operator for reconstruction methods based on CDL, DIP, TV, and wavelets for th 256 x 256 grey-level image Fig. 7 (top), and for PnP based reconstruction on 160 160 grey-level images (bottom) with a SNR of 20db. This time, unsupervised prior learning methods fail to recover information in the kernel space. More surprisingly, supervised PnP and CDL also struggle in the kernel space.
Original
Observation
DIP
Wavelets
TV
Figure 7: In noiseless scenario, reconstruction and PSD of a 256 x 256 RGB image blurred by gaussian kernel. PSNR: CDL 31.9dB, DIP 31.7dB, Wavelets 34.6dB, TV 32.7dB. The PSD clearly shows that nothing learned in high frequencies compared to what was obtained in inpainting.
low and high frequencies are retrieved, despite ringing artifacts in the case of CDL. However, CDL and DIP sensitive noise and fail to recover relevant frequencies from the observations in noisy scenarios - see Fig. in the appendix.
In the case of Plug-and-Play, we train DrCNN recover noisy images from the dataset Imagenette and plug into an iterative reconstruction algorithm. In the unsupervised case, the denoiser learns how to recover degraded images, as explained above. The results are shown Fig. for SNR=20dB and in Fig. D in appendix for more values of SNR. When the noise is low, i.c., SNR 2 20, and when the rate of missing pixels stays below 50%, unsupervised and supervised PnP leads similar performance levels in terms of PSNR. As for the single image example, unsupervised PnP can generalize what is learned in the range space of to the kernel space and performs closely to its supervised counterpart as long as the rate of masked pixels is not too large.
3.2 THE PITFALL OF CONVOLUTIONS DEBLURRING
Convolutions work well when all frequencies are preserved, as shown for inpainting. However, several inverse problems involve recovering signal with missing frequencies. In super-resolution,
Thhe data available https: /ttp:::///ttii /ttte//////tbt/tt////// com/ fastai //magenetteeeee
8

---

Under review as a conference paper at ICLR 2023
all odd frequencies lack in the signal. In deblurring, the signal is observed after degradation by low-pass filter. Unsupervised prior learning becomes troublesome in these cases, as mentioned in (Tachella et al., 2022). We will focus the example of deblurring in the following.
The CDL problem can be re-written in terms of Fourier trans-
Original
Blurred
forms with the Parseval equality
min Rik dle
Σ de
y
+ + 1lxl11
(12)
As the spectrum À is low-pass, nothing is observed in high frequencies. Thus, optimal dictionaries contain atoms (dæ), with high frequencies set to for the same reason as pointed in Proposition 2.1. This is illustrated in Fig. G in appendix.
data
DnCNN:
Fig. 7 displays the reconstructions and PSD of a blurred image for various methods and Fig. 6 their performances for vari- ous blur sizes in the kernel and range spaces. These results show that neither CDL nor DIP side the span of the blur, i.e., in high frequencies. While CDL puts all high frequencies O, DIP adds noise. The same phe- nomenon appears with PnP: there is performance gap between
recover information out-
Discrepancy
supervised and unsupervised learning in the kernel, and gener- alization from the range space to the kernel space is impossible.
weighted weighted
60
Is self-supervised learning adapted deblurring ? We have demonstrated why unsupervised prior learning based on convolutions won't work on deblurring. The figures also show that learning dictionary or denoiser on clean signals does not seem to lead to convincing performance: supervised CDL does not outperform hand-crafted priors, and supervised PnP hardly does better in the kernel space. The key to success is finding prior that can predict missing high frequencies from observed low frequencies. Indeed, the average PSD output by the DnCNN on Fig. 8 shows that the denoiser spontaneously learns to add high frequencies when trained on images that have been blurred, which is not the case otherwise. Then look at the discrepancy of frequencies in atoms learned on a clean image with CDL, defined as
50
5
10
15
20
Number atoms
Figure 8: (top) Average PSD of 10 iterations of DnCNN trained on clean and corrupted data. When trained in supervised setting, the denoiser spontancously adds high frequencies to the image. (bottom) Discrepancy of frequen- cies in atoms from supervised con- volutional dictionaries. When their number increases, the atoms do not necessarily mix frequencies in gen- eral (not weighted), but the ones used by sparse coding (weighted) integrate high and low frequencies.
Σ PSD( PSD((w))) log(w; + log(w, + 1)1
(13)
Atoms with high discrepancies contain broad range of fre- quencies, while the others only focus on specific bandwidths. We show the average and the weighted average take into account the usage that made of these atoms. It is interesting to note that the algorithm prefers atoms with large bandwidths.
These experiments highlight that learning priors on pretext tasks like denoising supervised setting somehow captures the spectral structure. However, supervised CDL and PnP do not perform as well as expected on deblurring. This hints that may be necessary to add specific regularizations or non-linearities like Sharpen filters (Habeeb et al., 2018) to these models to ensure that they learn how to link low and high frequencies appropriately.
CONCLUSION
Prior learning for unsupervised inverse problems is only feasible with multiple operators or appropri- ate constraints the model. When the operator is too ill-conditioned, which typically the case in deblurring, the prior knowledge should compensate for the lack of information. In particular, exclusively relying on convolutions is not enough, even in self-supervised settings with access to clean data.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Michal Aharon, Michael Elad, and Alfred Bruckstein. K-svd: An algorithm for designing overcom- plete dictionaries for sparse representation. IEEE Transactions on Signal Processing, 54:4311 4322, 2006.
Farhad Pourkamali Anaraki and Shannon M Hughes. Compressive k-svd. In 2013 JEEE International Conference on Acoustics, Speech and Signal Processing, pp. 5469-5473, IEEE, 2013.
Sanjeev Arora, Rong Ge, Tengyu Ma, and Ankur Moitra. Simple, efficient, and neural algorithms for sparse coding. Conference on learning theory, pp. 113-149. PMLR, 2015.
Amir Beck and Mare Teboulle. A fast iterative shrinkage-thrrshooldnng algorithm for linear inverse problems. SIAM J. Imaging Sciences, 2:183-202, 2009.
Ashish Bora, Eric Price, and Alexandros G Dimakis. Ambientgan: Generative models from lossy measurements. In International conference on learning representations, 2018.
Alon Brifman, Yaniv Romano, and Michael Elad. Turning denoiser into a super-resolver using plug and play priors. In 2016 IEEE International Conference on Image Processing (ICIP), pp- 1604-1408. IEEE, 2016.
Antonin Chambolle, Vicent Caselles, Daniel Cremers, Matteo Novaga, and Thomas Pock. An introduction to total variation for image analysis. Theoretical foundations and numerical methods for sparse recovery, 9(263-340)2227, 2010.
Stanley H Chan, Xiran Wang, and Omar Elgendy. Plug-and-pba admm for image restoration: Fixed-point convergence and applications. IEEE Transactions on Computational Imaging, 3(1): 84 98, 2016.
Thomas Chang, Bahareh Tolooshams, and Demba Ba. Randnet: Deep learning with compressed measurements of images. In 2019 IEEE 29th International Workshop on Machine Learning for Signal Processing (MLSP), pp. 1 1-6. IEEE, 2019.
Niladri Chatterji and Peter L Bartlett. Alternating minimization for dictionary learning with random initialization. Advances Neural Information Processing Systems, 30, 2017.
Dongdong Chen, Julián Tachella, and Mike Davies. Equivariant imaging: Learning beyond the range space. In Proceedings the IEEE/CVF International Conference on Computer Vision, pp. 4379-4385 2021.
Tom Dupré la Tour, Thomas Moreau, Mainak Jas, and Alexandre Gramfort. Multivariate convolutional sparse coding for electromagnetic brain signals. Advances in Neural Information Processing Systems, 31:3292-3302. 2018.
Michael Elad. Sparse and redundant representations: from theory to applications in signal and image processing. Springer Science & Business Media, 2010.
Simon Foucart and Holger Rauhut. An invitation to compressive sensing. In A mathematical introduction compressive sensing, pp. 1-39. Springer, 2013.
Alexandre Gramfort, Matthieu Kowalski, and Matti Hämäläinen. Mixed-norm estimates for the m/eeg inverse problem using accelerated gradient methods. Physics in medicine and biology, 57: 1937-61, 2012.
Rémi Gribonval, Rodolphe Jenatton, and Francis Bach. Sparse and spurious: dictionary learning with noise and outliers. IEEE Transactions on Information Theory, 61((1):6298-631 63119,9988669,,,, 2015.
Roger Grosse, Rajat Raina, Helen Kwong, and Andrew Y. Ng. Shift-Invariant Sparse Coding for Audio Classification. Cortex, 8:9, 2007.
Nada Jasim Habeeb, Salman Hussien Omran, and Dahir Abbas Radih. Contrast enhancement for visible-infrared image using image fusion and sharpen filters. 2018 International Conference on Advanced Science and Engineering (ICOASE), pp. 64-69. IEFE, 2018
10

---

Under review as a conference paper at ICLR 2023
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6900, 2014.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-222) 1998.
Jaakko Lehtinen, Jacob Munkberg, Jon Hasselgren, Samuli Laine, Tero Karras, Miika Aittala, and Timo Aila. Noise2noise: Learning image restoration without clean data. In International Conference on Machine Learning, pp. 2965-29777 PMLR, 2018.
Jiaming Liu, Yu 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 in Signal Processing, (016)):08819999 2020.
Julien Mairal, Francis Bach, J. Ponce, and Guillermo Sapiro. Online learning for matrix factorization and sparse coding. Journal of Machine Learning Research, 11, 2009.
Stéphane Mallat. A Wavelet Tour of Signal Processing. Academic press, 2008
Arthur Mensch, Julien Mairal, Bertrand Thirion, and Gaël Varoquaux. Dictionary learning for massive matrix factorization. In International Conference on Machine Leariin, pp. 1737-1746. PMLR, 2016.
Arthur Mensch, Julien Mairal, Bertrand Thirion, and Gaël Varoquaux. Stochastic subsampling for factorizing huge matrices. IEEE Transactions on Signal Processing, (0(1):113-1288 2017.
Valeriya Naumova and Karin Schnass. Dictionary learning from incomplete data for efficient image restoration. In 2017 25th European Signal Processing Conference (EUSIPCO), pp. 1429-1429. IEEE, 2017.
Bruno A. Olshausen and David J Field. Sparse coding with an incomplete basis set: A strategy employed by |protect( VV)). Vision Research, 37(23)3311-33355 1997.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. In Advances in neural information processing systems, pp. 8026-8037, 2019.
Fabian Pedregosa, Gael Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, Jake Vanderplas, Alexandre Passos, David Cournapeau, Matthieu Brucher, Matthieu Perrot, Edouard Duchesnay, and Gilles Louppe. Scikit-leamn: Machine learning in python. Journal of Machine Learning Research, 12, 2012.
Farhad Barkkamali-Aaarkke Stephen Becker, and Shannon M Hughes. Efficient dictionary learning via very sparse random projections. In 2015 International Conference on Sampling Theory and Applications (A)mpTA), pp. 478-482. IEEE, 2015.
Alejandro Ribes and Francis Schmitt. Linear inverse problems in imaging. IEEE Signal Processing Magazine, 24: (114):84999) 99, 2008
JH Rick Chang, Chun-Liang Li, Barnabas Poczos, BVK Vijaya Kumar, and Aswin C Sankara- narayanan. One network solve them all-solving linear inverse problems using deep projection models. In Proceedings of the IEEE International Conference on Computer Vision, pp. 5888-5897, 2017.
Yaniv Romano, Michael Elad, and Peyman Milanfar. The little engine that could: Regularization by denoising (red). SIAM Journal on Imaging Sciences,
2017.
Jean-Lue Starck. Sparsity and inverse problems in astrophysics. Journal of Physics: Conference Series, 699, 2016.
Christoph Studer and Richard G Baraniuk. Dictionary learning from sparsely corrupted compressed signals. In 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3341-3344. IEEF, 2012.
11

---

Under review as a conference paper at ICLR 2023
Zoltán Szabó, Barnabás Póczos, and András Lörinez. Online group-structure dictionary learning. In CVPR 2011, pp. 2865-28777 IEEE, 2011.
Julián Tachella, Dongdong Chen, and Mike Davies. Sampling theorems for learning from incomplete measurements. arXiv preprint wrxiv:221..221511 2022.
Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society Series B, 58:267-288, 1996.
Dmitry Ulyanov, Andrea Vedaldi, and Victor Lempitsky. Deep image prior. In Proceedings of the IEEE conference computer vision and patlern recognition, pp. 9446-9454, 2018.
Florence Yellin, Benjamin D Haeffele, and René Vidal. Blood cell detection and counting in holo- graphic lens-free imaging by convolutional sparse dictionary learning and coding. International Symposium Biomedical Imaging, pp. 650-653. IEEE, 2017.
Kai Zhang, Wangmeng Zuo, Yunjin Chen, Deyu Meng, and Lei Zhang. Beyond Gaussian denoiser: Residual learning of deep CNN for image denoising. IEEE Transactions on Image Processing, 26 (7):3142-3155, 2017.
A FULL DESCRIPTION OF THE EXPERIMENTS
This section provides complementary information on the experiments presented in the paper.
Optimization for dictionary learning. The Lasso is always solved with FISTA (Beck & Teboulle, 2009), then the minimization is done by gradient descent over the dictionary with the help of a line search.
A.1 PARTIAL RECOVERY IN DICTIONARY LEARNING WITH A SINGLE OPERATOR FIG.
We generate 10 000 samples from a random Gaussian dictionary D of dimension 100 x 100 and Bernoulli Gaussian sparse codes Z with several levels of sparsity, i.e. ratio of non zero elements in average. Then we degrade the signals with a random Gaussian compressed sensing operator of dimension x 100 for several values of m. i.e. Y ADZ. We compare the maximal recovery scores over X for each level of sparsity with the perfect score that we can achieve the range space of single operator. We repeat this experiment 5 times.
A.2 RECOVERY DICTIONARY LEARNING WITH MULTIPLE OPERATORS FIG.
We generate N = 10 000 samples from a random Gaussian dictionary D of dimension 100 x 100 and Bernoulli Gaussian sparse codes Z with ratio of non zero elements of 0.1. Then we degrade the signals with given number N of random Gaussian compressed sensing operators of dimension m x 100, i.e. samples [il [ل>ا J. (i (i+ 1)L Nm. are seen through operator A,, We compare the maximal recovery scores over for each N,, with the perfect score that we can achieve with a single operator. We repeat this experiment times.
N.
A.3 RECOVERY IN DICTIONARY LEARNING ON PATCHES FROM NATURAL IMAGE IN INPAINTING FIG.
We mask geey- 256 x 256 image with binary mask containing given level of missing pixels. Then we split this image into 10 x 10 patches and we learn a dictionary of size 100 on these patches, with À = 0.1. We compute the recovery score by comparing dictionaries obtained with and without the mask, and we weight the costs by the average of sparse activations Z in absolute value for a given atom
N
N
W
71.
ZI.
1T/
Σ i.j
Zinl
(14)
C
Do.
D
3
W)T
(15)
12

---

Under review as a conference paper at ICLR 2023
This better reflects the usefulness of the atoms, and allows to take into account the fact that dictionaries learned on natural signals may contain irrelevant atoms that are almost never used. We repeat this experiment 10 times.
A.4 PSNR RECONTRUCTION INPAINTING AND DEBLURRING FIG. AND FIG.
Single image (top). We mask grey-level 256 x 256 image with binary mask containing a given level of missing pixels.
CDL We learn convolutional dictionary on the observed image (unsupervised) or clean image (supervised) with atoms of size 10, and we take the maximal PSNR over several values of A.
DIP. We leverage the architecture based on SkipNet proposed in Ulyanov et al. (2018), and we train the network as in the DIP paper with Adam (Kingma & Ba, 2014), learning rate of 0.01, an input noise of standard deviation a = 0.1, and a regularization noise of 0.03. The result is displayed after 1000 epochs. This choice of hyper-parameten led to good results in practice.
standard deviation
Plug and Play (bottom). The dataset is composed of 1000 natural images from the dataset Ima- genette available at https:: ////tttt hub. com/ fastai/ fastai/imagenen /mmggnnetteteeee in grey-level and cropped to size 160 160. We mask the images with the same operator A, and we learn to denoise degraded images Y by minimizing the loss
Σ [A(f(())) - 1I1l
(16)
N
where y = Y, with ~ ~N, a²). The network is DrCNN (Zhang et al., 2017) available at https:://// //gtt/////ttbb com/ Doszn/DnCND, git We train it wih Adam, learning rate 0.001, batch size 32, maximal number of epochs 50. Then the network fo is integrated in reconstruction algorithm
Xa+1 fo(x, -Y)
(17)
for 100 iterations, with r which led to good results practice. We display the maximal average PSNR on the test set composed of 50 images from Imagenette degraded in the same way, over and epochs.
SNR for deblurring. We rely the Signal to Noise ratio (SNR) to measure the performance in the case of deblurring. We define the range space of the blur as the part of its spectrum within 2a. 95% of the power contained in the range space, and 5% in the kernel space, hence the interest in switching to the SNR instead of the PSNR.
A.5 DIGITS RECOVERY WITH DICTIONARY LEARNING FIG.
We generate an image composed of 10 digits from the dataset digits of scikit-learn (Pe- dregosa al., 2012). We then learn convolutional dictionary with 30 atoms size 10 x 10, and look at the correlation between each atom and each digit (we keep the best for each digit) to compute the average recovery on all digits. The algorithm is run with different values of hyper- parammparameters and we keep the best recovery score (oracle predictor). The experiment is repeated for several sizes of images, from 50 x to 300 300 and for several rates of missing pixels, with gaussian noise of standard deviation 0.1.
A.6 ILLUSTRATION OF INPAINTING AND DEBLURRING FIG. FIG. AND FIG. B
In the case of inpainting, the image is degraded by binary mask with rate of missing pixels of 50% without noise in Fig. and with SNR=6dB in Fig. B In the case of deblurring, the image is degraded by gaussian blurr of size 10 10 with = 0.3 without noise. The algorithms that can be used single image are run on each channel as described in Fig. and we display the reconstruction plus the power spectrum density.
13

---

Under review as a conference paper at ICLR 2023
A.7 SELF-SUPERVISED PRIOR LEARNING FIG. 8
Plug and Play (Top). We train a DnCNN as explained for Fig. 6 on both clean (supervised) and blurred (unsupervised) images (1000 samples), and we look at the average PSD of images output by 10 fixed point iterations of the network when fed with the test set (50 samples), i.e.
X (x,) 1 S 10,
(18)
where Xo is the blurred observation. The goal is to check if the network is able to add missing high frequencies to an image after being trained on a pretext task like denoising in the context of Plug and Play, where gradient descent steps alternate with forward passes in the denoiser.
CDL (Bottom). We learn a convolutional dictionary with atoms of size 20 x 20 on a clean grey- level image of size 256 256 and measure the discrepancy of frequencies in the atoms depending on the number atoms in the dictionary. In this example, the level of sparsity is high (we set À = 1). The discrepancy is defined as
Σ (SD((,)) log(w; + 1) log(ws 1)]
(19)
We repeat the experiment 20 times.
B EXTRA FIGURES AND EXPERIMENTAL RESULTS
B.1 DICTIONARY RECOVERY DEPENDING ON SPARSITY, PROPORTION OF MISSING VALUES AND NUMBER OF SAMPLES FIG. A
We generate the data from Gaussian dictionary of size 100 x 100 and Bernoulli Gaussian sparse codes of sparsity s (average rate of non zero coordinates). Then, we degrade the data with a binary mask of variable rates of available coordinates We learn dictionary of size 100 x 100 over several values of A. We show the ability of the algorithm to recover the dictionary, depending on p. the number of training samples and the level of sparsity in the data. Dictionary recovery is defined as obtaining a recovery score of at least 0.95. We display the results from three different perspectives:
Left. Minimal number of samples necessary to recover the dictionary depending sparsity and rate of available coordinates in the data. A number samples larger than 10 means no recovery possible.
Center. Maximal level of sparsity s (maximal proportion of non zero coordinates) to recover the dictionary depending on the number of samples and the rate of available coordinates. level equal to 0 means no recovery possible.
Right. Minimal rate of available coordinates for recovery depending on the number of samples and the level of sparsity. A level equal means recovery possible.
These figures show that there is a hard limit to what can be learned depending on the proportion of missing values and sparsity, regardless the number of training samples. Having access to the whole signal space is not sufficient condition to recover the dictionary.
B.2 RECONSTRUCTION WITH SNR 6DB FIG. B.
The image degraded by binary mask with a rate of missing pixels of 50% and with gaussian noise such that the SNR is equal to 6dB. The algorithms that can be used on single image are run on each channel as described for Fig. and we display the reconstruction plus the power spectrum density. As opposed to what we observed for SNR=20dB, the reconstruction is made harder by the presence of noise.
B.3 PSNR FOR INPAINTING WITH VARIOUS LEVELS OF NOISE FIG. AND FIG.
We repeat the experiments from Fig. 3 with various levels of SNR: noiseless, 20dB, 12dB, 6dB. When the noise is too high, unsupervised prior learning methods fail to learn proper prior in the range space of A.
14

---

Under review as a conference paper at ICLR 2023
N samples for recovery
Max. sparsity for recovery
Min, proportion for recovery 10t
0.30
104
10a
1.0
0.9
0.25
samples
samples
0.8
sparsity
10a
10a
0.15
10a
0.5
0.10
0.4
0.3
0.05
107
10a
0.5
1.0
0.5
1.0
0.1
0.2
0.3
P
P
sparsily
Figure A: Dictionary recovery depending on sparsity, proportion of available coordinates p and number of samples. There is a hard limit to what can be learned in inpainting, which depends on and sparsity.
Original
Observation
CDL
DIP
Wavelets
TV
Figure B: Reconstruction in noisy scenario with SNR 6dB.
B.4 SNR FOR DEBLURRING WITH VARIOUS LEVELS OF NOISE FIG. AND FIG. F
We repeat the experiments from Fig. 6 with various levels of SNR: noiseless, 20dB, 12dB, 6dB. When the noise is too high, unsupervised prior learning methods fail to learn proper prior in the range space of A.
15

---

Under review as a conference paper at ICLR 2023
SNR inf
SNR 20.0
SNR 12.0
SNR 6.0
25
30
30
20
PSNR
20
15
0.25 0.50 0.75
0.25 0.50 0.75
0.25 0.50
0.25 0.50 0.75
PSNR kernel
25
25
supervied
CDL
TV
Wavelets
15
15
15
DIP
0.25
0.50
45
24
30
PSNR
35
26
30
20
0.25 0.50 0.75
0.25 0.50
0.25 0.50 0.75 Prop. of pixels
0.25 0.50
Prop. of pixels
Prop. of pixels
Prop. of pixels
Figure C: PSNR depending the proportion of available pixels and noise for CDL, DIP, TV and wavelets based reconstruction on a 256 x 256 grey-level image. Unsupervised prior learning works only when the noise is not too high.
SNR Inf
SNR 20.0
SNR 12.0
SNR 6.0
PSNR recovery
30
25
30
20
10
10
15
0.25
0.50
0.75
0.25 0.50 0.75
0.25 0.50 0.75
0.25 0.50 0.75
30
PSNR keree
30
30
25
20
20
Unsup.
Sup.
10
15
0.25 0.50 0.75
0.25 0.50 0.75
0.25 0.50 0.75
0.25 0.50 0.75
PSNR range
30
30
25.0
40
28
22.5
20.0
0.25 0.50 0.75
0.25 0.50 0.75
Prop. of missing pixels
missing pixels
Prop. of missing
pixels
Figure D: PSNR depending the proportion of available pixels and noise for supervised and unsupervised Plug and Play. When the noise is too high, unsupervised PnP fails to recover the image both in the kernel and the range space of A.
16

---

Under review as a conference paper at ICLR 2023
inf
SNR 20.0
SNR 12.0
SNR
25
PSNR recovery
25
20
25
20
15
10
PSNR kernll
15
CDL supervised
CDL
10
TV
Wavelets
10
10
DIP
0.25
0.50
0.75
0.25 0.50
0.75
0.25 0.50
0.75
0.25 0.50 0.75
30.0
27.5
PSNR
40
30
20
0.25 0.50 0.75
0.25 0.50 0.75
0.25 0.50 0.75
0.25 0.50 0.75
Sigma blurr
Sigma blurr
Sigma blurr
Sigma blurr
Figure E: SNR depending the standard deviation of the blurr and noise for CDL, DIP, TV and wavelets based reconstruction on 256 256 grey-level image. Noise makes difficult for unsupervised prior learning to work in the range space of A.
SNR
SNR 20.0
SNR 12.0
SNR
PSNR recovery
40
30
25.0
22.5
25
20.0
17.5
20
0.25
0.50
0.75
0.25 0.50 0.75
0.25
0.50 0.75
0.25 0.50
0.75
20
PSNR kemel
15
20
15
Sup. PnP
10-
Unsup. PnP
10
10
0.25
0.50
0.75
0.25 0.50 0.75
0.25 0.50 0.75
0.25 0.50
0.75
37.5
32
28
PSIRR range
35.0
26
32.5
28
24
30.0
26
22
0.25 0.50 0.75
0.25 0.50 0.75
0.25 0.50 0.75 Sigma blur
0.25 0.50 0.75
Sigma blurr
Sigma blurr
Sigma blur
Figure F: SNR depending on the standard deviation of the blurr and noise for supervised and unsupervised Plug and Play. When the noise is too high, unsupervised PnP fails recover the image in the range space of A.
17

---

Under review as a conference paper at ICLR 2023
Figure G: 40 atoms of dictionary learned with CDL (A 0.1, atoms of size 20 x 20) for inpainting (left) and deblurring (right) on the image Figure 4. High frequencies are put to in the case of deblurring, thus the atoms appear blurry.
18

---

Under review as a conference paper at ICLR 2023
C
PROOFS
C.1 PROOF OF PROPOSITION 2.1
Let Zo E arg ming / |ADoZ r12
X >| Let 2j
-D
Zo,. Then
-Pob |l
I'D'Z' - = 1|AD/26 1112
(20)
|| - 1
(21)
The result follows.
C.2 PROOF OF PROPOSITION 2.2
Let A E Rmmx" Y E RmXT, We aim to solve
min DEC,2
|ADZ YI2 + 11
(22)
Performing a SVD on leads to
A
U UAV*
Rmxm
V
Rex
and UU* Lms VV* = 1n
(23)
X
0
0
0
A2
...
0
A
(24)
0
Am
0
Then,
1
min DEC,2 2
||ADZ
Y12
A|
min DEC,Z 2
WWAV-DZ-A DZ + 1
(25)
= min DEC,2 2
|AV* DZ - U-Y + + 1
(26)
1 ^DZ $112 + 1
min D.c.Z,D-VD.yy-ll 2
(27)
Adding zeros A to make square, and adding zeros the end of the measurement vector U*Y to respect dimensions, the problem reduces to
1 2
ADZ 71, + A|IZI|1, s.t. A diag(A)," Am O, ... ,0),,,,)....
U
min DEC.2
(28)
On-m
Then, Proposition 2.1 applies and an optimal dictionary is contained in ker(A)-
19


Reviews:
[{"review_id": "xTDr3eAJnx", "reviewer": "Reviewer_SBkU", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper considers learning priors in the case when one only has access to corrupted measurements of signals, rather than clean signals themselves. The authors first provide an analysis of learning a sparsifying dictionary when only given compressed measurements. It is shown that if only one measurement operator is used, then information in the kernel of the measurement operator cannot be recovered. The situation changes, however, when multiple measurement matrices are used which are “diverse” enough for information to be learned. The authors then experimentally demonstrate that recovery with only corrupted data is possible when convolutional structure is used as a prior in certain problems, namely inpainting. This is shown to not be the case, however, in deconvolution.", "summary_of_the_review": "I think that the paper is tackling an interesting problem and showcases some promising/interesting interesting experimental observations. However, in its current form, I think that it lacks novelty/significance compared to prior work in both the theory and experiments.", "strength_and_weaknesses": "\n**Strengths:**\n- The paper studies an important and challenging problem, which is to identify when and why its possible to learn priors directly from corrupted data.\n- The experimental make some interesting comments on when priors can be learned, which can happen when information is introduced into the prior model that can compensate for the type of degradation in the forward model.\n\n**Weaknesses:** \n- There is a lack of novelty in the theory presented in this paper. The results presented here are very similar in spirit to previous work. Please see the Novelty and significance section below.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "akuNek8mfW", "reviewer": "Reviewer_zjwn", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper tries to answer when prior learning can help in inverse problems using unsupervised ML methods. I don’t think this is an easy question to answer yet and understandably the paper considers a few simpler cases.  The paper starts off with traditional dictionary learning methods and shows that one can only learn atoms in the range of the operator. Next, they discuss convolutional dictionary learning and finally provide some empirical observations about unsupervised learning methods.", "summary_of_the_review": "I think the paper lacks few clear novel ideas that it wants to bring to the community. A lot of known conclusions are presented but unfortunately do not lead to something concrete or novel that the community can benefit from. I cannot recommend acceptance at this stage.", "strength_and_weaknesses": "-  I am not quite sure what the contributions of the paper are. The implications drawn from Prop 2.1 and 2.2 have been known for a while in inverse problems. \n- Similarly in the experiments, I do not think that SNR dropping in the kernel space while mostly stable in the range space is a novel observation; it is expected behaviour.\n- I don’t quite understand Eq 9, shouldn’t A only be applied to f_\\theta(Y_i)? In Eq 8, f_theta was taking in terms from the space of images (i.e. X space) while in 9 f_theta takes in measurements (Y-space)? Can the authors clarify how 8 leads to 9?\n- I do not find the WSS justification for convolutions convincing? Why is it ok for X  (an image) to be considered a WSS process?  I think the reasoning could have been given without any WSS assumption. Consider any image x, if we apply a random mask with masking probability p, the expected norm of the masked image should automatically be rho*\\|x\\|. What am I missing here?\n- “Natural images are stable enough to allow convolution-based algorithms to learn from all frequencies” – what does it mean for natural images to be stable? Also DIP or any other network has more than convolutions. In fact non-linearities are essential for a network’s performance. What is the claim here?\n- In Fig 3 and 6, please also include the image over which the experiment was run.\n- I also don’t understand what the authors mean to say when they claim that convolutions won’t work on deblurring. We do have sharpening filters that work to sharpen slightly blurred images. Is the claim that CNNs when trained DIP-style can’t deblur? \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Pr41fL2W8c6", "reviewer": "Reviewer_aFy7", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper studies where (weak) prior learning can and can’t work in unsupervised inverse problems, by considering dictionary learning in a conventional model as well as convolutional dictionary learning. Inpainting and deblurring asks are addressed in this work.\n", "summary_of_the_review": "Essentially, this work extends the study conducted by Tachella et al. (2022) in order to provide a practical understanding of when one can and can’t learn a prior for unsupervised inverse problems. In the submitted paper, the authors focus on the case where the prior is not constrained, with the analysis of dictionary learning, using a single measurement operator first and then extending these results to multiple operators. Finally, they address prior knowledge within convolutional dictionary learning, and demonstrated several claims, such as why convolutions are likely to work on tasks like inpainting, including learning convolutional dictionaries from incomplete data as well as the unsupervised reconstruction. The deblurring task was also considered in the paper.\nThe claims are clearly presented and going to the main claims, such as the prior knowledge should compensate for the lack of information in deblurring tasks.\n", "strength_and_weaknesses": "Weakness: this paper is roughly an extension of the work conducted by Tachella et al. (2022)\n\nStrengths:\nThe paper is well written, clearly presenting the claims and discussions. The paper presents many interesting results, within different tasks such as inpainting and deblurring. See other comments for details", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "OxERT8Vb-5", "reviewer": "Reviewer_ZBdm", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper focuses on unsupervised inverse problems, and studies under what conditions recovery is possible. Their contribution involves a series of characterization and analyses of the problem, explained below.\n\n- They focus on the compressive dictionary learning problem and provide the conditions under which dictionary recovery is possible given one or multiple compression operators (measurement matrix).\n- They focus on convolutional structure as a weak prior, and show how unsupervised CDL is able to perform similarly to supervised CDL when compression is not high.\n- They show that for deblurring, where high-frequency information is completely lost, supervised CDL, unsupervised CDL, and all the hand-crafted features fail to recover.\n- Given all these analyses and characterization of unsupervised inverse problems, they phrase the ultimate goal as \"the key to success is finding a prior that can predict missing high frequencies from observed low frequencies.\" They show that the structure of DnCNN is indeed able to do that by capturing spectral information.\n", "summary_of_the_review": "I enjoyed reading the paper. It is an interesting work on analyzing why unsupervised inverse problems may fail, how to bake weak priors to alleviate that, how supervised inverse problems may fail, and how to apply methods to capture spectral information to recover information that seems to be lost from the perspective of classical optimization. However, it is not clear if these results are already known in prior works. A discussion is needed here. Given that, I rate this paper as marginal acceptance. I may change my rating depending on the requested discussion.", "strength_and_weaknesses": "The paper is well organized. I enjoyed reading the paper. It provides very good analysis, nice explanations to give intuitions (e.g., paragraph after (4)), and clear experiments on when and where supervised/unsupervised inverse problems may fail.\n\n- The paper points out interesting insights on why dictionary learning with one operator may fail. It would be nice to indeed cite works that use several (instead of one) random measurement matrices for compressive dictionary learning (here are three examples [1,2,3]) when you introduce compressive dictionary learning (1).\n\n- My main concern is that it is not clear which result is known from prior work and which is theirs. Hence, please discuss the novelty of the work and how it is different from prior work. I find this paper more of a review paper and summarizing what is known in the literature. Please make a clear discussion on the new finding of this paper compared to prior work. For example, some of the findings of this paper are based on Tachella et al. (2022).\n\n- The paper considers only dictionary learning and linear inverse problem. How generalizable is this to other generative models and for example non-linear inverse problems?\n\nminor comments:\n- Before (4), \"if this is not feasible, then (2) is not feasible\". Please explain why?\n- It would be nice to visualize some of the dictionaries learned in this work.\n- Although very well-known, please cite lasso before (1) [4].\n- Move figures close to their explanation.\n- please use the same y-axis in sub-figures (e.g., page 16).\n\n[1] Anaraki, Farhad Pourkamali, and Shannon M. Hughes. \"Compressive k-svd.\" 2013 IEEE International Conference on Acoustics, Speech and Signal Processing. IEEE, 2013.\n\n[2] Pourkamali-Anaraki, Farhad, Stephen Becker, and Shannon M. Hughes. \"Efficient dictionary learning via very sparse random projections.\" 2015 International Conference on Sampling Theory and Applications (SampTA). IEEE, 2015.\n\n[3] Chang, Thomas, Bahareh Tolooshams, and Demba Ba. \"Randnet: Deep learning with compressed measurements of images.\" 2019 IEEE 29th International Workshop on Machine Learning for Signal Processing (MLSP). IEEE, 2019.\n\n[4] Tibshirani, Robert. \"Regression shrinkage and selection via the lasso.\" Journal of the Royal Statistical Society: Series B (Methodological) 58.1 (1996): 267-288.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject