Multi-layer State Evolution Under Random Convolutional Design
Authors: Mara Daniels
Cedric Gerbelot
Florent Krzakala
Lenka Zdeborova
Venue: NeurIPS 2022 Accept (2022)
Keywords: Approximate Message Passing
State Evolution
High-dimensional statistics
Generative Models
Convolution
Spatial Coupling

Abstract: Signal recovery under generative neural network priors has emerged as a promising direction in statistical inference and computational imaging. Theoretical analysis of reconstruction algorithms under generative priors is, however, challenging. For generative priors with fully connected layers and Gaussian i.i.d. weights, this was achieved by the multi-layer approximate message (ML-AMP) algorithm via a rigorous state evolution. However, practical generative priors are typically convolutional, allowing for computational benefits and inductive biases, and so the Gaussian i.i.d. weight assumption is very limiting. In this paper, we overcome this limitation and establish the state evolution of ML-AMP for random convolutional layers. We prove in particular that random convolutional layers belong to the same universality class as Gaussian matrices. Our proof technique is of an independent interest as it establishes a mapping between convolutional matrices and spatially coupled sensing matrices used in coding theory. 

Multi-layer State Evolution Under Random Convolutional Design
Max Daniels Northeastern University
Cédric Gerbelot
ENS Paris
daniels, www.rtheasteeen.ncmmmmmmm edu
cedric.gerbeloteenns
Florent Krzakala IdePHIcs Laboratory, EPFL kraeenttkkzaaaaaaeeppe.e.
Lenka Zdeborová SPOC Laboratory, EPFL
Lenka..zieborova@epp...c
Abstract
Signal recovery under generative neural network priors has emerged as a promising direction in statistical inference and computational imaging. Theoretical analysis of reconstruction algorithms under generative priors is, however, challenging. For generative priors with fully connected layers and Gaussian i.i.d. weights, this was achieved by the multi-layer approximate message (ML-AMP) algorithm via rigorous state evolution. However, practical generative priors typically convolutional, allowing for computational benefits and inductive biases, and so the Gaussian i.idd. weight assumption is very limiting. In this paper, overcome this limitation and establish the state evolution ML-AMP for random convolutional layers. We prove particular that random convolutional layers belong the same universality class as Gaussian matrices. Our proof technique is of an independent interest as it establishes mapping between convolutional matrices and spatially coupled sensing matrices used in coding theory.
Introduction
In a typical signal recovery problem, one seeks to recover data signal Zo given access to measure- ments yo (G())) where the parameters of the signal model known. In many problems, it is natural to view the measurement generation process as a composition of simple forward operators, or 'layers.' In this work, are concerned with multi-layer signal models the form (*))) Io; (()))..)).
Go(zo) ()) (()))
where ((()) 1 X are linear sensing matrices and where (000 (2; ()) are separable channel functions that may be non-linear and may depend on unknown channel noise Ç. In the multi-layer case L 1, this signal model can viewed as simple instance of recovery under Generative Neural Network (GNN) prior, technique which has recently shown promise as generalization of sparsity priors for signal processing applications [ora et al. [017]] For example, Gaussian compressive sensing yo AGo(xo) under prior with random Gaussian weights can be naturally viewed as an instance of the multilayer signal model, and given an estimate åt, one can recover the target signal = G²) from the weights (w(") and noise-independent channel functions (p(((())))
In practical settings GNNs often use structured convolutional weight matrices, preventing the direct application of estimators that require (1()) to have unstructured entries. Motivated by this, we take interest in a variant of the recovery problem in which some of the sensing matrices W/( may be
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Sparse Compressive Sensing (q = P 1024)
AMP Iterates for p= 0.25 (g 1024)
9- 0.4
Inc/MSE)
(SE))
0.15
0.5
-6-
-6-
0.55
MOC
Dense AMP
-10
Deuse SE
0.0
0.2
0.1
0.66
0.8
1.0
60
Measurement Ratio
AMP Iteration
Figure 1: Agreement between the performance of the AMP algorithm run with random multichannel convolutional matrices and its state evolution as proven in this paper. (left) Compressive sensing Yo W Zo + for noise Çi N/, 10 +) and signal prior Ip po 1) + p))(z)), where W E R Dax Py has varying aspect ratio 3 = D/P. Crosses correspond to AMP evaluations for W MCC(D, P.q. k.) according to Definition 3.2 averaged over 10 independent trials. Dots correspond to AMP evaluations for W E IR Dx with i.i.d. Gaussian entries Wij ~ .N(0, 1/P). Lines show the state evolution predictions when Wa₃ (O 1/Pg). The system size is P 1024, q 1024, k = 3, where 3 and D 3P vary. While our theorem treats the limit P. D - oc, 4, k = O(1), we observe strong empirical agreement even when y ~ P. Appendix C.1 we give the same figure for q 10 < P. (right) AMP iterates at p 0.25 and near the recovery transition. Rather than showing these models have equivalent fixed points, we show a stronger result: the state evolution equations equivalent each iteration.
multi-chammel convolutional (MCC) matrices, having a certain block-sparse circulant structure which captures the convolutional layers used by many modern generative neural network architectures Karras et al. 2018 2019].
In this work, develop an asymptotic analysis of the performance of an Approximate Message Passing (AMP) algorithm Donoho et al. [2009] for recovery from multichannel convolutional signal models. This family of algorithms originates in statistical physics Mézard and Montanari (2009). )
Zdeborová and Krzakala 2016) and allows to compute the marginals of an elaborate posterior distribution defined by inference problems involving dense random matrices. number of AMP
iterations have been proposed for various inference problems, such as compressed sensing Donoho al. 2009], low-rank matrix recovery Rangan and Fletcher 2012] or generalized linear modeling
Rangan 2011 More recently, composite AMP iterations (ML-AMP) have been proposed to study
multilayer inference problems Manoel et al. (017). Aubin et al. [2019]. Here we consider the
ML-AMP proposed in Manoel et al. [207]] to compute marginals of a multilayer generalized linear model with unstructured random weights, but we replace these weights random convolutional weight matrices. A major benefit of AMP lies in the fact that the asymptotic distribution of their iterates can be exactly determined by a low-dimensional recursion: the state evolution equations. This enables to obtain precise theoretical results for the reconstruction performance of the proposed algorithm. Another benefit of such iterations is their low computational complexity, as they only involve matrix muttiiiiuutiiiiaaiionn and, in the separable case, pointwise non-linearities.
Previous works on AMP suggest that the state evolution is not readily applicable to our setting because its derivation requires strong independence assumptions on the coordinates of the (W() which are violated by structured multi-channel convolution matrices. Despite this, we use AMP for our setting and rigorously prove its state evolution. Our main contributions are:
1. We rigorously prove state evolution equations for models of the form ①. where weights are allowed to be either i.i.d. Gaussian or random structured MCC matrices, as in Definition 3.2
2. For separable channel functions (P) and separable signal priors, we show that the original ML-AMP of Manoel et al. 2017 used with sensing matrices that are either dense Gaussian matrices or random convolutional ones admits the same state evolution equations, up to rescaling. Multi-layer MCC signal models can therefore simulate dense signal models while making use of fast structured matrix operations for convolutions.

---

3. The core of our proof shows how an AMP iteration involving random convolutional matrices may be reduced to another one with dense Gaussian matrices. We first show that random convolutional matrices are equivalent, through permutation matrices, to dense Gaussian ones with a (sparse) block-circulant structure. We then show how the block-circulant structure can be embedded in new, matrix-valued, multilayer AMP with dense Gaussian matrices, the state evolution equations of which are proven using the results of Gerbelot and Berthier [].2T]. with techniques involving spatially coupled matrices Krzakala et al. 2012 Javanmard and Montanari (2013).
4. We validate our theory numerically and observe close agreement between convolutional AMP iterations and its state evolution predictions, as shown Figure [ and in Section
Our code can be used as general purpose library to build compositional models and
evaluate AMP and its state evolution. We make this code available at
com momn/mmnlll 8/ /ec/vovmm -amp. git
2
Related Work
AMP-type algorithms arose independently in the contexts of signal recovery and spin-glass theory. In the former case, Donoho et al. [2009] derives AMP for Gaussian compressive sensing. This approach
was later generalized by Rangan 2011] to recovery problems with componentwise channel functions
functioos
that may be stochastic and/or nonlinear, and generalized further by Manoel et al. [2017] to multi-
or compositional models. Due to the versatility of this approach, a wide variety of general purpose frameworks for designing AMP variants have since been popularized Fletcher et al. [2018] Baker
et al. 2020), Gerbelot and Berthier 2021]. J. Proof techniques to show the concentration of AMP iterates to the state evolution prediction developed alongside new variants of the algorithm. In the context of spin-glan -lans theory, Bolthausen's 's seminal work BBlthausen (2009) introduces a Gaussian conditioning technique used widely to prove AMP concentration. Following this approach. [Baati and Montanari| [201T] Javanmard and Montanari (2013), Berthier et al. (2020) treat signal models with dense couplings and generalized channel functions. More recently, proof framework adaptable to composite inference problems was proposed in Gerbelot and Berthier [202]] which we use in our proof.
There has also been significant interest in relaxing the strong independence assumptions required by AMP algorithms sensing matrix coordinates. In one direction, Vector AMP (VAMP) algorithms target signal models whose sensing matrices are drawn from right orthogonally invariant distributions.
The development of VAMP algorithms followed similar trajectory to that of vanilla AMP (Schnttrr
et al. 2016), Fletcher et al. [2018), Rangan et al. (2019), Baker et al. 2020 The MCC ensemble considered this work is not right orthogonally invariant, but we observe strong empirical evidence that an analogous version of Theorem 4.2 holds for VAMP as well, as described in Appendix
+ second direction, there has been much interest in spatial coupling sensing matrices, which were used to achieve the information- teett-hhhorecallyy optimal performance in sparse compressive sensing Donoho
In a
ct al. (2013) Barbier et al. [2015). Krzakala et al. (2022). with complementary state evolution guarantees Javanmard and Montanari 20133] The concept of spatial coupling and proof' of its
performance originated in the literature of error correcting codes Kudekar et al. 2011 2013). where
it developed from the so-called convolutional codes Felstrom and Zigangirov [999]. The connection
between spatial coupling and convolution layers of neural networks, that we establish in this paper, is as far as we know novel.
Another direction of related work is the design of generative neural network architectures, and correspondingly, the design of signal recovery procedures that can make use of new generative prior models. [Bora al. [2017. J, one of the original works on compressive sensing with generative models, studies signal recovery under a fully connected VAE prior and a convolutional DC-GAN prior. More advanced convolutional architectures such as PG-GAN Karras et al. (0018) and Style-GAN Baale-GAKKarraas et al. [2099] have been studied in followup work as priors for a variety of signal recovery problems Daras et al. [2021) Gu al.] [2020]. For simplicity and theoretical tractibility, we do not consider some -raiind practical modifications used by these architetures, like batch normalization Lofte
and Szegedy 2015) or strided convolution layers Radford et al. (2015), focusing instead on the
essential elements of simple convolutional networks. Lastly, while our focus is on feedforward
convolutional priors such as GAN/VAE networks, there is growing interest in alternative approaches
to signal recovery under neural network priors, such as normalizing flows Rezende and Mohamed
3

---

Figure 2: MCC matrices operate Pg dimensional input data, composed of q-dimensional signals for each of P separate channels. The i-th output channel is a linear combination of convolutional features extracted from input channels, where is the convolutional filter size: y = E== Cizzo()), Each row of a concatenation of P different rows from convolutional matrices, each row hvaing nonzero entries, for total of kP nonzero entries. Blue boxes show which &P input entries contribute to single output entry.
2013 Dinh al. 2015 2017]. Kingma and Dhariwal [2018] Asim al. 2020 and score-based
generative models Song and Ermon 2020 Jalal et al. 2021 These approaches fall outside the scope of our work and may be interesting directions for future investigation.
3 Definition of the problem
3.1 Multi-channel Convolutional Matrices
We focus our attention multichannel convolution matrices that have localized convolutional filters. In this section, we introduce our notation and define the random matrix ensembles which are relevant to our result. We consider block structured signal vectors x E PR of the form refer to the blocks (+)) E R2 as 'channels.' For any vector of dimension d, we denote by Pa E Rdxd cyclic coordinate permutation matrix of order d, whose coordinates are (es, Paeş) 1 j + 1]. For block-structuree vector
[xx(1] A=1- and we
TR we denote by Pr.g E PRx the block cyelic permutation matrix satisfying (PPg))(0) = (i+1) for S < P, and (Pr.I)()) = (2)), Similarly, we denote the swap permutation matrix which exchanges blocks i, [St (1) = x(1)
by Sty E R PaxxxF Pa
[S),)((()) = ,(i), and [Str=]((k) = (*)) for k & i,j. Last, given a vector w E I& for k S denote by Zero-Padee (azo-Pad,,(w)) the vector whose first coordinates are w. and whose other coordinates zero.
(wr (w] W2 Wek
E R
We define the following ensemble for random multi-channel convolution matrices. Definition 3.1 (Gaussian i.i.d. Convolution). Let 2 k be integers. The convolutional en- semble C(g. k) contains random circulant matrices C' E I2*0 whose first row is given by C Zero- peero-pad..e [w] where w IR has i.i.d. Gaussian coordinates w, (O, 1/k). The remaining rows C, determined by circulant structure, ie. C; -P "ezzorrrpdd....
Random multi-channel convolutions are block-dense matrices with independent C(g. k) blocks.
Definition 3.2 (Multi-channel Gaussian i.i.d. Convolution). Let D, P and q 2 k > 1 be integers. The random multi-channel convolution ensemble M(D, k. () contains random block matrices M E R Pax of the form
C1.1
C12
CLP
C2
M
VP
LCD,1
CD.P.
where each Ct. ~ C(g, k)) is sampled independently.
Fig. 2 gives a graphical explanation of the link between these matrices and the convolutional layers. The parameter P (D) the number of input (output) channels, q is the dimension of the input and the filter size.

---

Layer
D
P
q
k
1+2
2
1024
512
4"
I
3
512
256
8²
5
+4
256
128
16a
5
4
128
3
64
5
Figure 3: System sizes for convolutional layers in a DC-GAN architecture used to generate LSUN images [Radford al. 2013) Figure 1J. These not directly comparable MCC matrices, as DCGAN uses fractionally strided convolutions, which can be thought of as composition of an MCC matrix with superresolution. However, they give reasonable picture of the sizes of typical layers in convolutional neural networks.
3.2 Thermodynamic-like Limit and Finite-size Regimes
We prove our main result in a thermodynamic-like limit D, - oo while 3 D/P fixed and q, k ((1). From a practical perspective, convolutional layers in deep neural networks often use large channel dimensions (D, P > 1), large signal dimensions (g > 1), and a small filter size (k O()).. As an example, we show in Figure 3 the sizes of convolutional layers used by the
DC-GAN architecture to generate LSUN images [Radford et al. 2013 Figure 1].
Interestingly, our theoretical predictions do not depend explicitly on the relative sizes of q and (D, P). We observe empirically that these predictions become accurate at finite sizes of (D, P) which may seem small relative to and which are realistic from practical neural network perspective. For example, in Figure (3 and D BP vary.
[ we observe strong empirical agreement with predictions for g P 1024 as
3.3 Multi-layer AMP
In this section, define class of probabilistic graphical models (PGMs) that captures the inference problems of interest, and we state the Multi-layer Approximate Message Passing (ML-AMP) Manoel al. 2017 iterations, which can be used for inference these PGMs. We consider the following signal model.
Definition 3.3 (Multi-layer Signal Model). Let (W() JIsKEL be matrices of dimension W(() e R=1-1=m__ Let (5000 (z; sssss be scalar channel functions for which 2 is the estimation quantity and ( represents channel noise. For vectors 2,5 E RR=-1,, we write (ot) () to indicate the coordinatewise application of cp()) The multi-layer GLM signal model is given by
y = ( (w()) (P)) (W.))). (...) (W(());;
We assume RT follows a known separable prior, I, ~ Px (x)) i...d., and that the channel noise (1) has i.d. (0, (a()) coordinates of known variance (a())2 2 0.
The full estimation quantities of the model are the coordinates of the vectors ( JisisL {2() hstgi, which are related by
yn ( (=()))()
(1) Σ W (1a)) ui
11T0 (21);
2 Σ w (2) (::0
11(-11 (1(1
(1) = Σ w
where we take (4) = Zo. The corresponding conditional probabilities, which define the factor nodes of the underlying PGM, are given by
p00 (ll 2) = - -d= ((x))(z)))
5

---

To compute the posterior marginals, ML-AMP iteratively updates the parameters of independent 1D Gaussian approximations each marginal. Each coordinate 1/ (t) has corresponding parameters {A4" (t), _ (t)} and each 2 (t) has corresponding {V/ (t), w/t ( (t)}, where 2 1 indexes the ML-AMP iterations. The recursive relationship between these parameters is defined in terms of scalar denoising functions, h()) and g(), which compute posterior averages of the estimation quantities given their prior parameters.
In general, these denoising functions can be chosen (up regularity assumptions) to adjust ML- AMP's ' performance in applied settings, such as in Metzler et al. (2015), and in these cases the denoisers may be nonseparable vector valued functions. However, the separable, Bayes-optimal regime where (x) and p&) (h 2) are known, the optimal denoisers are given by,
A (t + 1) == 0g log Z ((4)) !!!,, v,(+1), woft (((+1))
(3)
of 0 (t + 1) == hgh; (1) (t 1)
0 (t) == aw log 2 (A (()1)) 1B ((( " ;,,,,/9)
" (l) =- 0 (1)
/ p()( exp
1
(2- w)2
2 (A, B, V1 w) = V2TV
Bh
2 Ahh
dh dz
2V
where 2 S L, < I, 1, 2 2 and the prior parameters on the right hand side are taken at iteration t t2 2. The corresponding ML-AMP iterations are given by,
(t) = Ew o (t)
( = Σ w 1100 (t) (t)
(4)
(1) = Ei (t)
B (1) = Σ w of ( +
(1)
For the boundary cases = 1,/== 1, and ( = L, the iterations
are modified as follows.
1. At = 1, we initialize B(D) p!!) and will
p!!) where p!!) Pll are the distributions Bo We take (A (4())-== Var (B()) and
of the signal model parameters when ot Px.
Vy0) (w))
(1) (f) = 8, log 20) (y, (i( wol where
2. At = 1, the denoiser 9p
2 (y, (11) w (2))
2m / p(i)(y) ex)
1
(z (z- wfll
2V dz.
3. At L, the denoiser 1 (t) dB log Z(L (A! _B!l)), where
(A B! B( / (h) B - A n²)
dh.
3.3.1 Computational Savings of MCC Matrices
As ML-AMP requires only matrix-vector products, its computational burden can be significantly reduced when using structured and/or sparse sensing matrices. In our setting, multi-channel con- volutions M ~ MCC(D, P, q, k) have DPI: nonzero coordinates, compared to DPy² nonzero coordinates of Gaussian i.i.d. matrix. Typically, k represents the size of localized filter applied to a larger image, with &o < q [Gonzalez and Woods) 2008 Section 3.4], leading to significant space savings by a factor k/9². This same is true in convolutional neural networks, where the use of localized convolutional filters represents an inductive bias towards localized features that is considered a key aspect of their practical success Krizhevsky et al. 2012 Zeiler and Fergus 2014].
In addition to space savings, specialized matrix-vector product implementations can reduce the time complexity of ML-AMP with MCC sensing matrices. Simple routines for sparse matrix-vector products run in time proportional to the number of nonzero entries, resulting in the same k/q² constant factor speed up for MCC matrix-vector products. Alternatively, if l: > log y, then simple algorithm using a fast Fourier transform for convolution-vector products yields time complexity DDPg log q). Such algorithm is sketched Appendix B

---

4
Main result
We now state our main technical result, starting with the set of required assumptions.
(AI) for any & I < L, the function (2 <) is continuous and there exists a polynomial 600) of finite order such that, for any x E IR, (xx) c) < (x,
(A2) for any < 1 < L, the matrix W() is sampled from the ensemble M(D', Pl, ", where
p' Di g'
(A3) the iteration 4 is initialized with a random vector independent of the mixing matrices verifying
N [|boll2 +oo almost surely, and the prior distribution Px is subGaussian
(A4) for any 1 < & L, Dr, + oo with constant ratio 31 = Di/ with finite qt
Under these assumptions, we may define the following state evolution recursion Definition 4.1 (State Evolution). Consider the following recursion,
R00 (t) -3 =0 ( b,, - kx (1 [h h (R(U-)) ,,, (0(),, h)],
(5)
(6)
where 7()) is the second moment of P!l) where the right hand side parameters are taken at time t, and the expectations E(!) are taken with respect to
(w, 2, h, 6) P(0 (h) 2) w, ((0) - x) N(w; 0, N Nb; h,, Rl111)).
At 1, the state evolution is initialized at (()) 0 and (A())-1= ,() At the boundaries / 1, L. the expectations are modified analogously to the ML-AMP iterations as described by Manoel et al. [207]] We then have the following asymptotic characterization of the iterates from the convolutional ML-AMP algorithm
Theorem 4.2. Under the set of assumptions (A1)-(A4), for any sequences of uniformly pseudo- Lipschitz functions v 1/2 of order k; for any 1 & & T. and any i E N, the following holds
Dige
dh (1),
B
B (0)
E w/ (1), 20 (1)
Digi
Pig
(2 B() P E
(z(++)
(t), (0))
(8)
Piq
where ~N(, (t) ~ (0, A (t)) are independent random variables.
4.1
Proof Sketch
The proof of Theorem which is given in Appendix A has two key steps. First, construet permutation matrices U, Ú such that for W MCC(D, P. q, k), the matrix W = ÜWÜT is a block matrix whose blocks either have i.i.d. Gaussian elements or are zero valued, and has a block-circulant structure. The effect of the permutation is that entries of W which are correlated due to circulant structure of W are relocated to different blocks. Once these permutation matrices are defined, we define new, matrix-valued AMP iteration involving the dense Gaussian matrices obtained from the permutations, and whose non-lincarities account for the block-circulan structures and the permutation matrices. The state evolution of this new iteration is proven using the results of Gerbelot and Berthier (2021]. This provides an explicit example of how the aforementioned results can be used obtain rigorous, non Bayes-optimal SE equations on a composite AMP iteration. The separability assumption is key in showing that the AMP iterates obtained with the convolutional matrices can be exactly embedded a larger one. Note that this is a stronger result than proving SE equations for an algorithm that computes marginals of random convolutional posterior: we show the SE equations are the same as in the dense case. We finally invoke the Nishimori conditions, see e.g. Krzakala et al. 2012), to simplify the generic, non Bayes-optimal SE equations to the Baycs-optimal ones.
7

---

232
811
813
W11
W1z
211
M012
R18
9713
P28
1/22
M/25
F32
193
F53
M31
1782
8038
222
R42
R43
1141
MF42
W/45
291
Pga
R11
R12
R13
1011
W/1
1121
1122
P22
1125
Pg3
R21
Pg2
Pg5
1/22
M/2
251
230
M138
Rat
Ras
W512
20g1
10gg
730
6033
F41
A42
Fgg
M043
W44
2148
2111
Waz
M01
R11
213
241
0721
212
60
245
1043
1042
0563
10335
0041
1242
262
Figure 4: A sketch of the permutation lemma applied to matrix W MMCC(4,,,322) Left: W before permutation. Right: after permutation, UWÜT.
The idea of embedding non-separable effect such as block-circulant structure or different variances mixing matrix the core idea in the proofs of SE equations for spatially coupled systems, notably as done in Javanmard and Montanari [2013] Donoho et al. [2013] We note that in the numerical experiments shown at Figure the parameter g, considered finite in the proof, is actually comparable to the number of channel, considered to be extensive. Empirically
observe that this does not hinder the validity the result, something that was also observed in the spatial coupling literature, e.g. Krzakala al. [2012], where large number of different blocks in spatially coupled matrices were considered, with convincing numerical agreement.
The existence of permutations matrices verifying the property described above is formalized in the following lemma:
Lemma 4.3 (Permutation Lemma). Let W M,D, lt, q) be multi-channel convolution matrix.
There exist and column permutation matrices U E R. DoxD2 Ü TR Pyxx such that W UW ÜT is block-convolutional matrix with dense, Gaussian i..d. blocks. That is,
(
A
A(k)
A
A
A
W
A
(A))
Vk
(2))
A33)
A
A
where each ( E ERP.P 15 h has i..dd \ 1/P) coordinates.
Proof. Consider the elements of the matrix M which are non-zero and sampled i.i.d. as opposed to exact copies of other variables. They positioned on the first row of cach block of size q g, and thus the indexing for their rows and columns can be written as Mag+1d0+e where a, b, e are integers such that 0 E D 1. & b & P - and & & k. The integers a, describe the position of the q x block the variable is in, and describes, for each block, the position in the initial random Gaussian vector of size i that is zero-padded and circulated generate the block. The goal is to find the mapping that groups these variables into A: dense blocks of extensive size D x P. To do so, one can use the following bijection M M = Mag+1.69te where y = a + 1, a = c - 1 and 3= b 1. By doing this, becomes the block index and a, become the position in the dense block. This mapping can be represented by left and right permutation matrices which also prescribe the permutation for the rest of the elements of M. Figure shows sketch of this permutation.
L
The state evolution recursion given in Definition 4.1 equivalent to the state evolution for unstructured matrices proposed by Manoel et al. [2017). which may seem surprising relative to existing literature on spatial coupling, where spatially coupled sensing matrices are used achieve improved performance over unstructured sensing matrices. This equivalence
consequence the fact that W' has dense Gaussian blocks which each have the same variance, whereas in the literature, spatially coupled matrices typically have Gaussian blocks with inhomogeneous variances that can tuned to improve recovery performance.

---

Numerical Experiments
In this section, we compare state evolution predictions from Theorem with a numerical imple- mentation of the ML-AMP algorithm described in Section 3.3 Our first experiment, shown in Figure I a noisy compressive sensing task under a sparsity prior Px(x) - (x; + (1 - p))(2), where is the expected fraction of nonzero components of Ip- Measuremements
generated Vo = W xg + 1) for noise "i ~ (0, 10-*), where W ~ MCC(D, P. q, k). We show recovery performance sparsity levels p {0.25, 0.5, 0.75) as the measurement ratio 3 D/P varies, averaged over 10 independent AMP iterates. Additionally, we show convergence of the (averaged) AMP iterates for sparsity p 0.25 at range of 3 near the recovery threshold. We observe strong agreement between AMP empirical performance and the state evolution prediction. The system sizes P 1024, q 1024, with D 3P varying.
In In Figure 5 we consider two examples of L 2,3, layer models following Equation both, the output channel
generates noisy, compressive linear measurements y = 2 + for Si ~ (0, r²) and for dense couplings W. ~ / ~V00, 1/n(1). Layers 2 I < 4 use MCC couplings
W MCC(D;, Pr,g, k), where q ny and D. = BP ------ Channel functions (xp(0 vary across the two experiments. The input prior is (x(2z) = (xx;; 0, 0) and the problem parameters
are 10 channels, filter size k = 3, noise level x² = 10-4, input dimension n = 5000, and layerwise aspect ratios ((L) = 2 and g( = for < 1 < L. Finally, the channel aspect ratio 3(1) varies in each experiment.
Linear Activations
ReLU Activations
L= 2
2
-2
L 3
3
MCC AMP
MOC AMP
MSE)
Denoe AMP
Decaee AMP
Dense
Decave
-6-
0.4
0.6
0.8
1.0
0.0
0.4
0.8
884 Measurement Ratio
(10 Measurement Ratio
Figure ML-AMP compressive sensing recovery under multichannel convolutional designs (crossed) and the state evolution for the corresponding fully connected model (lined). For comparison, also plot the corresponding fully connected AMP iterations (dotted), in which W e Dix with Wi (0, 1/P)), with the dimensions of the prior and output channel adjusted appropriately. Left: For < S L,, the channel functions are (2; = + Ç where & ~ oO). Right: For 2 < | < L, the channel functions are (2; = max(z, 0) where the maximum is applied coordinatewise. This channel function is the popular ReLU activation function used by generative
convolutional neural networks such as Radford et al. 2015 Bora et al. [2077]
We compare the state evolution equations to empirical AMP results in two cases. the left panel, we show multilayer models with identity channel functions, and in the right panel, we show models with ReLU channel functions. The latter captures a simple but accurate example of convolutional GNN.
Discussion and Future Work
We have proven state evolution recursions for the ML-AMP algorithm for signal recovery from multi- layer convolutional networks. We consider networks whose weight matrices are drawn either i.i.d. Gaussian or from an ensemble of random multi-channel convolution matrices. Interestingly, under a separable prior and separable channel functions, these two matrix ensembles yield the same state evolution (up to a rescaling). These predictions closely match empirical observations compressive sensing under sparsity prior (Figure ! and under multi-layer priors (Figure 5).

---

Based on the discussion in Section 4.1 the equivalence property is expected to break down if W is replaced by a block matrix Wap with dense Gaussian blocks organized in the same block- corculcir structure, with inhomogeneous variances. we discuss Appendix D by inverting the permutation lemma, Wap corresponds filters, which can be taken as simple model for structured convolutions. Inhomogeneous blocks can also easily incorporated the Graph-AMP framework using nonseparable denoisers, so the key elements of our proof also apply to the inhomogeneous case. This generalized model for MCC matrices represents an interesting direction for future exploration, whose state evolution is expected to diverge from that of the dense Gaussian ensemble.
multi-channel convolution Wsp sp with inhomogeneous convolutional
Acknowledgments and Disclosure of Funding
M.D. acknowledges funding from Northeastern University's 's Undergraduate Research and Fellowships office and the Goldwater Award. We also acknowledge funding from the ERC under the European Union's ' Horizon 2020 Research and Innovation Program Grant Agreement 714608- SMiLe, and by the Swiss National Science Foundation grant SNES OperaGOST, 200021 2003900
10

---

References
Muhammad Asim, Max Daniels, Oscar Leong, Ali Ahmed, and Paul Hand. Invertible generative models for inverse problems: mitigating representation error and dataset bias. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 1 119 of Proceedings of Machine Learning Research, pages 409. PMLR, 13-18 Jul 2020. URL
mlx
html
Benjamin Aubin, Bruno Loureiro, Antoine Maillard, Florent Krzakala, and Lenka Zdeborová. The spiked matrix model with generative priors. Advances in Neural Information Processing Systems, 32, 2019.
Antoine Baker, Benjamin Aubin, Florent Krzakala, and Lenka Zdeborová. Tramp: Compositional inference with tree approximate message passing. arXiv preprint arXiv:200400557,, 2020.
Jean Barbier, Christophe Schülke,, and Florent Krzakala. Approximate message-passing with spatially coupled structured operators, with applications to compressed sensing and sparse superposition codes. Journal of Statistical Mechanics: Theory and Experiment, 2015(5) 2015.
Mohsen Bayati and Andrea Montanari. The dynamics message passing on dense graphs, with applications compressed sensing. IEEE Transactions Information Theory, 57(2):764-785, 2011.
Raphael Berthier, Andrea Montanari, and Phan-Minh Nguyen. State evolution for approximate message passing with non-separable functions. Information and Inference: Journal of the IMA, 91):333-79, 2020. 2020.
Erwin Bolthausen. On the high-tempeen reehhtempertuure phase of the sherrington-Kirkpatice model, Sep 2009.
Ashish Bora, Ajil Jalal, Eric Price, and Alexandros G Dimakis. Compressed sensing using generative models. In International Conference on Machine Learning, pages 537-546. PMLR, 2017.
Giannis Daras, Joseph Dean, Ajil Jalal, and Alex Dimakis. Intermediate layer optimization for inverse problems using deep generative models. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 2421-2432. PMLR, 18-24 Jul 2021. URL https::/
mlr.press. v 33t1133//aaaaaa html
Laurent Dinh, David Krueger, and Yoshua Bengio. NICE: non-linear independent components estimation. In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Workshop Track Proceedings, 2015. UtLpttp::/ //tp:////rxxii wwwexivv..rggaaae abs 1410. 8516
Laurent Dinh, Jascha Sohl- DickkstDin and Samy Bengio. Density estimation using real NVP, In International Conference on Learning Representations, 2017, URL [tLl:ttttt:////eeeiiii
net//oorum?id=ikppoll
David L Donoho, Arian Maleki, and Andrea Montanari. Message-passing algorithms for compressed sensing. Proceedings of the National Acudemy of Sciences, (896445)):1944-1339 2009.
David L Donoho, Adel Javanmard, and Andrea Montanari. Information-theoree theoreticalyy optimal compressed sensing via spatial coupling and approximate message passing. JEEE transactions on information theory, (9(11):74344744 7464, 2013.
A Jimenez Felstrom and Kamil Sh Zigangirov. Time-varying periodic convolutional codes with low-density parity-check matrix. IEEE Transactions on Information Theory, 45(6):2181-2111, 1999.
Alyson K Fletcher, Sundeep Rangan, and Philip Schniter. Inference in deep networks in high dimensions. In 2018 IEEE International Symposium on Information Theory (ISIT), pages 1884_ 1888. IEEE, 2018.
Cédric Gerbelot and Raphaël Berthier. Graph-based approximate message passing iterations. arXiv preprint arXiv:2109.1199 11905, 2021.

---

Rafael C. Gonzalez and Richard E. Woods. Digital image processing. 3rd Edition. Pearson Education, 2008. ISBN 9780135052679.
Jinjin Gu, Yujun Shen, and Bolei Zhou. Image processing using multi-code gan prior. In CVPR, 2020.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In Francis Bach and David Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 448 456, Lille, France, 07-09 Jul 2015. PMLR. URL https://
proceedings
html
Ajil Jalal, Sushrut Karmalkar, Alex Dimakis, and Eric Price. Instance-optimal compressed sensing via posterior sampling. In Marina Meila and Tong Zhang, editors. Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 4709-4720. PMLR, 18-24 Jul 2021. URL pettss:/procest iig...ddnnn.....ooo v1 http/jaaallaaaataeaaaaaa
ngs. ml press/
Adel Javanmard and Andrea Montanari. State evolution for general approximate message passing algorithms, with applications to spatial coupling. Information and Inference: A Journal of the IMA, 2(2):115-14,, 2013.
Tero Karras, Timo Aila, Samuli Laine, and Jaakko Lehtinen. Progressive growing of GANs for improved quality, stability, and variation. In International Conference on Learning Representations, 2018. URL httl:atttt//pperevaaaa
Tero Karras, Samuli Laine, and Timo Aila. A style-based generator architecture for generative adversarial networks. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pages 4401-4410, 2019.
Durk P Kingma and Prafulla Dhariwal. Glow: Generative flow with invertible 1x1 convolu- tions. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Desa-Bianchi, and R. Gar- nett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Asso- ciates, Inc., 2018 URL https: sttpss:/prooeedinng wwwpliinnnnn....rnieeeeeeee.eeee
neurips www.rips..ceappee////..... httppapee/2..////1.... pddf
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolu- tional neural networks. Advances in neural information processing systems, 25, 2012.
Florent Krzakala, Mare Mézard, François Sausset, YF Sun, and Lenka Zdeborová. natistical-physicee based reconstruction compressed sensing. Physical Review X, 2(2):021005, 2012.
Shrinivas Kudekar, Thomas Richardson, and Rüdiger L Urbanke. Threshold saturation via spatial coupling: Why convolutional Idpe ensembles perform well over the bec. IEEE Transactions Information Theory, 57(2):803-834 2011.
Shrinivas Kudekar, Tom Richardson, and Rüdiger L. Urbanke. Spatially coupled ensembles universally achieve capacity under belief propagation. IEEE Transactions on Information Theory, 59(12):
7761-7813, 2013.
Andre Manoel, Florent Krzakala, Mare Mézard, and Lenka Zdeborová. Multi-layer generalized linear estimation. In 2017 IEEE International Symposium on Information Theory (ISIT), pages 2098-2102, IEEE, 2017.
Christopher Metzler, Arian Maleki, and Richard Baraniuk. Bm3d-amp: new image recovery algorithm based on bm3d denoising, In 2015 IEEE International Conference Image Processing (ICIP), pages 31 3116-3. IEEE, 2015.
Marc Mézard and Andrea Montanari. Information, physics, and computation. Oxford University Press, 2009.
Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation learning with deep convolutional generative adversaria networks. arXiv preprint arXiv:1511.0644 2015.
12

---

Sundeep Rangan. Generalized approximate message passing for estimation with random linear mixing. 2011 IEEE International Symposium on Information Theory Proceedings, pages 11722. IEEE, 2011.
Sundeep Rangan and Alyson K Fletcher. Iterative estimation of constrained rank-one matrices in noise. 2012 IEEE International Symposium on Information Theory Proceedings, pages 1246-1250. IEEE, 2012.
Sundeep Rangan, Philip Schniter, and Alyson K Fletcher. Vector approximate message passing. IEEE Transactions on Information Theory, 65(10):6664-6684, 2019.
Danilo Rezende and Shakir Mohamed. Variational inference with normalizing flows. In Francis Bach and David Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 1530-15333 Lille, France, 07-09 Jul 2015. PMLR. URL https: htattps://pzoceedinng
www.m..ppp.......... wtt.s.................. rww.dd/eeeeddeee..ee htmll
Philip Schniter, Sundeep Rangan, and Alyson K Fletcher. Vector approximate message passing for the generalized linear model. In 2016 50th Asilomar Conference Signals, Systems and Computers, pages 1525-1529. IEEE, 2016.
Yang Song and Stefano Ermon. Improved techniques for training score-based generative models. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
Lenka Zdeborová and Florent Krzakala. Statistical physics of inference: Thresholds and algorithms. Advances in Physics, 65(5):453-552, 2016.
Matthew D Zeiler and Rob Fergus. Visualizing and understanding convolutional networks. In European conference on computer vision, pages 818-833. Springer, 2014.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section
(c) Did you discuss any potential negative societal impacts of your work? [No] We believe that because of the theoretical nature of this work, any potential negative societal impacts would be highly indirect. We are not aware of any potential direct negative societal impacts to discuss.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section
(b) Did you include complete proofs of all theoretical results? [Yes] See Section and the Appendix
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] The code to
reproduce our results is included in supplemental material and will be made publically available on Github.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A] Our results do require training
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "aA3pvkp3dmL", "reviewer": "Reviewer_xNsM", "summary": "The paper establishes state evolution analysis of multi-layer approximate message passing algorithms used to find an input vector from multi-layer noisy measurements (or finding the latent code of generative models) with random convolutional layers or random Gaussian layers.  The proof is based on writing random convolutional layers in terms of random Gaussian matrices using permutation matrices (Lemma 4.3). The proof points to a connection between convolutional matrices and spatially coupled matrices in coding theory. The results are numerically verified for linear and multi-layer cases. \n", "questions": "* Regarding Definition 3.3, Generative priors do not have noise in them. Note that this is not a bias term, otherwise, the conditional distributions  like $P^{(l)}(h|z)$ are not needed. This can indicate that the paper is about multi-layer measurements and not generative priors. The authors should comment on what happens if the channel noise is assumed to be zero or non-random. If I am not mistaken, the analysis should remain valid (at least in $y=Ax$ case, where the Onsager correction disappears).  \n\n\n* The problem description of the paper is bit confusing specially when the connection with generative prior is mentioned. Generative priors  are used to parametrize a signal $s$ using $s=G_\\theta(x)$, and then solve an inverse problem $y=As$ using it, for example by gradient descent on $\\Vert y-AG_\\theta(x) \\Vert_2^2$.\n\nThe authors. However, mention: “one seeks to recover a data signal $x_0$ given access to measurements $y_0 = G_\\theta(x_0)$”. This seems to combine the generative prior and measurement model.  The measurements are typically of form $y=Ax$; one can try to incorporate it as the last layer of the generative model, which is implicitly done by the authors. See Page 1, and the choice $\\phi(z)=z$ which means $y=Wh$. However, this is not typical generative compressed sensing setup.  As I reflected in my summary, the paper can be seen as finding the latent code of a generative model, which can be useful in context of generative compressed sensing. In any case, there is a subtle difference between these cases, and the authors can comment to clarify it. \n\n* As far as I can see Manoel et al. 2017 consider a general random matrix with i.i.d. entries and not only Gaussian (in contrast with the claim in page 2). However, the matrices are still unstructured. It is good if the authors replace the term “dense Gaussian” with a more general term, say unstructured random matrices.\n\n* The last paragraph of “Related Work” section: the notion of stable training, mentioned in this paragraph, is a bit convoluted and ill defined. The stability issues of training GANs is very different from covariate shift related stability handled by batch norm. These are different notions of stability. Besides, I do not see the relevance of this discussion for the rest of the paper. \n\n* On flow based models, it is better to cite the original work of Rezende et al 2015 and Dinh et al. 2015 and then mention follow up works like GLOW, RealNVP.  \n\n* Note that Bora et al do not only consider convolutional models. They also use MLP variants of generative priors (VAEs).  ", "limitations": "The main limitation of the paper is the way it connects with existing works on generative priors. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n* Applying state evolution analysis in deep learning context is very interesting direction, which is explored here. Similarly, spatially coupled matrices and related theoretical works are an important and rich area of coding theory, and the connection with coding theory opens up an interesting perspective. \n* The paper is in general well written and covers related works in a clear and adequate way.\n* The proofs and derivations seem sound to me and tend to follow standard message passing derivations apart from Lemma 4.3. I have not checked the derivations line by line.\n\n**Weaknesses**\n\n* The problem considered in this paper and some of the assumptions are different from typical generative compressed sensing paper (putting aside the assumptions on randomness of parameters). Please see my comments below.\n* The core issue, related to the comment above, is to mix the notion of measurements and the notion of prior. Generative priors are not measurements in context of generative CS. In the paper, the layers of the generative model are measurements with their measurement noise (channel noise $\\zeta$ in Definition 3.3). See my comments below on the notion of channel noise.\n* Practical models do not have random convolutions but trained ones. The implication of the current approach for the trained models is not clear and not discussed in the paper. \n\nOverall, the paper has a valuable contribution and present that contribution properly, however, the connection with generative compressed sensing in style of Bora et al is not properly established. A particular deviation from standard networks is the notion of channel noise. I think that the framework can still be relevant for generative priors by considering it as the problem of inverting a network or finding the latent code. This would require some changes in the paper and its exposition.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Uoa6C9u-XaI", "reviewer": "Reviewer_LN3c", "summary": "This paper studies the problem of estimating a signal vector from an observation obtained via a multilayer convolutional model. The weights defining the convolutional model are assumed to be random (and known). The main contributions are an AMP algorithm for signal estimation and a theorem proving that state evolution accurately predicts the performance of AMP on this model.  Numerical results, presented for synthetic settings, show good agreement of  empirical performance and state evolution predictions.", "questions": "-- It is mentioned in the abstract and the introduction that the state evolution equations for the MCC model are the same for as the iid Gaussian case, upto rescaling. I find this surprising based on an analogy with spatial coupling, where AMP with spatially coupled matrices has a different state evolution from the iid Gaussian case. The authors should discuss this point after Definition 4.1/Theorem 4.2, and if possible, give some high-intuition on why the two SEs are the same.\n\n-- The blue shaded parts in Fig. 2 are confusing.  It's not clear why kP entries from the matrix on the left are connected to a single one on the right.\n\n-- the notation is Definition 4.1 (State evolution) is inconsistent with the theorem below. One uses m and \\hat{m}, while the other uses \\kappa and \\hat{\\kappa}. Do these refer to the same quantities?\n\n-- To have a state evolution result that can applied to compute asymptotic loss, like MSE, the test functions in Theorem 4.2 should also take as arguments h^l/x or z^l. Please also refer to the assumptions (on x and the noise) in Def. 3.3 in the theorem statement.\n\n-- In the definition of the multilayer model (in the display above eq. 2), the same noise variable  \\eta is used for each layer. If the \\eta's in each layer are indepdendent, please make this clear.\n\n-- The noise level \\eta in the simulations is chosen to be 10^{-4}, extremely small. Is this required to get a good match between empirical results and SE at reasonable dimensions?\n\n-- Below eq. (2), could you clarify whether h^L is taken to be x? \n\nTypos: \nl.33 : distributions --> distribution;   l.206: should be \"iteration (4)\" -- add parentheses around 4.", "limitations": "The random convolutional model is simplistic and omits many aspects of real convolutional networks, but the authors acknowledge this.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The technical contribution of extending the multilayer AMP and state evolution from iid Gaussian weight matrices to a specific class of random convolutional matrices is a nice one. The proof technique is clever: it uses permutatation matrices to shuffle the weight matrices so that the correlated entries are in separate blocks, and then invokes the graph-based AMP proposed to define a matrix-valued AMP for the permuted matrix.  The problem setting is a bit artificial since assumes that the weights are random (rather than learned from data), but in my opinion the novelty of the proof technique is a nice contribution. \n\nA weakness of the paper is the presentation. The paper is dense, some of which is due to the notation required to defined the convolutional matrices, but the notation is inconsitent and sometimes confusing. Key results and their implications should also be discussed in more depth to aid understanding. More details in the \"Questions\" section below. \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "AA-0lmAlSY9", "reviewer": "Reviewer_fcUP", "summary": "This paper provides a theoretical study on the multi-layer approximate message passing (ML-AMP) algorithm with sensing matrices in some of the layers being multi-channel convolution, which extends previous results with regular 2D sensing matrices in all layers. The main result is the state evolution equations presented in Sec. 4, derived under asymptotic limits on the shape of convolution matrices. Experimental evidence shows that the theoretical results align well with the simulation results.", "questions": "The paper may benefit from a discussion on why their theoretical result is of practical interests.", "limitations": "This is discussed at the end of the paper.", "rating": 7, "confidence": 1, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Originality**\n\nAs the paper explains, there is existing work on the analysis of ML-AMP for regular (2D) sensing matrices. The novelty of this work lies in extending such analysis for the case where the sensing matrices are convolutional.\n\n**Quality**\n\nThe paper seems to be providing a good quality theoretical result that aligns well with the simulation results, even though the analysis concerns an asymptotic case only.\n\n**Clarity**\n\nI find the paper to be very well written, with an informative introduction, sufficient background before presenting their main result and so on.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "2zPFigHuL_v", "reviewer": "Reviewer_paFy", "summary": "The submitted paper addresses multi-layer aproximate message-passing (ML-AMP) for signal recovery under multi-layer generative neural network priors (1), in which the activation (or denoiser in compressed sensing) is separable and the sensing matrices are sampled from the multi-channel convolution ensemble in Definition 3.2. ML-AMP was originally proposed by Manoel et al. [2017] for dense sensing matrices with zero-mean i.i.d. (Gaussian) elements. The submitted paper generalizes the existing ML-AMP to the convolutional case in Definition 3.2. \n\nThe main contribution is rigorous state evolution of ML-AMP for the multi-channel convolution ensemble, i.e. Theorem 4.2. The proof is fully based on graph-based AMP and its rigorous state evolution by Gerbelot and Berthier [2021]. The main technical contribution is Lemma 4.3, allowing us to transform any multi-channel convolution matrix into block-convolutional matrix with dense, zero-mean, and i.i.d. Gaussian blocks via permutation. When separable activations, i.i.d. signals, and i.i.d. channel noise in (2) are assumed, all  permutation matrices are absorbed into messages in graph-based AMP via the change of variables. Since graph-based AMP is general enough to model ML-AMP, ML-AMP for the multi-channel convolution ensemble reduces to a special case of graph-based AMP. \n\nThe state evolution result is also justified via numerical simulations for artificial data. No numerical simulations are presented to show the advantage of the multi-channel convolution ensemble against conventional dense Gaussian ensemble or practical usefulness of ML-AMP for real data.", "questions": "--(A1) assumes pseudo-Lipschitz activations of any finite order while conventional state evolution by Bayati and Montanari [2011] postulated the Lipschitz-continuity. When pseudo-Lopschitz activations are used, in my understanding, the boundedness of higher-order signal moments is required as the iteration t increases. Eventually, we need to assume the boundedness of all signal moments. Do not the authors need to assume any regularity conditions on the signal prior, such as sub-Gaussian? \n\n--The terminology \"line\" is a bit unclear. Clarify whether it means column or row. \n\n--\\tilde{W} in Lemma 4.3 is not displayed appropriately. It should be presented like (57) in Appendix A. ", "limitations": "The submitted paper is theoretical and therefore has no negative social impacts.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\nThe strength is the proof of Theorem 4.2. From a technical point of view, the main part of the contributions to prove the theorem might be in Gerbelot and Berthier [2021]. Nonetheless, it should be significant contributions to understand graph-based AMP and apply its framework to signal recovery under multi-layer generative neural network priors. If the framework were old results, such as Bayati and Montanari [2011] or Rangan et al. [2019], I would not have positive impression since they are (well) known in the NeurIPS community. However, graph-based AMP is state-of-the-art message-passing and therefore not fully understood in the community.  \n\nWeakness \nAs pointed out in Summary, the weakness of the submitted paper presents no numerical simulations to show the advantage of the multi-channel convolution ensemble against conventional dense Gaussian ensemble or practical usefulness of ML-AMP for real data. The paper only presents numerical simulations for artificial data with the so-called Bernoulli-Gaussian prior. At least the authors could add numerical comparisons between the multi-channel convolution ensemble and conventional dense Gaussian ensemble for artificial data. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept