A JOHNSON–LINDENSTRAUSS FRAMEWORK FOR RANDOMLY INITIALIZED CNNS
Year: 2021

Abstract:
How does the geometric representation of a dataset change after the application of each randomly initialized layer of a neural network? The celebrated Johnson– Lindenstrauss lemma answers this question for linear fully-connected neural networks (FNNs), stating that the geometry is essentially preserved. For FNNs with the ReLU activation, the angle between two inputs contracts according to a known mapping. The question for non-linear convolutional neural networks (CNNs) becomes much more intricate. To answer this question, we introduce a geometric framework. For linear CNNs, we show that the Johnson–Lindenstrauss lemma continues to hold, namely, that the angle between two inputs is preserved. For CNNs with ReLU activation, on the other hand, the behavior is richer: The angle between the outputs contracts, where the level of contraction depends on the nature of the inputs. In particular, after one layer, the geometry of natural images is essentially preserved, whereas for Gaussian correlated inputs, CNNs exhibit the same contracting behavior as FNNs with ReLU activation.

heading: 1 INTRODUCTION
text: Neural networks have become a standard tool in multiple scientific fields, due to their success in classification (and estimation) tasks. Conceptually, this success is achieved since better representation is allowed by each subsequent layer until linear separability is achieved at the last (linear) layer. Indeed, in many disciplines involving real-world tasks, such as computer vision and natural language processing, the training process is biased toward these favorable representations. This bias is a product of several factors, with the neural-network initialization playing a pivotal role (Sutskever et al., 2013). Therefore, we concentrate in this work on studying the initialization of neural networks, with the following question guiding this work.
How does the geometric representation of a dataset change after the application of each randomly initialized layer of a neural network?
To answer this, we study how the following two geometrical quantities change after each layer.
〈x, y〉 The scalar inner product between vectors x and y.1 ρ := 〈x,y〉‖x‖‖y‖ The cosine similarity (or simply similarity) between vectors x and y.
The similarity ρ ∈ [−1, 1] between x and y equals ρ = cos(θ), where θ is the angle between them. Consider first one layer of a fully connected neural network (FNN) with an identity activation (linear FNN) that is initialized by independent identically distributed (i.i.d.) Gaussian weights with mean zero and variance 1/N , where N is the number of neurons in that layer. This random linear FNN induces an isometric embedding of the dataset, namely, the similarity ρin between any two inputs, xin and yin, is preserved together with their norm: ρout ≈ ρ̄out = ρin, where ρout is the similarity between the resulting random (due to the multiplication by the random weights) outputs, Xout and Yout (respectively), and ρ̄out is the mean output similarity defined by
1We mean here a vector in a wider sense: x and y may be matrices and tensors (of the same dimensions). In this situation, the standard inner product is equal to the vectorization thereof: 〈x, y〉 = 〈vec(x), vec(y)〉.
ρout := 〈Xout, Yout〉 ‖Xout‖ ‖Yout‖ , and ρ̄out := E [〈Xout, Yout〉]√
E [ ‖Xout‖2 ] E [ ‖Yout‖2 ] . (1)
The proof of this isometric relation between the input and output similarities follows from the celebrated Johnson–Lindenstrauss lemma (Johnson and Lindenstrauss, 1984; Dasgupta and Gupta, 1999). This lemma states that a random linear map of dimension N preserves the distance between any two points up to an ǫ > 0 contraction/expansion with probability at least 1 − δ for all N > c log(1/δ)/ǫ2 for an absolute constant c. In the context of randomly initialized linear FNNs, this result means that, for a number of neurons N that satisfies N > c log(1/δ)/ǫ2,
P (|ρout − ρin| < ǫ) ≥ 1− δ So, conceptually, the Johnson–Lindenstrauss lemma studies how inner products (or geometry) change, in expectation, after applying a random transformation and how well an average of these random transformations is concentrated around the expectation. This is the exact setting of randomly initialized neural networks. The random transformations consist of a random projection (multiplying the dataset by a random matrix) which is followed by a non-linearity.
Naturally, adding a non-linearity complicates the picture. Let us focus on the case where the activation function is a rectified linear unit (ReLU). That is, consider a random fully-connected layer with ReLU activation initialized with i.i.d. zero-mean Gaussian weights and two different inputs. For this case, Cho and Saul (2009), Giryes et al. (2016), and Daniely et al. (2016) proved that2
ρout ≈ ρ̄out = √ 1− ρ2in + ( π − cos−1(ρin) ) ρin
π . (2)
Following Daniely et al. (2016), we refer to the resulting function in (2) of ρ̄out in ρin as the dual activation of the ReLU; this function is represented in figure 1 by the yellow curve.
One may easily verify that the dual activation (2) of the ReLU satisfies ρout > ρin for ρin 6= 1, meaning that it is a contraction. Consequently, for deep FNNs, which comprise multiple layers, random initialization results in a collapse of all inputs with the same norm (a sphere) to a single point at the output of the FNN (equivalently, the entire dataset collapses to a single straight line).
Intuitively, this collapse is an unfavorable starting point for optimization. To see why, consider the gradient ∇ w
(i) j
of the weight w (i) j of some neuron j in a deep layer i in a randomly initialized ReLU
FNN. By the chain rule (backpropagation), this gradient is proportional to the output of the previous layer a(i−1) for the corresponding input, i.e., it holds that ∇ w
(i) j ∝ a(i−1). If the collapse is present already at layer i, this output is essentially proportional to a fixed vector a∗. But this implies that, in the gradient update, the weights of the deep layer will move roughly along a straight line which would impede, in turn, the process of achieving linear separability.
Indeed, it is considered that for a FNN to train well, its input–output Jacobian needs to exhibit dynamical isometry upon initialization (Saxe et al., 2014). Namely, the singular values of the Jacobian ∂xout/∂xin must be concentrated around 1, where xout and xin denote the input and output of the FNN, respectively. If the dataset collapses to a line, xout is essentially invariant to xin (up to a change in its norm), suggesting that the singular values of ∂xout/∂xin are close to zero. Therefore, randomly initialized FNNs exhibit the opposite behavior from dynamical isometry and hence do not train well.

heading: 1.1 OUR CONTRIBUTION
text: Our main interest lies in the following question.
Does the contraction observed in randomly initialized ReLU FNNs carry over to convolutional neural networks (CNNs)?
As we will show, qualitatively, the answer is yes. However, quantitatively, the answer is more subtle as is illustrated in figure 1. In this figure, the similarity between pairs of inputs sampled at random
2The results in (Cho and Saul, 2009) and (Daniely et al., 2016) were derived assuming unit-norm vectors ‖xin‖ = ‖yin‖ = 1. The result here follows by the homogeneity of the ReLU activation function: R(αx) = αR(x) for α ≥ 0, and ergodicity, assuming multiple filters are applied.
from standard natural image datasets—Fashion MNIST (F-MNIST), CIFAR-10, and ImageNet—are displayed against the corresponding output of a randomly initialized CNN layer. For these datasets, clearly ρout ≈ ρin meaning that the relation of ReLU FNNs (2)—represented in figure 1 by the yellow curve—breaks down.
That said, for inputs consisting of i.i.d. zero-mean Gaussians (and filters comprising i.i.d. zero-mean Gaussian weights as before) with a Pearson correlation coefficient ρ between corresponding entries (and independent otherwise), the relation in (2) between ρ̄out and ρin of ReLU FNNs does hold for ReLU CNNs as well, as illustrated in figure 1a.
This dataset-dependent behavior, observed in figure 1, suggests that, in contrast to randomlyinitialized FNNs which behave according to (2), randomly-initialized CNNs exhibit a richer behavior: ρ̄out does not depend only on ρin but on the inputs xin and yin themselves. Therefore, in this work, we characterize the behavior of ρ̄out after applying one layer in randomly initialized CNNs.
We start by considering randomly initialized CNNs with general activation functions. We show in theorem 1 that the expected (over the filters) inner product E [〈Xout, Yout〉] and the mean similarity ρ̄out depend on xin and yin (and not just 〈xin, yin〉) by extending the dual-activation notion of Daniely et al. (2016). In theorem 2, we further prove that, by taking multiple independent filters, 〈Xout, Yout〉 and ρout of (1) concentrate around E [〈Xout, Yout〉] and ρ̄out, respectively. We then specialize these results to linear CNNs (with identity activation) and derive a convolutionbased variant of the Johnson–Lindenstrauss lemma that shows that 〈Xout, Yout〉 ≈ 〈xin, yin〉 and ρout ≈ ρin for linear CNNs, both in expectation (ρ̄out = ρin for the latter) and with high probability. For randomly initialized ReLU CNNs, we derive the following tight upper and lower bounds for ρ̄out in terms of ρin in theorem 3:
max{ρin, 0} ≤ ρ̄out ≤ 1 + ρin
2 . (3)
These bounds imply, in turn, that for ρin 6= 1 each ReLU CNN layer is contracting. In theorem 4 we prove that ρ̄out for random Gaussian data satisfies the relation (2), in accordance with figure 1a.
To explain the (almost) isometric behavior of CNNs for natural images (figure 1), we note that many natural images consist of large, relative to the filter size, approximately monochromatic patches. This observation leads to a simple model of black and white (binary) images with “large patches”. To describe this model mathematically, we define a notion of a shared boundary between two images in definition 2, and model large patches by bodies whose area is large compared to the shared boundary. We prove that ρ̄out ≈ ρin for this model, meaning that the lower bound in (3) is in fact tight.

heading: 1.2 RELATED WORK
text: In this paper, we study how various inputs are embedded by randomly initialized convolutional neural networks. Neural tangent kernel (NTK) (Jacot et al., 2018) is a related line of work. This setting studies the infinite width limit (among other assumptions) in which one can consider neural network training as regression over a fixed kernel; this kernel is the NTK. There are two factors that affect the calculation of the NTK: The embedding of the input space at initialization and the gradients at initialization. In this paper we study the first one.
Arora et al. (2019), and Bietti and Mairal (2019) give expressions for the NTK and the convolutional NTK (CNTK). Theorem 1 may be implicitly deduced from those expressions. Arora et al. (2019) provide concentration bounds for the NTK of fully connected networks with finite width. Bietti and Mairal (2019) derive smoothness properties for NTKs, e.g., upper bounds on the deformation induced by the NTK in terms of the initial Euclidean distance between the inputs. A related approach to NTK is taken in (Bietti, 2021) where convolutional kernel networks (CKN) are used.
Standard initialization techniques use the Glorot initializtion (Glorot and Bengio, 2010) and He initialization (He et al., 2015). Both were introduced to prevent the gradients from exploding/vanishing. On a similar note, Hanin and Rolnick (2018) discuss how to prevent exploding/vanishing mean activation length—which corresponds to the gradients to some degree—in FNN with and without skip connections. For a comprehensive review on other techniques see (Narkhede et al., 2021-06-28).
Schoenholz et al. (2017); Poole et al. (2016); Yang and Schoenholz (2017) study the initialization of FNNs using mean-field theory, in a setting where the width of the network is infinite. They demonstrate that for some activation functions there exists an initialization variance such that the network does not suffer from vanishing/exploding gradients. In this case, the network is said to be initialized at the edge of chaos.
As mentioned earlier, Saxe et al. (2014) introduced a stronger requirement than that of moderate gradients at initialization, in the form of dynamical isometry. for linear FNNs, they showed that orthogonal initialization achieves dynamical isometry whereas Gaussian i.i.d. initialization does not.
For non-linear FNNs, Pennington et al. (2017) show that the hyperbolic tangent (tanh) activation can achieve dynamical isometry while ReLU FNNs with Gaussian i.i.d. initialization or orthogonal initialization cannot. In contrast, Burkholz and Dubatovka (2019) show that ReLU FNNs achieve dynamical isometry by moving away from i.i.d. initialization. And lastly, Tarnowski et al. (2019) show that residual networks achieve dynamical isometry over a broad spectrum of activations (including ReLU) and initializations.
Xiao et al. (2018) trained tanh (and not ReLU) CNNs with 10000 layers that achieve dynamical isometry using the delta-orthogonal initialization. Similarly, Zhang et al. (2019) trained residual CNNs with 10000 layers without batch normalization using fixup-initialization that prevents exploding/vanishing gradients.

heading: 1.3 NOTATION
text: R,N,Z The sets of real, natural, and integer numbers, respectively.
∨,∧ The logical ‘or’ and ‘and’ operators, respectively. Zn, [n] The sets {0, 1, . . . , n− 1} and {0, 1, . . . , n− 1}. Aij , Tijk The (i, j) entry of the matrix A and the (i, j, k) entry of the tensor T , respectively.
[T ]rij The sub-tensor of T formed from rows i to i + r − 1 and columns j to j + r − 1 (and full third “layer” dimension).
Ik The identity matrix of dimensions k × k. vec(·) The vectorization operation of a matrix or a tensor in some systemic order. 〈x, y〉 The standard inner product between vectors x and y. For matrix or tensor x and y (of
the same dimensions) the inner product is defined as 〈x, y〉 = 〈vec(x), vec(y)〉. ‖x‖ The standard Euclidean norm, induced by the standard inner product: ‖x‖ = √ 〈x, x〉.
ρ The (cosine) similarity. The similarity between x and y is defined as ρ = 〈x,y〉‖x‖‖y‖ . ρ̄ The mean similarity. ρ̄ between random X and Y is defined as ρ̄ = E[〈X,Y 〉]√ E[‖X‖2]E[‖Y ‖2] .
σ, σ̂ An activation function and its dual, respectively, as defined in definition 1. R(x) The ReLU applied to x: R(x) := max{0, x}; for a tensor x the R is applied entrywise. R̂(ρ) The dual activation of the ReLU at ρ ∈ [−1, 1]: R̂(ρ) := √ 1−ρ2+(π−cos−1(ρ))ρ
π .
N (µ,C) A Gaussian vector with mean vector µ and covariance matrix C.

heading: 2 SETTING AND DEFINITIONS
text: The output z ∈ Rn×n of a single filter of a CNN is given by z = σ(F ∗ x)
where x ∈ Rn×n×d is the input; F ∈ Rr×r×d is the filter (or kernel) of this layer; and σ : R → R is the activation function of this layer and is understood to apply entrywise when applied to tensors. The dimensions satisfy n, d, r ∈ N, r ≤ n. The first two dimensions of x and z are the image dimensions (width and height), while the third dimension is the number of channels, and is most commonly equal to either 1 for grayscale images and 3 for RGB color images; r is the dimension of the filter; ‘∗’ denotes the cyclic convolution operation:
(F ∗ x)uv = ∑
i∈Zr,j∈Zr,k∈Zd Fijk · xu−i,v−j,k (4)
where the subtraction operation in the arguments is the subtraction operation modulo n. In this work, we will concentrate on the ReLU activation function which is given by σ(x) = max{0, x}. Typically, a single layer of a CNN consists of multiple filters F1, . . . , FN .
The following definition is an adaptation of the dual activation of Daniely et al. (2016) to CNNs. Definition 1 (Dual activation). The dual activation function σ̂ : Rn×Rn×R → R of an activation function σ is defined as
σ̂(x, y, ν) = E [σ(νX) · σ(νY )] for input vectors x, y ∈ Rn, and a parameter ν > 0, where
( X Y ) ∼ N (( 0 0 ) , ( ‖x‖2 〈x, y〉 〈x, y〉 ‖y‖2 )) . (5)
For tensors x, y ∈ Rn×n×d, the dual activation σ̂ is defined as in (5) with the inner products and norms replaced by the standard inner product between tensors:
〈x, y〉 = ∑
i∈Zn,j∈Zn,k∈Zd xijk · yijk, ‖x‖ =
√ 〈x, x〉.
In the special case of an activation that is homogeneous, i.e., satisfying σ(cx) = cσ(x) for c ≥ 0, we use an additional notation for −1 ≤ ρ ≤ 1, with some abuse of notation:
ν2σ := E [ σ(X)2 ] , σ̂(ρ) := E [σ(X) · σ(Y )] ν2σ ,
( X Y ) ∼ N (( 0 0 ) , ( 1 ρ
ρ 1
)) . (6)
This is the dual activation function of Daniely et al. (2016). Note that, by this definition, σ̂(1) = 1.
We will be mostly interested in the ReLU activation, denoted by R, for which the following holds (see, e.g., (Daniely et al., 2016, Table 1 and Section C of supplement))
ν2R := 1/2 , R̂(ρ) := E [R(X) · R(Y )]
ν2R =
√ 1− ρ2 + ( π − cos−1(ρ) ) ρ
π .

heading: 3 MAIN RESULTS
text: In this section, we present the main results of this work. The proofs of all the results in this section may be found in the appendix. Theorem 1. Let x, y ∈ Rn×n×d be inputs to a convolution filter F ∈ Rr×r×d with r ≤ n and activation function σ such that the entries of F are i.i.d. Gaussian with variance ν2. Then,
E [〈σ(F ∗ x), σ(F ∗ y)〉] = ∑ i,j∈Zn σ̂ ( [x]rij , [y] r ij , ν ) . (7)
In particular, for a homogeneous activation function we have
E [〈σ(F ∗ x), σ(F ∗ y)〉] = ν2 · ν2σ ∑
i,j∈Zn
∥∥[x]rij ∥∥ ∥∥[y]rij ∥∥ σ̂ (ρij) , (8)
E [ σ(F ∗ x)2 ] = ν2 · ν2σ · r2‖x‖2 , (9)
where ρij = 〈[x]rij ,[y]rij〉
‖[x]rij‖·‖[y]rij‖ and ν 2 σ has been defined in (6).
In particular, due to (9), for homogeneous activations we can choose ν = 1/(νσr) and get E [ σ(F ∗ x)2 ] = ‖x‖2. That is, the norms are preserved in expectation for every input x.
Note that theorem 1 may be deduced as a special case from existing more general formulas; see, e.g., Arora et al. (2019); Bietti and Mairal (2019). Nevertheless, it is an important starting point for us.
While theorem 1 holds in the mean sense, it does not hold for a specific realization of a single filter F , in general. The next theorem, whose proofs relies on the notions of sub-Gaussian and subexponential RVs and their concentration of measure, states that theorem 1 holds approximately for a large enough number of applied filters.
We apply basic, general concentration bounds on the activation. There exist sharper bounds in special cases, e.g., in the context of cosine similarity and ReLU, see (Buchanan et al., 2021, app. E). Theorem 2. Let x, y ∈ Rn×n×d be inputs to N filters F1, . . . , FN ∈ Rr×r×d with r ≤ n such that max i,j∈Zn ∥∥[x]rij ∥∥ ≤ R, max i,j∈Zn ∥∥[y]rij ∥∥ ≤ R, (10) all the entries of all the filters are i.i.d. Gaussian with zero mean and variance ν2, and a Lipschitz continuous activation function σ with a Lipschitz constant L and satisfying σ(0) = 0. Then, for δ > 0, however small,
P   ∣∣∣∣∣∣ 1 N N∑
ℓ=1
〈σ(Fℓ ∗ x), σ(Fℓ ∗ y)〉 − n∑
i,j=1
σ̂ ( [x]rij , [y] r ij , ν ) ∣∣∣∣∣∣ ≥ ǫ   ≤ δ (11)
for N > max ( K,K2 ) log 2n 2
δ , where K = Dν2L2R2n2/ǫ and D > 0 is an absolute constant.
Remark 1. Clearly, ‖[x]rij‖ and ‖[y]rij‖ in (10) may be bounded by ‖x‖ and ‖y‖, respectively. However, since r is typically much smaller than n, we prefer to state the result in terms of the norms of [x]rij and [y] r ij .
Theorem 2 states a concentration result in terms of the inner product. We now give a parallel result for homogeneous activations in terms of the cosine similarity ρout. To that end, consider a homogeneous activation σ and N random filters F1, . . . , FN ; for these filters, the quantities of (1) for two inputs x and y are equal to
ρout = ∑N ℓ=1〈σ (Fℓ ∗ x) , σ (Fℓ ∗ y)〉√∑N
ℓ=1 ‖σ (Fℓ ∗ x)‖ 2 √∑N ℓ=1 ‖σ (Fℓ ∗ y)‖ 2 , ρ̄out =
∑ i,j∈Zn ‖[x]rij‖ · ‖[y]rij‖σ̂ (ρij)
r2‖x‖ · ‖y‖ ,
(12)
where ρij is defined in theorem 1. Applying theorem 2 to these quantities, yields the following.
Corollary 1. Let x, y be inputs to N filters F1, . . . , FN such that
max i,j∈Zn ‖[x]rij‖ ‖x‖ ≤ R , maxi,j∈Zn ‖[y]rij‖ ‖y‖ ≤ R ,
all the entries of the filters are i.i.d. Gaussian with zero mean and variance ν2, and a Lipschitz homogeneous activation σ with Lipschitz constant L. Then, for 0 < ǫ ≤ 1/10 and δ > 0,
P ( |ρout(x, y)− ρ̄out(x, y)| ≥ ǫ ) ≤ δ
for N > max(K,K2) log 6n 2
δ , where K = DL
2R2n2
ǫν2σr 2 and D > 0 is an absolute constant.
Remark 2. To make sense out of the constants in corollary 1, we point out that applying it to inputs x, y ∈ {±1}n×n×d (so that ‖x‖2 = ‖y‖2 = dn2 and ‖[x]rij‖2 = ‖[y]rij‖2 = dr2) results in K = DL 2
ǫν2σ , which does not depend on n or ν2. There remains a log n2 factor that increases with n.
In the remainder of this section, we derive an analogous result to the Johnson–Lindenstrauss lemma (Johnson and Lindenstrauss, 1984; Dasgupta and Gupta, 1999) in section 3.1 for random linear CNNs, namely, CNNs with identity activation functions. We then move to treating random CNNs with ReLU activation functions: We derive upper and lower bounds on the inner product between the outputs in section 3.2, and prove that they are achievable for Gaussian inputs in section 3.3, and for large convex-body inputs in section 3.4, respectively.

heading: 3.1 LINEAR CNN
text: Theorem 1 yields a variant of the Johnson–Lindenstrauss lemma where the random projection is replaced with random filtering, that is, by applying a (properly normalized) random filter, the inner product is preserved (equivalently, the angle). Lemma 1. Consider the setting of theorem 1 with ν = 1/r. Then, E [〈F ∗ x, F ∗ y〉] = 〈x, y〉. Lemma 2. Consider the setting of theorem 2 with ν = 1/r (and σ(x) ≡ x). Then,
P (∣∣∣∣∣ 1 N N∑
ℓ=1
〈Fℓ ∗ x, Fℓ ∗ y〉 − 〈x, y〉 ∣∣∣∣∣ ≥ ǫ ) ≤ δ
for N > max ( K,K2 ) log 2n 2
δ , where K = DR
2n2
r2ǫ and D > 0 is an absolute constant.
Related result appears in Krahmer et al. (2014) (theorem 1.1) which shows norm preservation of sparse vectors for convolutional operators with a filter dimension that equals the input dimension.

heading: 3.2 CNN WITH RELU ACTIVATION
text: The following theorem implies that every layer of a neural network is contracting in expectation (over F ). That is, the expected inner product between any two data points will get larger with each random CNN layer. We also develop an upper bound on the new correlation.
Theorem 3. Consider the setting of theorem 1 with a ReLU activation function and variance ν = 2/r2, for inputs x and y with similarity ρ. Then,
max{〈x, y〉, 0} ≤ E [〈R(F ∗ x),R(F ∗ y)〉] ≤ ‖x‖ ‖y‖ 1 + ρ 2 , (13)
Remark 3. All the bounds in theorem 3 are tight. For simplicity, we present examples where the unit vectors x, y are flat, i.e., they are not tensors and r = 1. Similar examples can be drawn for tensor inputs and r > 1. The upper bound is realized for x, y ∈ R2 of the form x = (√ 1+ρ 2 , √ 1−ρ 2 ) ,
y = (√ 1+ρ 2 ,− √ 1−ρ 2 ) . Similarly, x, y ∈ R3 with x = (√1− ρ,√ρ, 0), y = (0,−√ρ,√1− ρ) satisfy 〈x, y〉 = −ρ and E [σ(F ∗ x)σ(F ∗ y)] = 0 for r = 1 and 0 ≤ ρ ≤ 1. Finally, we can take x = ( √ 1− ρ,√ρ, 0) and y = (0,√ρ,√1− ρ) to obtain 〈x, y〉 = E [σ(F ∗ x)σ(F ∗ y)] = ρ. These examples are illustrated in figure 3.
Remark 4. Although the lower bound is tight, in most typical scenarios it will be strict, so, in expectation, the convolutional layers will contract the dataset after application of enough layers. To see why, observe (23c); equality is achieved iff ρij = 1 ∨ [x]rij = 0 ∨ [y]rij = 0. For real data sets this will never hold over all (i, j). This can be observed in figures 1b, 1c, and 1d where the linear fit has a slope of 0.97.

heading: 3.3 GAUSSIAN INPUTS
text: The following result shows that the behavior reported by (Daniely et al., 2016) [and illustrated in figure 1a by the orange curve] for FNNs holds for CNNs with Gaussian correlated inputs; this is illustrated in figure 1a. For simplicity, we state the result for d = 1 (n × n inputs instead of n× n× d); the extension to d > 1 is straightforward. Theorem 4. Let X,Y ∈ Rn×n be zero-mean jointly Gaussian with the following auto- and crosscorrelation functions:
E [XijXkℓ] = E [YijYkℓ] = 1
n2 δikδjℓ, E [XijYkℓ] =
ρ
n2 δikδjℓ, (14)
i.e., X and Y have pairwise i.i.d. entries which are correlated with a Pearson correlation coefficient ρ. Assume further that the filter F ∈ Rr×r comprises zero-mean i.i.d. Gaussian entries with variance 2/r2 and is independent of (X,Y ). Then, for a ReLU activation function σ,
E [〈σ(F ∗X), σ(F ∗ Y )〉] = √
1− ρ2 + (π − cos−1(ρ))ρ π .

heading: 3.4 SIMPLE BLACK AND WHITE IMAGE MODEL
text: This section provides insight why we get roughly an isometry when embedding natural images via a random convolution followed by ReLU.
As a conceptual model, we will work with binary pictures {0, 1}n×n or equivalently as subsets of Zn×Zn. Also, when considering real-life pictures, an apparent characteristic is that they consist of relatively large monochromatic patches, so for the next theorem, one should keep in mind pictures that consist of large convex bodies.
To state our results, we define a notion of a shared r-boundary. Definition 2 (Boundary). Let A,B ⊂ Zn × Zn and let r ∈ [n]. Then, the r-boundary of the intersection between A and B, denoted by ∂r(A,B), is defined as the set of all pixels (i, j) ∈ Zn × Zn such that
∃a1, b1, c1, d1 ∈ {−r, . . . , r} : (i+ a1, j + b1) ∈ A ∧ (i+ c1, j + d1) ∈ B (15a) ∃a2, b2, c2, d2 ∈ {−r, . . . , r} : (i+ a2, j + b2) /∈ A ∨ (i+ c2, j + d2) /∈ B (15b)
where the addition in (15a) and (15b) is over Zn.
In words, a pixel (i, j) belongs to the r-boundary ∂r(A,B) if, considering the square with edge size 2r + 1 centered at the pixel: (1) the square intersects both A and B, (2) the square is not contained in A or is not contained in B. Example 1. Let A and B be axis-aligned rectangles of sizes a × b and c × d, respectively, and an intersection of size e × f where e, f ≥ 2r. Then, |∂r(A,B)| = 4r(e + f). This is illustrated in figure 2 in the appendix.
The next theorem bounds the inner product between A and B after applying a ReLU convolution layer in terms of the r-boundary of the intersection of A and B. Theorem 5. Let A,B ⊂ [n]× [n] and a convolution filter F ∈ R(2r+1)×(2r+1) such that the entries in F are i.i.d. Gaussians with variance 2/(2r + 1)2. Then,
〈A,B〉 − |∂r(A,B)| ≤ E [〈R(F ∗A),R(F ∗B)〉] ≤ 〈A,B〉+ |∂r(A,B)| , (16a) ‖A−B‖2 − 2|∂r(A,B)| ≤ E [ ‖R(F ∗A)− R(F ∗B)‖2 ] ≤ ‖A−B‖2 + 2|∂r(A,B)| . (16b)
Theorem 5 and corollary 1 imply
|ρout − ρin| ≤ ∂r(A,B)
‖A‖ ‖B‖ + ǫ
with high probability for a large enough number of filters N . This shows that a set of images consisting of “large patches”, meaning that ∂r(A,B) ‖A‖‖B‖ is small (as in example 1 for small r), is embedded almost-isometrically by a random ReLU convolutional layer. Moreover, any set of images may be embedded almost-isometrically this way. To see how, fix r while increasing artificially (digitally) the resolution of the images. The latter would yield ∂r(A,B) ‖A‖‖B‖ → 0 as the resolution tends to infinity.

heading: 4 DISCUSSION

heading: 4.1 GRAYSCALE VERSUS RGB IMAGES
text: The curious reader might wonder how the analysis over black-and-white (B/W) images can be extended to grayscale and RGB images. While we concentrated on B/W images in this work, the definition of a shared boundary readily extends to grayscale images as does the result of theorem 5. This, in turn, explains the behavior of the grayscale-image dataset F-MNIST in figure 1b.
For RGB images, the framework developed in this work does not hold in general. To see why, consider two extremely simple RGB images: Red—consisting of all-zero green and blue channels and a constant unit-norm red channel, and Green—consisting of all-zero red and blue channels and a constant unit-norm green channel. Clearly, 〈Red,Green〉 = 0. However, a simple computation, in the spirit of this work, shows that E [〈R(F ∗Red),R(F ∗Green)〉] = 1/π = R̂(0) which is far from 0. That is, for such monochromatic pairs, the network behaves as a fully connected network (2) and not according to the almost isometric behavior of theorem 5 and figure 1d.
So why does an almost isometric relation appear in figures 1c and 1d? The answer is somewhat surprising and of an independent interest. It appears that for the RGB datasets CIFAR-10 and ImageNet, the RGB channels have high cosine similarity (which might not be surprising on its own), and additionally all the three channels have roughly the same norm. Quantitatively—averaged over 104 images that were picked uniformly at random from the ImageNet dataset—the angle between two channels is ~12.5◦ and the relative difference between the channel norms is ~9.2%.
This phenomenon implies that our analysis for black and white images (as well as its extension to grayscale images) holds for RGB natural-images datasets. That said, there are images that are roughly monochromatic (namely, predominantly single-color images) but their measure is small and therefore these images can be treated as outliers.

heading: 4.2 FUTURE WORK
text: Figure 1 demonstrates that a randomly initialized convolutional layer induces an almost-isometric yet contracting embedding of natural images (mind the linear fit with slope ~0.97 in the figure), and therefore the contraction intensifies (“worsens”) with each additional layer.
In practice, the datasets are preprocessed by operations such as mean removal and normalization. These operations induce a sharper contraction. Since a sharp collapse in the deeper layers implies failure to achieve dynamical isometry, a natural goal for a practitioner would be to prevent such a collapse. Saxe et al. (2014) propose to replace the i.i.d. Gaussian initialization with orthogonal initialization that is chosen uniformly over the orthogonal group for linear FNNs. However, the latter would fail to prevent the collapse phenomenon as well (see (Pennington et al., 2017)). This can be shown by a similar calculation to that of the dual activation of ReLU with i.i.d. Gaussian initialization. In fact, the dual activations of both initializations will coincide in the limit of large input dimensions.
That said, the collapse can be prevented by moving further away from i.i.d. initialization. For example, by drawing the weights of every filter from the Gaussian distribution under the condition that the filter’s sum of weights is zero. Curiously, also including batch normalization between the layers prevents such a collapse. In both cases, the opposite phenomenon to a collapse happens, an expansion. In the deeper layers, the dataset pre-activation vectors become orthogonal to one another. Understanding this expansion and why it holds for seemingly unrelated modifications is a compelling line of research.

heading: A PROOF OF THEOREM 1
text: To prove theorem 1, we first prove the following simple result.
Lemma 3. Let u, v ∈ Rk be two (deterministic) vectors, and let G,H ∈ Rk be zero-mean jointly Gaussian vectors with the following auto- and cross-correlation matrices:
E [ GGT ] = E [ HHT ] = ν2Ik, E [ GHT ] = ρν2Ik.
Then,
Z = ( 〈u,G〉 〈v,H〉 ) = ( uTG vTH )
is a zero-mean Gaussian vector with a covariance matrix
E [ ZZT ] = ν2 ( ‖u‖2 ρ〈u, v〉 ρ〈u, v〉 ‖v‖2 ) .
Proof of lemma 3. Z is a Gaussian vector as a linear combination of two jointly Gaussian vectors. Furthermore,
E [Z] = E [( uTG vTH )] = ( uTE [G] vTE [H] ) = 0,
E [ ZZT ] = E [( uTGGTu uTGHT v vTHGTu vTHHT v )] = ( uTE [ GGT ] u uTE [ GHT ] v vTE [ HGT ] u vTE [ HHT ] v )
= ν2 (
‖u‖2 ρ〈u, v〉 ρ〈u, v〉 ‖v‖2
)
We are now ready to prove theorem 1.
Proof of theorem 1. The equation (7) is proved as follows.
E [〈σ(F ∗ x), σ(F ∗ y)〉] = ∑ i,j∈Zn E [ σ(〈F, [x]rij〉) · σ ( 〈F, [y]rij〉 )] (17a)
= ∑ i,j∈Zn σ̂ ( [x]rij , [y] r ij , ν ) , (17b)
where (17a) follows from the definition of the cyclic convolution (4) and the linearity of expectation, and (17b) follows from definition 1 using lemma 3 with F taking the role of G and H (with ρ = 1), and [x]rij and [y] r ij taking the roles of u and v, respectively.
Now, we set out to prove (8) under the assumption that σ is homogeneous and the following notation.
( Xij Yij ) ∼ N (( 0 0 ) , ( ∥∥[x]rij ∥∥2 〈[x]rij , [y]rij〉
〈[x]rij , [y]rij〉 ∥∥[y]rij ∥∥2
))
( X̄ij Ȳij ) ∼ N (( 0 0 ) , ( 1 ρij ρij 1 ))
E [〈σ(F ∗ x), σ(F ∗ y)〉] = ∑ i,j∈Zn σ̂ ( [x]rij , [y] r ij , ν )
= ∑
i,j∈Zn E [σ(νXij) · σ(νYij)] (18a)
= ν2 ∑
i,j∈Zn
∥∥[x]rij ∥∥ ∥∥[y]rij ∥∥E [ σ(Xij/ ∥∥[x]rij ∥∥) · σ(Yij/ ∥∥[y]rij ∥∥) ] (18b)
= ν2 ∑
i,j∈Zn
∥∥[x]rij ∥∥ ∥∥[y]rij ∥∥E [ σ(X̄ij) · σ(Ȳij) ] (18c)
= ν2 · ν2σ ∑
i,j∈Zn
∥∥[x]rij ∥∥ ∥∥[y]rij ∥∥ σ̂ (ρij) , (18d)
where (18a) follows from definition 1, (18b) follows from the homogeneity of σ, (18c) follows from standard random variable calculus, and (18d) follows from (6).
Finally, to obtain (9), we apply (8) for x = y and use that ρij = 1 and σ̂(1) = 1:
E [ σ(F ∗ x)2 ] = ν2 · ν2σ ∑
i,j∈Zn ‖[x]rij‖2σ̂(ρij)
= ν2 · ν2σ ∑
i,j∈Zn ‖[x]rij‖2σ̂(1)
= ν2 · ν2σ ∑
i,j∈Zn ‖[x]rij‖2 = ν2 · ν2σ · r2‖x‖2 .

heading: B PROOF OF THEOREM 2
text: To prove the concentration of measure results of this work, we will make use of the following definition.
Definition 3. The Orlicz norm of a random variable (RV)X with respect to (w.r.t.) a convex function ψ : [0,∞) → [0,∞) such that ψ(0) = 0 and limx→∞ ψ(x) = ∞ is defined by
‖X‖ψ := inf { t > 0 ∣∣∣∣ E [ ψ ( |X| t )] ≤ 1 } .
In particular, X is said to be sub-Gaussian if ‖X‖ψ2 < ∞, and sub-exponential if ‖X‖ψ1 < ∞, where ψp(x) := exp {xp} − 1 for p ≥ 1.
The following two results, whose proofs are available in (Vershynin, 2018, Ch. 2 and 5.2), will be useful for the proof of theorem 2.
Lemma 4. Let X and Y be sub-Gaussian random variables (not necessarily independent). Then,
1. Sum of independent sub-Gaussians. If X and Y are also independent, then their sum,
X + Y , is sub-Gaussian. Moreover, ‖X + Y ‖2ψ2 ≤ C ( ‖X‖2ψ2 + ‖Y ‖ 2 ψ2 ) for an absolute constant C. The same holds (with the same constant C) also for sums of multiple independent sub-Gaussian RVs.
2. Centering. X − E [X] is sub-Gaussian. Moreover, ‖X − E [X]‖ψ2 ≤ C ‖X‖ψ2 for an absolute constant C.
3. Lipschitz functions of Gaussians. If X is a centered Gaussian and f is a function with Lipschitz constant L, then ‖f(X)− E [f(X)]‖ψ2 ≤ C ‖X‖ψ2 for an absolute constant C.
4. Product of sub-Gaussians. XY is sub-exponential. Moreover, ‖XY ‖ψ1 ≤ ‖X‖ψ2 ‖Y ‖ψ2 . Theorem 6 (Bernstein’s inequality for sub-exponentials). Let X1, . . . , XN be independent zeromean sub-exponential RVs. Then,
P (∣∣∣∣∣ 1 N N∑
i=1
Xi ∣∣∣∣∣ ≥ t ) ≤ 2 exp { −min { t2 K2 , t K } · c ·N } , ∀t ≥ 0,
where K = maxi ‖Xi‖ψ1 and c > 0 is an absolute constant.
We are now ready to prove the desired concentration-of-measure result.
Proof of theorem 2. 〈Fℓ, [x]rij〉 and 〈Fℓ, [y]rij〉 are (jointly) Gaussian RVs—as linear combinations of i.i.d. Gaussian RVs—with mean zero and variances ν2 ∥∥[x]rij ∥∥2 and ν2 ∥∥[y]rij ∥∥2, respectively, for all ℓ ∈ [N ] and i, j ∈ Zn. Hence, 〈Fℓ, [x]rij〉 and 〈Fℓ, [y]rij〉 are also sub-Gaussian with ∥∥〈Fℓ, [x]rij〉 ∥∥ ψ2 ≤ C0νR, ∥∥〈Fℓ, [y]rij〉 ∥∥ ψ2 ≤ C0νR, ∀ℓ ∈ [N ], ∀i, j ∈ Zn
for some universal constant C0 > 0. Define now
Xijℓ := σ ( 〈Fℓ, [x]rij〉 ) , Yijℓ := σ ( 〈Fℓ, [y]rij〉 ) , ∀ℓ ∈ [N ], ∀i, j ∈ Zn.
Since σ is Lipschitz continuous with a Lipschitz constant L, and since the inner products 〈Fℓ, [x]rij〉 and 〈Fℓ, [y]rij〉 are centered Gaussians, by property 3 in lemma 4 it follows that Xijℓ and Yijℓ are sub-Gaussian with
‖Xijℓ − E [Xijℓ]‖ψ2 ≤ C0LνR, ‖Yijℓ − E [Yijℓ]‖ψ2 ≤ C0LνR, ∀ℓ ∈ [N ], ∀i, j ∈ Zn.(19) Due to the assumption σ(0) = 0 and the fact that σ has Lipschitz constant L, inequality |σ(x)| ≤ L|x| holds for every x ∈ R. Accordingly, we can bound the expectation of E [Xijℓ] with
|E [Xijℓ]| ≤ E [|Xijℓ|] ≤ LE [∣∣〈Fℓ, [x]rij〉 ∣∣] ≤ L √ Var [ 〈Fℓ, [x]rij〉 ] ≤ LνR , (20)
where we applied the Cauchy–Schwarz inequality. Similarly, it holds that∣∣E [Yijℓ] ∣∣ ≤ LνR . (21) Since by homogeneity of norm it also holds for any constant D ∈ R that ‖D‖ψ2 ≤ C0|D|, by triangle inequality it then follows from (19), (20) and (21) that
‖Xijℓ‖ψ2 ≤ ‖Xijℓ − E [Xijℓ]‖ψ2 + ‖E [Xijℓ]‖ψ2 ≤ 2C0LνR , ‖Yijℓ‖ψ2 ≤ 2C0LνR .
Therefore, subsequent application of properties 4 and 2 of lemma 4 to XijℓYijℓ, yields
‖XijℓYijℓ‖ψ1 ≤ 4C 2 0ν 2L2R2,
‖XijℓYijℓ − E [XijℓYijℓ]‖ψ1 ≤ 4C 2 0Cν
2L2R2, (22)
for all ℓ ∈ [N ] and all i, j ∈ Zn, where C > 0 is is the absolute constant from lemma 4. Now it follows
P   ∣∣∣∣∣∣ 1 N N∑
ℓ=1
〈σ(Fℓ ∗ x), σ(Fℓ ∗ y)〉 − n∑
i,j=1
σ̂ ( [x]rij , [y] r ij , ν ) ∣∣∣∣∣∣ ≥ ǫ  
= P   1 N ∣∣∣∣∣∣
∑
ℓ∈[N ];i,j∈Zn
{ XijℓYijℓ − E [XijℓYijℓ] } ∣∣∣∣∣∣ ≥ ǫ   (23a)
≤ P   1 N ∑
i,j∈Zn
∣∣∣∣∣∣ ∑
ℓ∈[N ]
{ XijℓYijℓ − E [XijℓYijℓ] } ∣∣∣∣∣∣ ≥ ǫ   (23b)
≤ P
 n 2
N max i,j∈Zn ∣∣∣∣∣∣ ∑
ℓ∈[N ]
{ XijℓYijℓ − E [XijℓYijℓ] } ∣∣∣∣∣∣ ≥ ǫ   (23c)
≤ ∑
i,j∈Zn P
 n 2
N ∣∣∣∣∣∣ ∑
ℓ∈[N ]
{ XijℓYijℓ − E [XijℓYijℓ] } ∣∣∣∣∣∣ ≥ ǫ   (23d)
≤ 2n2 exp { −min ( 16ǫ2
C40C 2ν4L4R4n4
, 4ǫ
C20Cν 2L2R2n2
) cN } , (23e)
where (23a) follows from theorem 1 and (19), (23b) follows from the triangle inequality, (23d) follows from the union bound, and (23e) follows from (22) and theorem 6. Finally, noting that (11) holds for N > max ( C40C 2ν4L4R4n4
16cǫ2 , C20Cν 2L2R2n2 4cǫ
) log 2n 2
δ concludes the
proof.

heading: C PROOF OF COROLLARY 1
text: Let us start by inspecting (12) to observe that, by homogeneity of σ, neither the value of ρ̄out nor the distribution of ρout depend on ν or the norms of x and y. Therefore, let us assume without loss of generality that x and y are unit vectors, as well as that ν = 1
νσr . Furthermore, note that homogeneity
of σ implies σ(0) = 0, so theorem 2 can be applied with activation function σ.
Let A := 1 N ∑N ℓ=1〈σ(Fℓ ∗x), σ(Fℓ ∗y)〉, B := 1N ∑N ℓ=1 ‖σ(Fℓ ∗x)‖2, C := 1N ∑N ℓ=1 ‖σ(Fℓ ∗y)‖2 and A′ := 1 r2 ∑ i,j∈Zn ‖[x]rij‖ · ‖[y]rij‖σ̂(ρij). Comparing against (12), we see that ρout = A√ BC and that ρ̄out = A ′.
We now apply theorem 2 three times, for pairs of vectors (x, y), (x, x) and (y, y), respectively, with parameters of ǫ/5 and δ/3. Using equations (7)–(9) from theorem 1, we check that indeed each of the three following relations holds for N > max(K,K2) log 6n 2
δ , except with probability δ/3:
|A−A′| ≤ ǫ 5 , |B − 1| ≤ ǫ 5 , |C − 1| ≤ ǫ 5 . (24)
By union bound, all three inequalities in (24) hold simultaneously except with probability δ. Finally, by elementary inequalities we establish that if (24) holds for someA,A′, B,C ∈ R such that |A| ≤ 1 and 0 < ǫ ≤ 1/10, then it also holds that
∣∣ρout − ρ̄out ∣∣ = ∣∣∣∣ A√ BC −A′ ∣∣∣∣ ≤ ǫ .
Since this occurs except with probability δ, the proof is concluded.

heading: D PROOF OF LEMMATA 1 AND 2
text: Proof of lemma 1. Lemma 1 may be viewed as a special case of theorem 1 with an identity activation function σ. Therefore,
E [〈F ∗ x, F ∗ y〉] (a)= ∑ i,j∈Zn σ̂ ( [x]rij , [y] r ij , ν ) (b) = ∑ i,j∈Zn ν2〈[x]rij , [y]rij〉 (c) = 〈x, y〉,
where (a) follows from theorem 1, (b) follows from definition 1, and (c) holds since ν2 = 1/r2.
Proof of lemma 2. Again, lemma 2 follows from theorem 2 for σ(x) ≡ x (and hence L = 1) and from lemma 1.

heading: E PROOF OF THEOREM 3
text: We start with the lower bound. Define ρij := 〈[x]rij ,[y]rij〉
‖[x]rij‖‖[y]rij‖ for all i, j ∈ Zn. Then, for all i, j ∈ Zn,
〈[x]rij , [y]rij〉 = ∥∥[x]rij ∥∥ ∥∥[y]rij ∥∥ ρij (25a)
≤ ∥∥[x]rij ∥∥ ∥∥[y]rij ∥∥
√ 1− ρ2ij + (π − cos−1(ρij))ρij
π (25b)
= r2E [ σ ( 〈F, [x]rij〉 ) σ ( 〈F, [y]rij〉 )] , (25c)
where (25a) holds by the definition of ρij , (25b) holds since
a ≤ √ 1− a2 + ( π − cos−1(a) ) a
π ∀|a| ≤ 1,
and (25c) follows from (Daniely et al., 2016, Table 1 and Section C of supplement). Thus, 〈x, y〉 = 1/r2 ∑
i,j∈Zn 〈[x]rij , [y]rij〉 ≤
∑ i,j∈Zn E [ σ ( 〈F, [x]rij〉 ) σ ( 〈F, [y]rij〉 )] = E [σ(F ∗ x)σ(F ∗ y)] ,
(26)
where the inequality follows from (25), and the last step is due to (17). Now, since the ReLU activation is non-negative, 0 ≤ E [σ(F ∗ x)σ(F ∗ y)], which completes the proof of the left inequality in (13).
For the upper bound, we use the following convexity argument. First, by homogeneity of ReLU, we can assume without loss of generality that x and y have unit norm. Therefore, it remains to show E [σ(F ∗ x)σ(F ∗ y)] ≤ 1+ρ2 for x, y such that ‖x‖ = ‖y‖ = 1 and 〈x, y〉 = ρ.
Recall that ρij = 〈[x]rij ,[y]rij〉
‖[x]r ij ‖‖[y]r ij ‖ . We expand the definitions in the same way as in (26) and (25c) E [σ(F ∗ x)σ(F ∗ y)] = ∑
i,j∈Zn E [ σ ( 〈F, [x]rij〉 ) σ ( 〈F, [y]rij〉 )]
= ∑
i,j∈Zn
‖[x]rij‖‖[y]rij‖ r2 R̂(ρij) . (27)
It is easily checked that R̂(1) = 1, R̂(−1) = 0 and that R̂(x) is convex for −1 ≤ x ≤ 1. Accordingly, using the decomposition ρ = 1+ρ2 ·1+ 1−ρ 2 ·(−1), we have by Jensen’s inequality for every i, j ∈ Zn
R̂(ρij) ≤ 1 + ρij
2 .
Substituting into (27),
E [σ(F ∗ x)σ(F ∗ y)] ≤ ∑
i,j∈Zn
‖[x]rij‖‖[y]rij‖ r2 · 1 + ρij 2
= 1
2r2
∑
i,j∈Zn ‖[x]rij‖‖[y]rij‖+
1
2r2
∑
i,j∈Zn 〈[x]rij , [y]rij〉
≤ 1 2r2
√√√√√   ∑
i,j∈Zn ‖[x]rij‖2
    ∑
i,j∈Zn ‖[y]rij‖2
 + 1
2 · 〈x, y〉 (28)
= 1 + ρ
2 ,
where in (28) we applied the Cauchy–Schwarz inequality and used the initial assumption ‖x‖ = ‖y‖ = 1.

heading: F PROOF OF THEOREM 4
text: The proof follows from the following steps.
E [〈σ(F ∗X), σ(F ∗ Y )〉] = E  E   ∑
i,j∈Zn σ(〈F, [X]rij〉)σ(〈F, [Y ]rij〉) ∣∣∣∣∣∣ F     (29a)
= E [ n2E [σ (XF )σ (YF )] ] (29b)
= 1
2
√ 1− ρ2 + ( π − cos−1(ρ) ) ρ
π E
[ ‖F‖2 ] (29c)
=
√ 1− ρ2 + ( π − cos−1(ρ) ) ρ
π (29d)
where (29a) follows from the law of total expectation; (29b) follows from (14), from the independence of F in (X,Y ), and from lemma 3 with F taking the roles of u and v, and [X]rij and [Y ] r ij taking the roles of G and H , resulting in XF and YF which are zero-mean jointly Gaussian with variances ‖F‖2 /n2 and a Pearson correlation coefficient ρ; (29c) follows from the homogeneity of the ReLU activation function and from (Cho and Saul, 2009, eq. (6)), (Daniely et al., 2016, Section 8); (29d) holds by the definition of F .

heading: G PROOF OF THEOREM 5
text: In this section, we will use the following additional notations. [A]r̄ij will denote the submatrix of A formed from rows i − r to i + r and columns j − r to j + r, and 1k×k will denote a k × k matrix with all entries equal 1.
The main effort in the proof is establishing (16a). We apply theorem 1, so we have E [〈σ(F ∗A), σ(F ∗B)〉] = ∑i,j σ̂([A]r̄ij , [B]r̄ij , 2/(2r + 1)). And specifically, for the ReLU activation, it holds that
σ̂([A]r̄ij , [B] r̄ ij , 2/(2r + 1)) =
∥∥[A]r̄ij ∥∥ ∥∥[B]r̄ij ∥∥ R̂(ρij) (2r + 1)2
(30)
where ρij = 〈[A]r̄ij ,[B]r̄ij〉
‖[A]r̄ij‖‖[B]r̄ij‖ .
A natural way to show that the convolutional layer induces isometry in expectation would be to show
σ̂([A]r̄ij , [B] r̄ ij , 2/(2r + 1)) = Aij ·Bij
for all pairs (i, j). Unfortunately, this does not hold for all pairs. However, we will show that the only pairs for which it does not hold belong to the r-boundary ∂r(A,B). There are two cases to consider Aij ·Bij = 0 and Aij ·Bij = 1 since A and B are binary. Let σ̂ij = σ̂ ( [A]r̄ij , [B] r̄ ij), 2/(2r + 1) ) . Let E0 = {(i, j) ∈ Zn : Aij · Bij = 0 ∧ σ̂ij 6= 0} and E1 = {(i, j) ∈ Zn : Aij · Bij = 1 ∧ σ̂ij 6= 1}. Since clearly 0 ≤ σ̂ij ≤ 1 and 〈A,B〉 = |{(i, j) : Aij ·Bij = 1}|, we have
〈A,B〉 − |E1| ≤ EF [σ(F ∗A), σ(F ∗B)] ≤ 〈A,B〉+ |E0| . In particular, if we show E0, E1 ⊆ ∂r(A,B), then (16a) will be established. This is what we show in the rest of the proof.
For readability, we repeat here the two conditions for a pair (i, j) to be included in the boundary, see definition 2. Namely, (i, j) belongs to ∂r(A,B) if and only if both conditions below hold:
1. ∃a1, b1, c1, d1 ∈ {−r, . . . , r} : (i+ a1, j + b1) ∈ A ∧ (i+ c1, j + d1) ∈ B. 2. ∃a2, b2, c2, d2 ∈ {−r, . . . , r} : (i+ a2, j + b2) /∈ A ∨ (i+ c2, j + d2) /∈ B.
Let (i, j) be such that Aij ·Bij = 0. By equation (30), σ̂ij = 0 if and only if [A]r̄ij = 0 or [B]r̄ij = 0. So, when Aij ·Bij = 0, for σ̂ij 6= 0 to hold it is necessary that there are a1, b1, c1, d1 ∈ {−r, . . . , r} such that Ai+a1,j+b1 = 1 and Ai+c1,j+d1 = 1 which corresponds to the first item in definition 2. The second item holds with a2 = b2 = c2 = d2 = 0 since Aij · Bij = 0 so either Aij = 0 or Bij = 0. This shows that pairs of indices for which Aij · Bij = 0 and σ̂ij 6= 0 are contained in ∂r(A,B), in other words that E0 ⊆ ∂r(A,B). Now take (i, j) such that Aij · Bij = 1. By equation (30), σ̂ij = 1 if and only if [A]r̄ij = 1(2r+1)×(2r+1) and [B] r̄ ij = 1(2r+1)×(2r+1). So, when Aij · Bij = 1 and σ̂ij 6= 1, then there are a2, b2, c2, d2 ∈ {−r, . . . , r} such that Ai+a2,j+b2 = 0 or Bi+c2,j+d2 = 0 which corresponds to the second item in definition 2. The first item holds with a1 = b1 = c1 = d1 = 0 since Aij ·Bij = 1 so both Aij = 1 and Bij = 1. This shows that pairs of indices for which Aij ·Bij = 1 and σ̂ij 6= 1 are contained in ∂r(A,B), or equivalently that E1 ⊆ ∂r(A,B). This concludes the proof of (16a). As for (16b), it follows easily by substituting in the formula ‖A − B‖2 = ‖A‖2 + ‖B‖2 − 2〈A,B〉. We then use the fact E [∥∥R(F ∗A)2 ∥∥] = ‖A‖2, which follows from (9), recalling that ν2 = 2/(2r + 1)2 and ν2R = 1/2.

Review summaries:
This paper studies the random initialized CNNs and analyzes the geometry preservation. For linear CNNs, the authors show the JL lemma type results hold. For  CNN+ ReLU, the output contracts and the level of contraction depend on the inputs. In numerical experiments, the authors verify the geometry of natural images is preserved, while for random gaussian correlated inputs, the contraction behavior appears. 

 The authors consider angle propagation in randomly-initialized convolutional neural network layers -- given two input images that have cosine angle $\rho$, what is the cosine angle of their feature embeddings when propagated through the random layer? They show that the behavior is very different from the standard feedforward case that has been discussed at length following the work of Daniely et al. (2016): for filters of small spatial support and e.g. ReLU activations, the output cosine angle can be as small as the ReLU of the input cosine angle, or as large as a linear function of the input cosine angle, depending on the patch structure of the input image. This has implications for understanding signal propagation and issues like dynamical isometry in convolutional networks. The authors give some measure concentration results, in the spirit of Daniely et al.'s results for feedforward networks, that specify the behavior in the convolutional case, and present examples of different types of images (unstructured/gaussian; cartoons; CIFAR-10 data) where different angle propagation behaviors are observed. 

The paper shows (as clearly described in the introduction) two things: random filters have the distance preservation property. For random convolution + ReLU activation it is contracted (which is also expected, since ReLU throws away half of the entries). However, for images the authors try to explain why CNN+ReLU is isometric by considering images as objects with large monochromatic images.   The main motivation for such research in practice is initialization. A deep fully-connected network with ReLU may lead to collapse, whereas for CNNs it does not. The paper argues that the randomized theory presented here is a justification for such fact for images.