On the Inversion of Deep Generative Models
Authors: Aviad Aberdam
Dror Simon
Michael Elad
Venue:  (2021)
Keywords: Sparse Representation
Inverse Problem
Deep Generative Models
Compressed Sensing

Abstract: Deep generative models (e.g. GANs and VAEs) have been developed quite extensively in recent years. Lately, there has been an increased interest in the inversion of such a model, i.e. given a (possibly corrupted) signal, we wish to recover the latent vector that generated it. Building upon sparse representation theory, we define conditions that rely only on the cardinalities of the hidden layer and are applicable to any inversion algorithm (gradient descent, deep encoder, etc.), under which such generative models are invertible with a unique solution. Importantly, the proposed analysis is applicable to any trained model, and does not depend on Gaussian i.i.d. weights. Furthermore, we introduce two layer-wise inversion pursuit algorithms for trained generative networks of arbitrary depth, where one of them is accompanied by recovery guarantees. Finally, we validate our theoretical results numerically and show that our method outperforms gradient descent when inverting such generators, both for clean and corrupted signals.

Under review as a conference paper at ICLR 2021
ON THE INVERSION OF DEEP GENERATIVE MODELS
Anonymous authors Paper under double-blind review
ABSTRACT
Deep generative models (e.g. GANs and VAEs) have been developed quite exten- sively in recent years. Lately, there has been an increased interest in the inversion of such model, i.e. given (possibly corrupted) signal, we wish to recover the latent vector that generated it. Building upon sparse representation theory, we define conditions that rely only on the cardinalities of the hidden layer and are applicable to any inversion algorithm (gradient descent, deep encoder, etc.), under which such generative models are invertible with unique solution. Importantly, the proposed analysis is applicable to any trained model, and does not depend on Gaussian i.idd. weights. Furthermore, we introduce two layer-wise inversion pur- suit algorithms for trained generative networks of arbitrary depth, where one of them accompanied by recovery guarantees. Finally, we validate our theoretical results numerically and show that method outperforms gradient descent when inverting such generators, both for clean and corrupted signals.
INTRODUCTION
In the past several years, deep generative models, e.g. Generative Adversarial Networks (GANs) (Goodfellow et al., 2014) and Variational Auto-Encoders (VAEs) (Kingma & Welling 2013). have been greatly developed, leading to networks that can generate images, videos, and speech voices among others, that look and sound authentic humans. Loosely speaking, these models learn mapping from random low-dimensional latent space to the training data distribution, obtained in an unsupervised manner.
Interestingly, deep generative models are not used only to generate arbitrary signals. Recent work rely on the inversion of these models to perform visual manipulations, compressed sensing, image interpolation, and more (Zhu et al., 2016 Bora et al.] 2017 [Simon & Aberdam) 2020). In this work, we study this inversion task. Formally, denoting the signal to invert by y E R", the generative model as G I - _2", and the latent vector E In we study the following problem:
z" arg min
[IG(2) - -11
where G is assumed be feed-forward neural network.
The first question that comes to mind is whether this model is invertible, or equivalently, does Equa- tion I have unique solution? In this work, we establish theoretical conditions that guarantee the invertibility of the model G. Notably, the provided theorems are applicable to general non-random generative models, and do not depend on the chosen inversion algorithm.
Once the existence of unique solution is recognized, the next challenge is to provide recovery algorithm that is guaranteed to obtain the sought solution. common and simple approach is to draw random vector and iteratively update it using gradient descent, opting to minimize Equation (Zhu et al. 2016 [Bora et al. (017). Unfortunately, this approach has theoretical guarantees only limited scenarios (Hand et al. [0018] Hand & Voroninski 2019), since the inversion problem is generally non-convex. An alternative approach is to train an encoding neural network that maps images to their latent vectors (Zhu et al., 2016: Donahue et al. 2016 Bau et al. 2019 Simon & Aberdam 2020); however, this method is not accompanied by any theoretical justification.
We adopt a third approach in which the generative model is inverted in analytical fashion. Specif- ically, we perform the inversion layer-by-layee similar to Lei et al. (2019). Our approach is based on the observation that every hidden layer is outcome of weight matrix multiplying sparse

---

Under review as a conference paper at ICLR 2021
vector, followed by ReLU activation. By utilizing sparse representation theory, the proposed algo- rithm ensures perfect recovery in the noiseless case and bounded estimation error in the noisy one. Moreover, we show numerically that our algorithm outperforms gradient descent in several tasks, including reconstruction of noiseless and corrupted images.
The contributions of this work are both theoretical and practical. We derive theoretical conditions for the invertiblity of deep generative models by ensuring a unique solution for the inversion problem defined in Equation [ In short, these conditions rely on the growth of the non-zero elements of consecutive hidden layers by a factor of 2 for trained networks and by any constant greater than 1 for random models. Then, by leveraging the inherent sparsity of the hidden layers, we introduce layerwise inversion algorithm with provable guarantees in the noiseless and noisy settings for fully-connected generators. To the best of our knowledge, this is the first work that provides such guarantees for general (non-random) models, addressing both the conceptual in- version and provable algorithms for solving Equation Finally, we provide numerical experiments, demonstrating the superiority of our approach over gradient descent in various scenarios.
Main contributions:
1.1 RELATED WORK
Inverting deep generative models: A tempting approach for solving Equation I to use first or- der methods such as gradient descent. Even though this inversion is generally non-convex, the works Hndandd & Voroninski (2019); Hand et al. (2018) show that if the weights are random then, under ad- ditional assumptions, no spurious stationary points exist, and thus gradient descent converges to the optimum. A different analysis, given in Latorre et al. (2019), studies the case of strongly smooth gen- erative models that are near isometry. In this work, we study the inversion of general (non-random and non-smooth) ReLU activated generative networks, and provide provable algorithm that em- pirically outperforms gradient descent. A close but different line of theoretical work analyzes the compressive sensing abilities of trained deep generative networks (Shah & Hegde 2018 [Bora al., 2017|: however, these works assume that an ideal inversion algorithm, solving Equation I| exists. Different works (Bojanowski et al. (2017): Wu et al. (2019) suggest training procedures that result with generative models that can be easily inverted. Nevertheless, in this work we do not assume anything on the training procedure itself, and only rely on the weights of the trained model.
Layered-wise inversion: The closest work to ours, and indeed its source of inspiration, is Lei et al. (2019), which proposes a novel scheme for inverting generative models. By assuming that the input signal was corrupted by bounded noise in terms of É or fxo, they suggest inverting the model using linear programs layer-by-layer. That said, to assure stable inversion, their analysis is restricted to cases where: (i) the network weights are Gaussian i.idd variables; (ii) the layers expand such that the number of non-zero elements in each layer is larger than the size of the entire layer preceding it; and (iii) that the last activation function is either ReLU or leaky-ReLU. Unfortunately, as mentioned in their work, these three assumptions often do not hold in practice. In this work, we do not rely on the distribution of the weights nor on the chosen activation function of the last layer. Furthermore, we relax the expansion assumption as to rely only on the expansion of the number of non-zero elements. This relaxation is especially needed in the last hidden layer, which is typically larger than the image size.
Neural networks and sparse representation: In the search for profound theoretical understand- ing for deep learning, series of papers suggested a connection between neural networks and sparse coding, by demonstrating that the forward pass of a neural network is in fact a pursuit for a multi- layer sparse representation (Papyan et al. [2177; (ullm et al., 2018 Chun & Fessler) 2019; [Sulam] jet al.) 2019: Romano et al., 2019 Xin et al.] 2016)). In this work, we expand this proposition by showing that the inversion of generative model is based on sequential sparse coding steps.
2 THE GENERATIVE MODEL
Notations:
We use bold uppercase letters to represent matrices, and bold lowercase letters to rep- resent vectors. The vector w, represents the jth column in the matrix W. Similarly, the vector Wa, represents the jth column in the matrix W, The activation function ReLU is the entry- operator Re)U(u) = max/u, 0}. We denote by spark(W) the smallest number of columns in W that are emearly-dependent and by ||x||, the number of non-zero elements in x. The mutual
2

---

Under review as a conference paper at ICLR 2021
coherence of matrix W is defined as: (W) mf w 1
Finally, we define x and
W the supported vector and the row-supported matrix according to the set S, and denote by S the complementary set of S.
Problem Statement: We consider typical generative scheme G IR + R" of the form:
Xn
X ReLU(W,x,), for all {O....,, 1},
G(z) = ((WL)))
where x; E RT, {- are the hidden layers, W; E R Xn are the weight matrices (Ni++1 n). Xu E R is the latent vector that is usually randomly selected from normal distribution, z N=, Im,)). and Φ is an invertible activation function, e.g. tanh, sigmoid, or piece-wise linear.
G(z), that created by the generative model above, aim recover its latent vector z. Note that each hidden vector in the model is produced by a ReLU activation, leading to hidden layers that inherently sparse. This observation supports this model utilizing sparse representation theory. In what follows, we use this observation to derive theoretical statements on the invertibility and the stability of this problem, and to develop pursuit algorithms that are guaranteed to restore the original latent vector.
Given sample
approach study
3 INVERTIBILITY AND UNIQUENESS
We start by addressing this question: "Is this generative process invertible?". In other words, when given a signal that was generated by the model, x = G(z"), we know that a solution z" to the inverse problem exists; however,
ensure that this is the only one? Theorem Saarreemmebaae below (its proof is given in Appendix A provides such guarantees, which are based on the sparsity level of the hidden layers and the spark of the weight matrices (see Section [ Importantly, this theorem is not restricted to specific pursuit algorithm; it can rather be used for any restoration method (gradient descent, deep encoder, etc.) to determine whether the recovered latent vector is the unique solution.
Definition (sub-spark). Define the s-sub-spark of matrix W as the minimal spark of any subset of rows of cardinality S) = 8, sub-spark( W, 8) min spark( (W
Definition (sub-rank), Define the s-sub-rank of matrix W as the minimal rank over any subset S of rows of cardinality S = s, sub-rank( W min rank (WS).
Theorem 1 (Uniqueness). Consider the generative scheme described in Equation 2 and signal x G(zz) with a corresponding set of representations {x: ) that satisfy:
(i) 5t |x|
spark(W,))
(ii) 8; = ||x] llo < sub-spark(W. (..1)))) for all [I....,--11,
2
(iii) sub-rank( Cerrankk(W..555 (1) S1.
Then, zt the unique solution to the inverse problem that meets these sparsity conditions.
Theorem Tis the first of its kind to provide uniqueness guarantees for general non-statistical weight matrices. Moreover, it only requires an expansion of the layer cardinalities as opposed to Huang al. 2018); Hand& & Voroninski] (20l))ssssi(22)))))) Led et al. (2019) that require dimensionality expansion that often does not hold for the last layer (typically << <nz).
direct corollary of Theorem I in the case of random matrices. In such case, the probability of heaving linearly dependent columns is essentially zero [Elad] 2010 Chapter 2). Hence, the conditions of Theorem become:
1+1
8:41 +
(i) 81
(ii) 8
(iii) 81 2 nig
(3)
2
2
In fact, since singular square matrices have Lebesgue measure zero, this corollary holds for almost all set of matrices.
3

---

Under review as a conference paper at ICLR 2021
In practice, to allow for sufficient increase in the cardinalities of the hidden layers, their dimensions should expand as well, excluding the last layer. For example, if the dimensions of the hidden layers increase by a factor of 2, as long the hidden layers preserve constant percentage of non-zero elements, Theorem T holds almost surely. Notably, this is the common practice in various generative architectures, such DC-GAN Radford al. (2013) and PGAN PGAN al. (2017).
Nevertheless, in the random setting, we can further relax the above conditions by utilizing theorem by Foucart& & Rauhut (2013). This theorem considers typical sparse representation model with a random dictionary and states that a sparse representation is unique as long as its cardinality is smaller than the signal dimension. Therefore, as presented in Theorem 2 in the random setting the cardinality across the layers need to grow only by a constant, i.e. S; 81+1 and SL < n.
Theorem 2 (Uniqueness for Random Weight Matrices), Assume that the weight matrices comprise of random independent and identically distributed entries (say Gaussian). If the representations of signal G(z") satisfy:
(i) S | TL
(ii 8; = ||x llu < 8141 for all E II....,--111 1).
(iii) = |x1llo 2 no.
then, with probability 1, the inverse problem has a unique solution that meets these conditions.
The above theorem states that to ensure unique global minimum in the stochastic case, the number of nonzero elements should expand by only a single parameter. The proof of this theorem follows the same protocol as Theorem Is proof, while replacing the spark-based uniqueness (Donoho & Elad 2003) with Foucart& & Rauhut (2013). As presented Section [. these conditions are very effective in predicting whether the generative process is invertible or not, regardless of the recovery algorithm used.
4 PURSUIT GUARANTEES
In this section we provide an inversion al- gorithm supported by reconstruction guar- antees for the noiseless and noisy settings. To reveal the potential of our approach, first discuss the performance of an Oracle, in which the true supports of all the hidden layers are known, and only their values are missing. This estimation can be performed by sequence of simple linear projections on the known supports. Note that already in the first step of estimating XL, we can realize the advantage of utilizing the inher- ent sparsity of the hidden layers. Here, the reconstruction error of the Oracle is pro- portional to $L || lo whereas solving a least square problem, as suggested in Lei al. (2019), results with an error that is proportional to nz.- For more details see Appendix B
Algorithm 1 Layered Basis-Pursuit
Input: y G(z) + E R", where ||e||2 S e, and sparsity levels {=:)/=1-
First step: X = arg min 1 - W 2 +
A || with A = 26e.
Set S₁ = (x)) and (3+V1.5) lr. min, WW
General step: For any layer i L L..... execute:
S111 i+1
W S x
1. & arg minx 1
\ ||x||
with A; 2ei+1.
2. Set S, Support(x.) and c;
(3+ (3+v1.5)
8.41
G+1
ming
Wi.
W 2
Final step: Set à arg min, 1
In what follows, we propose to invert the model by solving sparse coding problems layer-by-layer while leveraging the sparsity of all the intermediate feature vectors. Specifically, Algorithm [ de- scribes a layered Basis-Pursuit approach, and Theorem provides reconstruction guarantees for this algorithm. The proof of this theorem is given in Appendix C In Corollary [ we provide guarantees for this algorithm when inverting non-random generative models in the noiseless case.
Definition 3 (Mutual Coherence of Submatrix). Define μ, (W()) as the maximal mutual coherence of any submatrix of W with rows, Hs (W) max]s]= n (WS)
4

---

Under review as a conference paper at ICLR 2021
First Layer Inversion inearieed ADMM
Midlayer Inversion Linesroed ABMM
Midlayer Inversion
Last Layer Inversion Gradient
ReLJ
CPPPL
W
W
Wa
no
72
71g
Figure I: The Latent-Pursuit inverts the generative model layer-by-layer as described in Algorithm 3 and is composed of three steps: (I) last layer inversion by Algorithm{] (2) midlayer inversions using
Algorithm 2] and (3) first layer inversion via Algorithm with the x-step replaced by Equation TO
Theorem 3 (Layered Basis-Pursuit Stability). Suppose that y x e, where G(z) is an unknown signal with known sparsity levels {s and ||e||| I Let i be the Lipschitz constant of 6 and define cL+1 = Ee. If in each midlayer i (I..... L}. 3 (W.)' then,
The support of &; is subset of the true support, S, S S;;
The vector &; is the unique solution for the basis pusssip
The midlayer's 's error satisfies || - xill2 < EG where E;
(3+vT.3) vs
(3+
8,-1
Ei+1-
miny
W3.)
2
the recovery error on the latent space is upper bounded by
el
(3
1.5)
Vsj
where yp Amin ( 0.
||2 11-22112-
2112
(4)
8,11 1,3
minj
w
Corollary (Layered Basis-Pursuit Noiseles Case), Let x = G(z) with sparsity levels {8i)
and assume that 1/3 (W,) for all i {l...., ......,, L}. and that sp Amin Amin((W- ((WS:)TWd) Then Algorithm recovers the latent vector à = perfectly.
5 THE LATENT-PURSUNE ALGORITHM
$44
While Algorithm provably inverts the generative model, it only uses the non-zero elements x;+1 estimate the previous layer x,. Here we present the Latent-Pursuit algorithm, which expands the Layered Pasis-Pursuit algorithm by imposing two additional constraints. First, the Latent-Pursuit sets inequality constraints, w S x, S 0, that emerge from the ReLU activation. Second, recall that the ReLU activation constrains the midlayers to have nonnegative values, 2 0. Furthermore, we refrain from inverting the activation function directly Φ since practically, this inversion might be unstable, e.g. when using tanh. In what follows, we describe each of the three parts of the proposed algorithm: (i) the image layer; (ii) the middle layers; and (iii) the first layer.
Starting with the inversion of the last layer, i.e. the image layer, we need to solve
X1. arg min lly & W w 1 x, s. x x 0,
(5)
where 1 T'x represents an & regularization term under the nonnegative constraint. Assuming that ø is smooth and strictly monotonic increasing, this problem is smooth convex function with sepa- rable constraints, and therefore, it can be solved using projected gradient descent algorithm. In particular, we employ FISTA (Beck & Teboulle 2009, described in Algorithm i Appendix D

---

Under review as a conference paper at ICLR 2021
We move on the middle layers, i.e. estimating x, for E {l,.... 1}. Here, both the approxi- mated vector and the given signal are assumed to result from a ReLU activation function. This leads us to the following problem:
X; = arg min 2 x
1,1xx, s.t. {
[
0, W x
(6)
where S S is the support of the output of the layer be inverted, and S S is its complementary. To solve this problem we introduce an auxiliary variable a = W. x, leading to the following augmented Lagrangian form:
1
||xf+1 w + A,1' Pi W 2
min X.a.u
S. t.
S 0.
2
This optimization problem could be solved using ADMM (Boyd et al. 2011 however, it would require inverting matrix of size n4 x n4, which might be costly. Alternatively. we employ a more
general method, called alternating direction proximal method of multipliers (Beck) 2017 Chapter 15), in which a quadratic proximity term, ||x x(k) 1q
is added to Equation By setting
Q = aI W.S : + " T W with 3 2 Amax WWS' W + W.ST W
get that Q is positive semidefinite. This leads to the Linearized-ADMin algorithm in Algorithm which is guaranteed to converge to the optimal solution of Equation 7 (see details in Appendix D
We now recovered all the hidden layers, and only the latent vector is left to be estimated. For this inversion step we adopt a MAP estimator utilizing the fact that z drawn from a normal distribution:
Y 2 || w + 2 2 12 s. t. w z S 0,
z = arg min
with y > 0. This problem can be solved by the Linearized-ADee ADMM algorithm described above (see which becomes:
details in Appendix DD. except for the update of in Algorithm 2
we" a + 3 + (aa ()z+))z() -ws" (WSz( -xxx p wor (WS" (8) (1))-(())) (k) u (k)
(10)
Once the latent vector and all the hidden layers {x, Min recovered, propose optional step to improve the final estimation. In this step, which we refer to as debiasing, we freeze the recovered supports and only optimize over the non-zero values in end-to-end fashion. This is equivalent to computing the Oracle, only here the supports are not known, but rather estimated using the proposed pursuit. Algorithm 3 provides short description of the entire proposed inversion method.
Algorithm 2 Latent Pursuit: Midlayer Inversion
Algorithm 3 The Latent-Pursui Algorithm
Initialization: (0) E RR, u
(0) RRe
Initialization: Set X; > 0 and P; > 0.
p. > O, and a, 8 satisfying Equation 8
First step: Estimate X i.e. solve Equa-
Until converged: for k 0, l,... execute:
tion using Algorithm
1. (k+1) ReLU (K)
atp W (WFx(())
Middle step: For layers L
1.
estimate x; using Algorithm 2
x
W.S*T
(W: (k) (()) (1) 2t3
Final step: Estimate z using Algorithm 2
a+o
but with the x-step of Equation TO
2. a (k+1) &- ReRU (n( w x((+1)). -W**(++))
Debiasing (optional):
Set
arg min, ||y y & ((TT.. W
3. (++1) + (t) (k+1) w (1+11)
2
NUMERICAL EXPERIMENTS
We demonstrate the effectiveness of our approach through numerical experiments, where our goal twofold. First, we study random generative models and show the ability of the uniqueness claim above (Theorem 2) to predict when both gradient descent and our approach fail to invert G as the inversion is not unique. In addition, we show that in these random networks and under the conditions of Corollary [ the latent vector is perfectly recovered by both the Layered Basis-Pursul and the Matent-Pursurt algorithm. Our second goal is to demonstrate the advantage of Latent-Pursun over gradient descent for trained generative models, in two settings: noiseless and image inpainting.

---

Under review as a conference paper at ICLR 2021
Random Models
Layers Reconstruction Errors
Gradient Descent
Layered Basis-Pursuih Pursuit
Inversion Bound
Basis-
Latent-Purse
150
E 12
SNT [43)
50
(a) Latent vector
(b) Hidden layer X1
(e) Image G(z)
150
(dP)
1000
E 1
22
50
200
400
600
800
1000
200
400
600
800
1000
200
400
600
800
1000
Hidden Layer Size
Hidden Layer Size
Hidden Layer Size
(d) Latent
(e) Hidden layer
(() Image G(z)
Figure 2: Gaussian iid weights: Recovery errors as function of the hidden-layer size (n1). where the image space is 625. Subfigures (a)-(c) correspond results support Theorem stating that to guarantee a unique solution, the hidden layer cardinality 81 2y should be larger than the latent vector space and smaller than the image space. Moreover, supports Corollary by showing that under the non-zero expansion condition, both Layered Basis- Pursuit and Matent-Pursute (Algorithms) and recover the original latent vector perfectly.
R100 and (d)-(f) to E R2000 These
6.1 RANDOM WEIGHTS
First, we validate the above theorems on random generative models, by considering framework similar to Huang et al. (2018) and Lei et al. 2019). Here, the generator is composed of two layers:
x = G(z) tanh W2 ReLUU(W1)),
(11)
where the dimensions of the network are {100, 200). The weight matrices W and W2 2 are drawn from an iid Gaussian distribution. We generate 512 signals by feeding the generator with latent vectors from a Gaussian distribution, and then test the performance of the inversion of these signals terms of SNR for all the layers, using gradient descent, Layered Basis-Pursuit (Algorithm I). and Latent- Latent-Pursuit (Algorithm B). For gra- dient descent, we use the smallest step-size from {le 1, 1e0, 1e1, 1e2, 1e3, 1e4} for 10, 000 steps that resulted with gradient
625, varies between 50 to 1000 and E
smaller than 1e 9. For Layered Basis-Pursuit A1 from {1e 5, 7 - 6, 3e - 6, le 6, 0), and for Latent-Pursuit, we use \ = 0, = 1e 2 and y O. In Layered Basis-Pursuit and Latent-Pursui we preform debiasing step ner to gradient descent. Figure 2 marks median results in the central line, while the ribbons show 90%, 75%. 25%, and 10% quantiles. In these experiments the sparsity level of the hidden layer is ||x1|lo = 2 due to the weights being random. In what follows, we split
the best
similar man-
approximately 50%, the analysis of Figure 2 to three segments. Roughly, these segments are $1 < no, no < 81 < n, and 81 as suggested by the theoretical results given in Theorem and Corollary [
In the first segment, Figure 2 shows that all three methods fail. Indeed, as suggested by the unique- ness conditions introduced in Theorem 2 when < no, the inversion problem of the first layer does not have unique global minimizer. The dashed vertical line in Figure marks the spot where = ng. Interestingly, we note that the conclusions in (Huang et al.) 2018 Lei et al. 2019), sug- gesting that large latent spaces cause gradient descent to fail, are imprecise and valid only for fixed hidden layer size. This be our uniqueness study and as demonstrated in Figure 2 gradient descent (and any other algorithm) fails when the ratio between the cardinalities of the layers is smaller than 2. Nevertheless, Figure
by comparing ny 100 7u 200. As direct outcome of
7

---

Under review as a conference paper at ICLR 2021
exposes an advantage for using approach over gradient descent. Note that our methods success- fully invert the model for all the layers that follow the layer for which the sparsity assumptions do not hold, and fail only past that layer. since only then uniqueness is no longer guaranteed. However, since gradient descent starts at a random location, all the layers are poorly reconstructed.
For the second segment, we recall Theorem 3 and in particular Corollary | There have shown that Layered Basis-Pursuit and Latent-Pursenn are guaranteed to perfectly recover the latent vector as long as the cardinality of the midlayer s1 ||x Il satisfies no S 81 S 1//3((Wi) 1). Indeed, demonstrates the success of these two methods even when 81 R my is greater than the 2
Figure [
worst-case bound 1/3 (1 Moreover, this figure validates that Latent-Pursuit. which leverages additional properties of the signal, outperforms Layered Basis-PPrsuns especially when $1 is large. Importantly, while the analysis in Lei et al.) (019) suggests that n has to be larger than ni, in practice, all three methods succeed to invert the signal even when >> n. This result highlights the strength of the proposed analysis that leans on the cardinality of the layers rather than their size.
We move to the third and final segment, where the size of hidden layer is significantly larger than the dimension the image. Unfortunately, in this scenario the layer-wise methods fail, while gradient descent succeeds. Note that, in this setting, inverting the last layer solely is an ambitious (actually, impossible) task; however, since gradient descent solves an optimization problem of a much lower dimension, it succeeds in this case well. This experiment and the accompanied analysis suggest that a hybrid approach, utilizing both gradient descent and the layered approach, might be of interest. We defer study of such approach for future work.
6.2 TRAINED NETWORK
To demonstrate the practical contribution of our work, we experiment with generative network trained on the MNIST dataset. Our architecture is composed of fully connected layers of sizes 20, 128, 392, and finally an image of size 28 28 = 784. The first two layers include batch- normalization and a ReLU activation function, whereas the last one includes a piecewise linear unit (Nicolae 2018). We train this network in an adversarial fashion using fully connected dis- criminator and spectral normalization (Miyato et al.] (2018). We should note that images produced by fully connected models are typically not visually appealing as ones generated by convolutional architectures. However, since the theory provided here focuses on fully connected models, this set- ting was chosen for the experimental section, similar to other previous work (Huang al., 2018 Lei et al. 2019) that study the inversion process.
Network inversion: We start with the noiseless setting and compare the Latent-Pursuit algorithm to the Oracle (which knows the exact support of each layer) and to gradient descent. To invert a signal and compute its reconstruction quality, we first invert the entire model and estimate the latent vector. Then, we feed this vector back to the model to estimate the hidden representations and the reconstructed image. For our algorithm we use p = 1E - for layers and 10, 000 iterations of debiasing. For gradient-descent run, we use 10, 000 iterations, momentum of 0.9 and step size of le that gradually decays to assure convergence. Overall, we repeat this experiment 512 times.
Figure 3a demonstrates the reconstruction error of the latent vector. First, we observe that the per- formance of our inversion algorithm is on par with those of the Oracle. Moreover, not only does our approach performs much better than gradient descent, but in many experiments the latter fails utterly. In Appendix
E.I we provide reconstruction error for all the layers followed by image samples.
A remark regarding the run-time of these algorithms is in place. Using an Nvidia 1080Ti GPU, the proposed PatenntPuussui algorithm took approximately 15 seconds per layer to converge for a total of approximately 75 seconds complete, including the debiasing step, for all 512 experiments. On the other hand, gradient-descent took approximately 30 seconds to conclude.
We continue our experiments with image inpainting, i.e. inverting the network and reconstructing a clean signal when only some of its pixels are known. First, we apply a random mask in which 45% of the pixels are randomly concealed. Since the number of known pixels is still larger than the number of non non-zero elements in the layer preceding it, our inversion algorithm usually reconstructs the image successfully as suggested by Figure pp.. In this experiment, we perform slightly worse than the Oracle, which is not surprising considering the information disparity between
Image inpainting:
Note that after training, batch-normalizztion a simple linear operation.
8

---

Under review as a conference paper at ICLR 2021
Trained Models
Latent Vector Reconstruction Error | G (y)ll
Num Exqariment
60
Gradient Descent
Parssit
Oracle Estinator
120
0
20
10
20
20
SNR
(b) ENR [4B3
SNR [uB]
(a)
images
inpaining
(c) Top maek inpaining
Figure 3: Trained layers model: Reconstruction error of the latent vector in 512 experiments.
Latent-Pursui clearly outperforms gradient descent.
the two. As for gradient descent, we see similar results to the ones received in the non-corrupted setting. Appendix [2.2 provides image samples and reconstruction comparison across all layers. Finally, we repeat the above experiment using deterministic mask that conceals the upper 45% of each image (13 out of 28 rows). The results of this experiment, which are provided in Figure 3 and Appendix 3 lead to similar conclusions as in the previous experiment. Indeed, since the model contains fully connected layers, we expect the last two experiments to show comparable results.
CONCLUSIONS
In this paper we have introduced novel perspective regarding the inversion of deep generative networks and its connection to sparse representation theory. Building on this, we have proposed novel invertibility guarantees for such model for both random and trained networks. We have accompanied our analysis by novel pursuit algorithms for this inversion and presented numerical experiments that validate our theoretical claims and the superiority of our approach compared to the more classic gradient descent. We believe that the insights underlining this work could lead to a broader activity which further improves the inversion of these models in variety of tasks.
REFERENCES
Aviad Aberdam, Jeremias Sulam, and Michael Elad. Multi-layer sparse coding: the holistic way. SIAM Journal on Mathematics of Data Science, 1(1):46-77, 2019.
David Bau, Jun- Yan Zhu, Jonas Wulff, William Peebles, Hendrik Strobelt, Bolei Zhou, and An- tonio Torralba. Seeing what a gan cannot generate. In Proceedings of the IEEE International Conference on Computer Vision, pp. 4502-4511, 2019.
Amir Beck. First-order methods in optimization, volume 25. SIAM, 2017.
Amir Beck and Mare Teboulle. A fast iterative thrinkag algorithm for linear inverse problems. SIAM journal on imaging sciences, 2(1):183-202, 2009.
Piotr Bojanowski, Armand Joulin, David Lopez-Paz. and Arthur Szlam. Optimizing the latent space of generative networks. arXiv preprint arXiv:1707.05770 057777,7777 2017.
Ashish Bora, Ajil Jalal, Eric Price, and Alexandros G Dimakis. Compressed sensing using gener- ative models. In International Conference on Machine Learning (ICML), pp. 537-546. JMLR.
org, 2017.
Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein. Distributed optimiza- tion and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine learning, 3(1):1-122, 2011.
Il Yong Chun and Jeffrey A Fessler. Convolutional analysis operator learning: acceleration and convergence. IEEE Transactions on Image Processing, 29(1):2108-2122, 2019.
Jeff Donahue, Philipp Krähenbühl, and Trevor Darrell. Adversarial feature learning. arXiv preprint arXiv: 1605500978 2016.

---

Under review as a conference paper at ICLR 2021
David L Donoho and Michael Elad. Optimally sparse representation in general (nonorthogonal) dictionaries via & minimization. Proceedings of the National Academy of Sciences, 100(5): 2197-2202, 2003. 2003.
Michael Elad. Sparse and redundant representations: from theory applications in signal and image processing. Springer Science & Business Media, 2010.
Simon Foucart and Holger Rauhut. An invitation to compressive sensing. In A mathematical intro- duction to compressive sensing, pp. 1-39. Springer, 2013.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural infor- mation processing systems, pp. 2672-2680, 2014.
Paul Hand and Vladislav Voroninski. Global guarantees for enforcing deep generative priors by empirical risk. IEEE Transactions on Information Theory, 66(1) 1::01111111 2019.
Paul Hand, Oscar Leong, and Vlad Voroninski. Phase retrieval under generative prior. In Advances in Neural Information Processing Systems, pp. 9136-9146, 2018.
Wen Huang, Paul Hand, Reinhard Heckel, and Vladislav Voroninski. A provably convergent scheme for compressive sensing under random generative priors. arXiv preprini 1812.0448/ 2018.
Tero Karras, Timo Aila, Samuli Laine, and Jaakko Lehtinen. Progressive growing of gans for im- proved quality, stability, and variation. arXiv preprint 1xXvv:771.110966 2017.
Diederik Kingma and Max Welling. arXiv:1312.6114 2013.
Auto-encoding variational bayes. arXiv preprint
Fabian Latorre, Armin eftekhari, and Volkan Cevher. Fast and provable admm for learning with generative priors. In Advances in Neural Information Processing Systems, 12004-12016, 2019.
Qi Lei, Ajil Jalal, Inderjit S Dhillon, and Alexandros G Dimakis. Inverting deep generative models, one layer at time. In Advances in Neural Information Processing Systems, pp. 13910-13919, 2019.
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. arXiv preprini arXiv:1802.05957. 2018.
Andrei Nicolae. Plu: The piecewise linear unit activation function. arXiv:1809.09534 2018
arXiv preprint
Vardan Papyan, Yaniv Romano, and Michael Elad. Convolutional neural networks analyzed via con- volutional sparse coding. The Journal of Machine Learning Research, 18(1):2887-29) 223888,,,,,,, 2017.
Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation learning with deep convolutional generative adversarial networks. arXiv preprint 0rX1v:1511.06434, 2015.
Yaniv Romano, Aviad Aberdam, Jeremias Sulam, and Michael Flad. Adversarial noise attacks of deep learning architectures: Stability analysis via sparse-modeled signals. Journal of Mathemat- ical Imaging and Vision, pp. 1-15,2011 2019.
Viraj Shah and Chinmay Hegde. Solving linear inverse problems using gan priors: An algorithm with provable guarantees. In IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 4609-4613. IEEE, 2018.
Dror Simon and Aviad Aberdam. Barycenters of natural images constrained wasserstein barycen- ters for image morphing. In Proceedings of the IEEF/CVE Conference on Computer Vision and Pattern Recognition, pp. 7910-7919, 2020.
Jeremias Sulam, Vardan Papyan, Yaniv Romano, and Michael Elad. Multilayer convolutional sparse modeling: Pursuit and dictionary learning. IEEE Transactions on Signal Processing, 66(15): 4090-4104, 2018.
10

---

Under review as a conference paper at ICLR 2021
Jeremias Sulam, Aviad Aberdam, Amir Beck, and Michael Elad. On multi-layer basis pursuit, efficient algorithms and convolutional neural networks. IEEE transactions on pattern analysis and machine intelligence, 2019.
Joel A Tropp. Just relax: Convex programming methods for identifying sparse signals in noise. IEEE transactions on information theory, 52(3):1030-105, 2006.
Yan Wu, Mihaela Rosca, and Timothy Lillicrap. Deep compressed sensing. arXiv preprint arXiv:1905.06723. 2019.
Bo Xin, Yizhou Wang, Wen Gao, David Wipf, and Baoyuan Wang. Maximal sparsity with deep networks? In Advances in Neural Information Processing Systems (NeurlPS), pp. 4340 4348, 2016.
Jun-Yan Zhu, Philipp Krähenbühl, Eli Shechtman, and Alexei A Efros. Generative visual manipu- lation on the natural image manifold. European Conference on Computer Vision, pp. 597-613 Springer, 2016.
A THEOREM 1 PROOF
Proof. The main idea of the proof is to show that under the conditions Theorem I the inversion task at every layer i {1...., L 1} has unique global minimum. For this goal utilize the well-known uniqueness guarantee from sparse representation theory.
Lemma (Sparse Representation Uniqueness Guarantee Donoho & Elad 2003 Elad (0100).
a system of linear equations y = Wx has a solution x satisfying |xloo < spark( W)/2, then this solution is necessarily the sparset possible.
Using the above Lemma, we can conclude that if x obeys ||xr.llo < spark W wr.)/2, then x is the unique vector that has at most $L nonzeros, while satisfying the equation ø (x) = WxxL.
Moving on to the previous layer, we can employ again the above Lemma for the supported vector x This way, ensure that x 1 is the unique SL-1-sparse solution of x W - as long as
spark spark(W
SL-1 ||x
(12)
sub-spark( (....rr)( implies that the above necessarily holds. This way we can ensure that each layer i, i 11, ,I....,L L 1} is the unique sparse solution.
However, the condition 8I.1 ||x llo
Finally, in order to invert the first layer we need to solve x w z. If W has full column- rank, this system either has no solution or unique one. our case, do know that solution exists, and thus, necessarily, it is unique. A necessary but insufficient condition for this to be true 81 2 nn- The additional requirement sub-rank( WW, 81) = no S 81 is sufficient for to be the unique solution, and this concludes the proof.
B THE ORACLE ESTIMATOR
The motivation for studying the recovery ability of the Oracle that it can reveal the power of utilizing the inherent sparsity of the feature maps. Therefore, we analyze the layer-wise Oracle estimator described in Algorithm 4 which similar to the layer-by-layer fashion we adopt both the Layered Basis- Basis-Pursuit Pursuit (Algorithm D and in the Perenut (Algorithm 3). In this analysis we assume that the contaminating noise is white additive Gaussian.
The noisy signal y carries additive noise with energy proportional to its dimension, 82n. Theorem below suggests that the Oracle can attenuate this noise by a factor of n smaller than 1. Moreover, the error in each layer is proportional to its cardinality o²s;. These results expected, the Oracle simply projects the noisy signal on oowdiineniional subspaces of known
no which is typically much
11

---

Under review as a conference paper at ICLR 2021
Algorithm 4 The Layered-War Wise Oracle
Input: y = Gzz) + e E IR", and supports of each layer {Si)er
First step: &y arg minx 2 (y) W 1 1 where Wz & is the column supported matrix
W.]:.Sz].
Intermediate steps: For any layer i = L - 1, 1, set &, arg min 1 1 Wix
where
W, is the row and column supported matrix W, w S S.). Final step: Set = arg min, ]
2 | w. 2
dimension. That said, this result reveals another advantage of employing the sparse coding approach over solving least squares problems, as the error can be proportional s; rather than n,
Theorem (The Oracle). Given noisy signal G(z) e where ~ N0 and assuming known supports {S.) the recovery errors satisfy
a²
8 SEI
x
Wj) 86
(13)
I Amax W W
W,
Ami
for E (I..... LJ. where W; is the row and column supported matrix, W Wi Stl. The recovery error bounds for the latent vector are similarly given by:
02 11 Amax W W;)
0²
no SE 211 <
nn-
(14)
11 Amin (W, W,)
Proof. Assume y x + with x = G(z). then the Oracle for the Lth layer is xf. W.y. Since
y= W + c, we get that x = x + êτ, where é₁ W and ê₁ N(O, o² ( W -1). Therefore, using the same proof technique in Aberdam et al. (2019), the upper bound on the recovery error the Lth layer is:
E &
12122 tracel (W W[W))- 502
SL
(15)
Amin (W.WW)
Using the same approach derive the lower bound by using the largest eigenvalue of W W 1-
In a similar fashion, we can write x = x + ē for all E {O..... ,.....,, L 1}. where è; A c and A ( A w!W! W ... w!. Therefore, the upper bound for the recovery error the äth layer
For simplicity assume here that is the identity function.
12

---

Under review as a conference paper at ICLR 2021
becomes:
E ||x;
x; 212
| Ap.peel ?
E
o² trace
(A..))
o² trace
(ALL--
A
A (11-11)
o² trace
(AL.L-I -A 11
a²
trace () (.1--1)
Amia
(W Wt)
(16)
trace (R,)) (R (a.1)
Amin W W2)
0²
trace (W," W:)-
==++1 Amin W Wj)
j= Amin (W) W 8i.
and this concludes the proof.
C THEOREM 3
PROOF
Proof. We first recall the stability guarantee from Tropp 2006) for the basis-pursuit.
Lemma (Basis Pursuit Stability Tropp (006)). Let x" be an unknown sparse representation with known cardinality f[xx llo s, and lety Wx*+e, where W is matrix with unit-norm columns and ||ella S Assume the mutual coherence of the dictionary W satisfies < 11(3p(W)) Let
& arg min [ly Wx + +|||x|] with x = 2e. Then, & unique, the support of & is subset of the support of xx, and
Ix x1 < (3 VI.5)e.
(17)
In order to the above lemma in analysis need modify it such that W does need to be column normalized and that the error is f2- and not -oundded For the first modification decompose general unnormalized matrix W WD, where W is the normalized matrix, w; / [ and D is a diagonal matrix with d: = ||wall2. Using the above lemma we get that
|D[x" - x)1b3 (3 VI.5)e.
(18)
Thus, the error in x is bounded by
(3 + 1.5)
||x |||00
(19)
min; |[,, l2
Since Lemma guarantees that the support of a subset of the support of x", we can conclude that
(3
1.5
|xx x
min; [wwll EvS.
(20)
Under the conditions of Theorem 3 we can use the above conclusion guarantee that estimating Xy from the noisy input y using Basis-Pursun must lead to a unique & such that its support is subset of that of xz. Also,
(3 V1.5) min, w Wollly
[x xLll2 <el
EL+IV8L.
(21)
13

---

Under review as a conference paper at ICLR 2021
Algorithm 5 Latent Pursuit: Last Layer Inversion
Ar. 2 0, E (0, 2), 6(-) is E-smooth and strictly monotonic increasing. Input: y E K E,
Initialization: ( < 0, - 0, (0) 1.
General step: for any k = 0, ...... K execute the following:
1. g WEd (WLX))
( (WIx() x)
2. 1) 1) ReLU (k)
μ (g 2x,1))
3. (k++)) + 1+
2
(k+1) + -((+t] + मरनby (u(k+t) - (+))
4. X
(K)
Return: X1.
where WL, is the jth column in W L, and 6L71 = el as (y) can increase the noise by a factor of f.
Moving on to the estimation of the previous layer, we have that X w L-1 + ez, where |ez]lp S <z- According to Theorem 3 assumptions, the mutual coherence condition holds, and therefore, we get that the support of x is a subset of the support of x & is unique, and that
(3 VI.5)
X - 81-1 <
ELV
(22)
S1
minj
w L-15
Using the same technique proof for all the hidden layers results in
(3 +
1.55)
|x; - -illl2 <
G4IVs, for i (1...., L -- 1}.
(23)
$ w t 2
min,
S.11 is the jth column in w where way
$:11
Finally, we have that x Amin (WS)) TwS)) 0, and
w z
e1, where ||e1l2 I 61
Therefore, if x
2 arg min | w z
1
(24)
Then,
| 1/2 e (w.))
1 < -
(25)
3
which concludes Theorem
3 guaranttes..
D DETAILS ON THE LATENT-PURSUIT ALGORITHM
Here provide additional details on the Latent- Pirent-Pursuit algorithm described in Section In order to estimate the last layer we aim to solve
X arg min lly & ( 1 1z1'xx s. 0.
(26)
For this goal make of FISTA (Beck & Teboulle 2009) algorithm as described in Algorithm
As describe in Section 5 for estimating the middle layers we aim solve:
arg min w x
x5
1, s.t. x 0, W x O.
(27)
x 2
14

---

Under review as a conference paper at ICLR 2021
Using the auxiliary variable W and the positive semidefiitt matrix Q al
W. W
31 P; w: W we get that the Linearized-ADMM aims to solve:
min x.a.u
x wfx x 2 a : x +
+ x x
8. x
0, a 0.
(28)
This leads to an algorithm that alternates through the following steps:
x((+1)
arg min
a 2
x
xx(1)
1 (WSx((*)
WSS
x(
+ +xx+
(29)
x
a
B
[k(
WoST (W.S. ((())a(t) -(())
2
8. 2 0.
B
(k+1) < arg min Pi a w (1--1) + u(()
2¹ s.t. a.
(30)
a 2
(k+1) (1) + a (k+1) w x (1++1)
(31)
Thus, the Linearize-ADDM. algorithm, described in Algorithm is guaranteed to converge to the optimal solution of Equation 7
After recovering all the hidden layers, we aim estimate the latent vector z. For this inversion step adopt MAP estimator as described in Section 5
z = arg min
2 ||
Y |2 s.t. W 2 S 0,
(32)
with 7 > O. In fact, this problem can be solved by a similar Linearized-ADMM algorithm described above, expect for the update of x (Equation 29
which becomes:
((++1) arg min
a
(k)
Wos (WSz -x:)) +
xx)
2
a
(33)
8
(k) Pi
wSST (ws (b)) -a()) (*)
+
7
|z|
Equivalently, for the latent vector z, the first step Algorithm 2 is changed to
k- a 3 + (la+ wSs ( xfo w (WS 2 (8) -a -(()))
E INVERSION RESULTS FOR TRAINED NETWORKS
Here provide detailed results for the various inversion experiments described in Section 6.2
E.I CLEAN IMAGES
demonstrates the reconstruction error for all the layers when inverting clean images. In Figures and 6 we demonstrate successful and failure cases of the gradient-descent algorithm and compare them to our approach.
Figure
E.2 RANDOM MASK INPAINTING
demonstrate the performance of our approach compared gradient descent in terms of SNR and image quality respectively for the randomly-generann mask experiment.
Figures 7
E.3 NON-RANDOM MASK INPAINTING
Figures TO 12
demonstrate the performance of our approach compared to gradient descent in terms of SNR and image quality respectively for the non-random mask experiment.
15

---

Under review as a conference paper at ICLR 2021
Layer:0 [Latent]
Erors Layen:
72-
Lateri-Parutt
LuterkPunut
Orace Esimator
Droce Esiiator
Grodient Descont
Gradient Descort
Nam Eneemmen
40
23
(d8)
(a) Latent vector
(b) First hidden layer
Emrors for Layen:2
Errers for Layen:3 (Image)
Groiden
Gradlent
70
Mum Expermeets
Mun Experpe tnets
40
28-
10
80
20
60
80
SHR
SNR (d8]
Second hidden layer X2
(d) Image G(z)
Figure 4: Trained 3-Layers Model: Reconstruction error for all the layers for 512 clean images. As can be observed, the Latent- Pursuit almost mimics the oracle, and outperforms gradient descent.
Ground truth
5
9
3
Gradient descent
2
Our approach
9
2
Figure 5: Reconstruction failures of gradient descent on clean images.
Ground truth
8
3
3
6
5
2
Gradient descent
3
0
3
3
6
5
2
Our approach
8
3
3
6
5
2
Figure Successful reconstructions of gradient descent on clean images.
16

---

Under review as a conference paper at ICLR 2021
Layer:0 (Latent)
Layer]
Latere Pursut
60
Latert Pusut
Orac Estimator
Oncce Estimator
Descent
Gracdent Descent
Experrett
Expeiimnnts
22
10-
50
5KA
500 (d3]
(a) Latent vector
(b) First hidden layor
Errors for Layer:2
Errors for Layen: (Image)
Lateri Purast
Extimator
70-
Latera-Puruut
72-
Coudlent Descent
Gracdient Descert
Nom Dipetments
Num Dipetrents
60-
1.0
20
30
50
10
30
40
60
80
[48]
Second hidden layer x2
(d) Image G(z)
Figure 7: Random mask inpainting reconstruction error for all the layers on a trained generator.
ia
8
Ground truth
Masked input
Gradient descent
3
4
6
2
3
7
Our approach
O
i
3
4
2
0
Figure 8: Random mask inpainting gradient descent failed reconstructions,
Ground truth
S
8
6
3
2
Masked input
Gradient descent
5
6
0
0
4
2
Our approach
7
6
4
3
2
Figure 9: Random mask inpainting gradient descent successful reconstructions.
17

---

Under review as a conference paper at ICLR 2021
Layen: (Latent)
Layer1
Latert Pursut
Latert Pusut
60
Orace Estimator
Descent
75
Gracdent Descert
Oncce Estimator
62-
Expetrent
Expeiments
82
20
10
SMR (nn)
500 (48]
(a) Latent vector
(b) First hidden layor
Errors for Layer:2
Errors for Layen: (Image)
Lateri-Puran Purust
Laterk-Purutt Extimetor
82-
Coudlett Descent
Gracieen Descert
Num Dapatrents
Num Diprtreett
40
50
20
29
12
10
40
50
60
10
60
90
90
[48]
Second hidden layer x2
(d) Image G(z)
Figure 10: Half image mask inpainting reconstruction error for all the layers.
3
Ground truth
Masked input
Gradient descent
Our approach
3
Figure 11: Half image mask inpainting gradient descent failed reconstructions.
3
5
6
f
Ground truth
ł
Masked input
5
W
+
5
b
Gradient descent
B
S
7
b
4
5
6
Our approach
8
S
b
4
6
6
Figure 12: Half image mask inpainting gradient descent successful reconstructions,
18


Reviews:
[{"review_id": "onXqXL_7nj", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n\nThis paper proposes the conditions for the invertibility of deep generative models, and two pursuit algorithms for inverting them. The idea is based on sparse representation theory, applied on layer-by-layer inversion. The authors claim this to be the first work that provides provable guarantees of inversion for general non-random neural networks.\n\nThis is a very solid piece of work, with significant contributions on both the theoretical and practical sides. However, the impact of this work might be limited by the sparsity assumption, which is central to this work. It is unclear whether this holds in more general settings, especially for very deep models trained on large scale datasets.\n\nPros\n1. It is overall clearly written and well-structured.\n2. This work is built on a solid theoretical foundation. It provides interesting connections between neural networks and signal processing / convex optimisation.\n3. This work relaxes the assumptions in previous work [1], which makes it more relevant in practice.\n\nCons\n1. It is unclear how well does the sparsity assumption in theorem 1 hold in practice for trained models, which may limit the impact of this work.\n2. The claims of provable guarantees for inversion is exaggerated, as it only applies to Algorithm 1, which relies on an oracle to provide the true supports of all hidden layers. There is no such guarantee for the more general Algorithm 3.\n3. The experiments are limited to toyish and simple dataset. They are unlikely to capture the statistics of e.g., natural images that are practically more relevant.\n\nOther comments and questions:\n\n1. How to reconcile the difference between the special case of theorem 1 with random matrices (the paragraph above theorem 2) and theorem 2?\n2. At the end of page 2, the complementary S^c_{i+1} is used before it is defined after eq. 5.\n3. What is the distribution of the random input signal used in section 6.1? How is it chosen?\n4. It might be helpful to summarise the sparsity assumptions from theorem 1 in the abstract or introduction, so that the limitation of the analysis and method is more clear for readers.\n5. For gradient descent baselines, it worth considering (at least discussing) algorithms that jointly train the model with gradient descent (e.g.,  [2], [3]).\n\n[1] Inverting Deep Generative models, One layer at a time, Lei et al. 2019\n[2] Optimizing the Latent Space of Generative Networks, Bojanowski et al. 2017\n[3] Deep Compressed Sensing, Wu et al. 2019\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "b-PRog4Mp37", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Clarity:\nThe paper is relatively clearly written except for the experimental section. \n\nOriginality:\nThe content of this paper is not novel. \n\nSignificance:\nThe claimed contribution of this paper is not significant. \n\nCons:\n\nThis work tries to rigorously characterize the conditions for a rather intuitive task (reconstruction). There are a few serious issues around it. \n\nFirst, without having the learned weights satisfying certain conditions exactly, the theorems (e.g. Thm1) are way too conservative, i.e. the bounds are too loose in order to catch all corner cases. In addition, in reality, the activations are not necessarily sparse, especially for generative models. The combination of these caveats make these theorems' indications of little meaning. \n\nSecond, in reality, we use much more complex architecture (CNN, attention, ReLU, Normalization) but these theoretical works can't easily go beyond simple MLP with ReLU, making these results even less meaningful. \n\nThirdly, despite all the above, it is hard for me to reason why the theorems are significant in anyway in the context of ML, e.g. why uniqueness is important. I can understand the significance of existence and uniqueness in the context of differential equation but not ML. \n\nOther comments:\nWhat is \"sparse representation theory\"? I know \"sparse representation\", and \"representation theory\", but not sure about \"sparse representation theory\".\n\nLack of novelty: the proofs are direct extensions of existing compress sensing literature. \n\nExperiments: \n-the experimental setups are quite contrived and not optimized for model performance but for the papers' plots. E.g. a larger scale b etter designed MLP can model MNIST dataset quite well (e.g. 4 layers of 1024x1024 with LeakyReLU)\n-the evaluation metric is suboptimal. Eventually, we want to measure the recovered signal, not the latent code error. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "YJQ82ddZkS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this submission, the authors study the inversion of ReLU networks (where the output of the network is subject to an invertible activation function).  This is an important task, for example for inverse problems using generative priors.  The authors introduce spark-based conditions for the invertibility of each layer of the network, leveraging sparsity that is induced by ReLUs.  The authors also introduce a novel layer wise inversion algorithm and provide provable recovery guarantees in both noisy and noiseless settings.  Empirical results demonstrate the superiority of the proposed algorithm relative to baselines for inversion in particular parameter regimes.  \n\nTheorem 1 on invertibility/uniqueness is a significant contribution in that it permits an invertibility guarantee for neural networks without random weight assumptions.  Previous works involved weights coming from particular distributions.  Theorem 3 is significant because it establishes exact-noiseless recovery or stable-noisy recovery of an inversion algorithm without assuming random wights or growth rates on the network widths.  The authors present a clear and sophisticated algorithmic implementation, where different numerical approaches are used at each layer of an inversion process.  \n\nThere are a few minor issues the authors should fix upon revision:\n(1) In Section 2, the authors should state that n_{L+1}=n.  \n(2) It is not clear whether the authors are simply restating Theorem 2 from Foucart and Rauhut or whether this is a novel contribution.  The connection between the Theorem and the preceding paragraph needs to be clarified.  It appears to the reviewer that Theorem 1's conditions in the random case are more restrictive than Theorem 2's conditions (by a factor of 2).  \n(3) In Section 1.1 paragraph 2, the authors write that they relax expansion assumptions as to rely only on the expansion of the number of non-zero elements.  The commentary on this point during the results sections could be more thorough.  The lines above Theorem 2 indicate that in the random case, the sparsity levels must grow by approximately a factor of two at each layer.  The paper does not say so, but this condition requires that the network widths are larger than a particular geometric sequence with growth rate 2.  I believe this statement also holds true in the non-random case as well.  Please add commentary to this effect after Theorem 1. \n(4) Defn 3: coherent -> coherence\n(5) Theorem 3: epsilon_i isn't defined. It is defined within Algorithm 1, but this should be clearly pointed out.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviews are a bit mixed, so the AC independently examined the submission as well. While the authors' response helped clarifying some issues, the draft would still need some major revision, especially the motivation and the experiment part. Here are some concrete suggestions:

(a) The problem definition in Eq (1) is already problematic, as the authors term the least squares reconstruction as an "inversion." When exact reconstruction is not possible, one needs to question the choice of the 2-norm here: why 2-norm and what happens if we change the norm? How does this choice of norm enter the proof and the theorem statements? The uniqueness, as pointed out by one of the reviewers, requires further elaborations: It is not clear that for applications like image denoising or impainting it is necessary to have a unique latent vector, if all one cares about is good reconstruction.

(b) The authors need to explain the motivation of the "inversion" problem better, in the context of generative models. In generative models, G pushes a distribution p on R^{n_0} to q on R^n. If both p and q have nontrivial support and n_0 < n, the map G can be highly irregular and the reconstruction problem can be very ill-conditioned. Putting assumptions on G (such as incoherence) might heavily constrain what kind of distributions q we can learn. This trade-off was hardly discussed. In fact, if we take n_0 = n, then there exist normalizing flows that can learn any distribution q and that can be trivially inverted. If one is interested in inversion, why not use a universal normalizing flow? 

(c) The authors mentioned a few possible applications (image denoising, compressed sensing, image inpainting) of the inversion problem, but none of them (to my best knowledge) relies on modelling the underlying distribution. There are also classic algorithms for each of these applications. It would be much more convincing if the authors could explain why a deep generative model is advantageous for these applications and compare the proposed algorithms on standard benchmarks of these applications. The AC agrees with the reviewers that the current experiments are a bit toy-ish (which is not wrong by itself but does require a bit more elaboration when the motivation is in question).

(d) The significance of Theorem 1 requires further elaboration. How does one verify its conditions? How often does a trained network satisfy these conditions? How do these conditions restrict the expressiveness of the underlying model? Some of these questions were asked in the reviews but regrettably the authors largely dismissed them. Results like Theorem 2 also require further clarification: what does random weight mean for a generative model? The authors seemed to only care about inversion while completely ignored the expressiveness of a generative model. As a trivial example, one could take a linear network, with regularization we can always invert (in the sense of the authors' definition) the signal. Why is this any different from (if not better than) the authors' results?
Decision: Reject