Title: UNDERSTANDING AND TRAINING DEEP DIAGONAL CIRCULANT NEURAL NETWORKS

Abstract: In this paper, we study deep diagonal circulant neural networks, that is deep neural networks in which weight matrices are the product of diagonal and circulant ones. Besides making a theoretical analysis of their expressivity, we introduced principled techniques for training these models: we devise an initialization scheme and proposed a smart use of non-linearity functions in order to train deep diagonal circulant networks. Furthermore, we show that these networks outperform recently introduced deep networks with other types of structured layers. We conduct a thorough experimental study to compare the performance of deep diagonal circulant networks with state of the art models based on structured matrices and with dense models. We show that our models achieve better accuracy than other structured approaches while required 2x fewer weights as the next best approach. Finally we train deep diagonal circulant networks to build a compact and accurate models on a real world video classification dataset with over 3.8 million training examples.

1. INTRODUCTION:

The deep learning revolution has yielded models of increasingly large size. In recent years, designing compact and accurate neural networks with a small number of trainable parameters has been an active research topic, motivated by practical applications in embedded systems (to reduce memory footprint (Sainath & Parada, 2015) ), federated and distributed learning (to reduce communication (Konečný et al., 2016) ), derivative-free optimization in reinforcement learning (to simplify the computation of the approximated gradient (Choromanski et al., 2018) ). Besides a number of practical applications, it is also an important research question whether or not models really need to be this big or if smaller results can achieve similar accuracy (Ba & Caruana, 2014) .

Structured matrices are at the very core of most of the work on compact networks. In these models, dense weight matrices are replaced by matrices with a prescribed structure (e.g. low rank matrices, Toeplitz matrices, circulant matrices, LDR, etc.). Despite substantial efforts (e.g. Cheng et al. (2015) ; Moczulski et al. (2015) ), the performance of compact models is still far from achieving an acceptable accuracy motivating their use in real-world scenarios. This raises several questions about the effectiveness of such models and about our ability to train them. In particular two main questions call for investigation: Q1 How to efficiently train deep neural networks with a large number of structured layers? Q2 What is the expressive power of structured layers compared to dense layers?

In this paper, we provide principled answers to these questions for the particular case of deep neural networks based on diagonal and circulant matrices (a.k.a. Diagonal-circulant networks or DCNNs).

The idea of using diagonal and circulant matrices together comes from a series of results in linear algebra by Müller-Quade et al. (1998) and Huhtanen & Perämäki (2015) . The most recent result from Huhtanen & Perämäki demonstrates that any matrix A in C n⇥n can be decomposed into the product of 2n 1 alternating diagonal and circulant matrices. The diagonal-circulant decomposition inspired Moczulski et al. (2015) to design the AFDF structured layer, which is the building block of DCNNs. However, Moczulski et al. (2015) were not able to train deep neural networks based on AFDF.

To answer Q1, we first describe a theoretically sound initialization procedure for DCNN which allows the signal to propagate through the network without vanishing or exploding. Furthermore, we provide a number of empirical insights to explain the behaviour of DCNNs, and show the impact of the number of the non-linearities in the network on the convergence rate and the accuracy of the network. By combining all these insights, we are able (for the first time) to train large and deep DCNNs. We demonstrate the good performance of DCNNs on a large scale application (the YouTube-8M video classification problem) and obtain very competitive accuracy.

To answer Q2, we propose an analysis of the expressivity of DCNNs by extending the results by Huhtanen & Perämäki (2015) . We introduce a new bound on the number of diagonal-circulant required to approximate a matrix that depends on its rank. Building on this result, we demonstrate that a DCNN with bounded width and small depth can approximate any dense networks with ReLU activations.

Outline of the paper: We present in Section 2 the related work on structured neural networks and several compression techniques. Section 3 introduces circulant matrices, our new result extending the one from Huhtanen & Perämäki (2015) . Section 4 proposes an theoretical analysis on the expressivity on DCNNs. Section 5 describes two efficient techniques for training deep diagonal circulant neural networks. Finally, Section 6 presents extensive experiments to compare the performance of deep diagonal circulant neural networks in different settings w.r.t. other state of the art approaches. Section 7 provides a discussion and concluding remarks.

2. RELATED WORK:

Structured matrices exhibit a number of good properties which have been exploited by deep learning practitioners, mainly to compress large neural networks architectures into smaller ones. For example Hinrichs & Vybíral (2011) have demonstrated that a single circulant matrix can be used to approximate the Johson-Lindenstrauss transform, often used in machine learning to perform dimensionality reduction. Building upon this result, Cheng et al. (2015) proposed to replace the weight matrix of a fully connected layer by a circulant matrix effectively replacing the complex transform modeled by the fully connected layer by a simple dimensionality reduction. Despite the reduction of expressivity, the resulting network demonstrated good accuracy using only a fraction of its original size (90% reduction).

Comparison with ACDC. Moczulski et al. (2015) have introduced two Structured Efficient Linear Layers (SELL) called AFDF and ACDC. The AFDF structured layer benefits from the theoretical results introduced by Huhtanen & Perämäki and can be seen the building block of DCNNs. However, Moczulski et al. (2015) only experiment using ACDC, a different type of layer that does not involve circulant matrices. As far as we can tell, the theoretical guarantees available for the AFDF layer do not apply on the ACDC layer since the cosine transform does not diagonalize circulant matrices (Sanchez et al., 1995) . Another possible limit of the ACDC paper is that they only train large neural networks involving ACDC layers combined with many other expressive layers. Although the resulting network demonstrates good accuracy, it is difficult the characterize the true contribution of the ACDC layers in this setting.

Comparison with Low displacement rank structures. More recently, Thomas et al. (2018) have generalized these works by proposing neural networks with low-displacement rank matrices (LDR), that are structured matrices encompassing a large family of structured matrices, including Toeplitzlike, Vandermonde-like, Cauchy-like and more notably DCNNs. To obtain this result, LDR represents a structured matrix using two displacement operators and a low-rank residual. Despite being elegant and general, we found that the LDR framework suffers from several limits which are inherent to its generality, and makes it difficult to use in the context of large and deep neural networks. First, the training procedure for learning LDR matrices is highly involved and implies many complex mathematical objects such as Krylov matrices. Then, as acknowledged by the authors, the number of parameters required to represent a given structured matrix (e.g. a Toeplitz matrix) in practice is unnecessarily high (higher than required in theory).

Other compression techniques.:

Besides structured matrices, a variety of techniques have been proposed to build more compact deep learning models. These include model distillation (Hinton et al., 2015) , Tensor Train (Novikov et al., 2015) , Low-rank decomposition (Denil et al., 2013) , to mention a few. However, Circulant networks show good performances in several contexts (the interested reader can refer to the results reported by Moczulski et al. (2015) and Thomas et al. (2018) ).

3. A PRIMER ON CIRCULANT MATRICES AND A NEW RESULT:

An n-by-n circulant matrix C is a matrix where each row is a cyclic right shift of the previous one as illustrated below.

C = circ(c) = 2 6 6 6 6 4 c0 cn 1 cn 2 . . . c1 c1 c0 cn 1 c2 c2 c1 c0 c3 . . . . . . . . . cn 1 cn 2 cn 3 c0 3 7 7 7 7 5

Circulant matrices exhibit several interesting properties from the perspective of numerical computations. Most importantly, any n-by-n circulant matrix C can be represented using only n coefficients instead of the n 2 coefficients required to represent classical unstructured matrices. In addition, the matrix-vector product is simplified from O(n 2 ) to O(n log(n)) using the convolution theorem.

As we will show in this paper, circulant matrices also have a strong expressive power. So far, we know that a single circulant matrix can be used to represent a variety of important linear transforms such as random projections (Hinrichs & Vybíral, 2011) . When they are combined with diagonal matrices, they can also be used as building blocks to represent any linear transform (Schmid et al., 2000; Huhtanen & Perämäki, 2015) with an arbitrary precision. Huhtanen & Perämäki were able to bound the number of factors that is required to approximate any matrix A with arbitrary precision.

Relation between diagonal circulant matrices and low rank matrices We recall this result in Theorem 1 as it is the starting point of our theoretical analysis (note that in the rest of the paper, k•k denotes the `2 norm when applied to vectors, and the operator norm when applied to matrices).

Theorem 1. (Reformulation Huhtanen & Perämäki (2015) ) For every matrix A 2 C n⇥n , for any ✏ > 0 , there exists a sequence of matrices B 1 . . . B 2n 1 where B i is a circulant matrix if i is odd, and a diagonal matrix otherwise, such that kB 1 B 2 . . . B 2n 1 Ak < ✏.

Unfortunately, this theorem is of little use to understand the expressive power of diagonal-circulant matrices when they are used in deep neural networks. This is because: 1) the bound only depends on the dimension of the matrix A, not on the matrix itself, 2) the theorem does not provide any insights regarding the expressive power of m diagonal-circulant factors when m is much lower than 2n 1 as it is the case in most practical scenarios we consider in this paper.

In the following theorem, we enhance the result by Huhtanen & Perämäki by expressing the number of factors required to approximate A, as a function of the rank of A. This is useful when one deals with low-rank matrices, which is common in machine learning problems.

Theorem 2. (Rank-based circulant decomposition) Let A 2 C n⇥n be a matrix of rank at most k.

Assume that n can be divided by k. For any ✏ > 0, there exists a sequence of 4k + 1 matrices B 1 , . . . , B 4k+1 , where B i is a circulant matrix if i is odd, and a diagonal matrix otherwise, such that kB 1 B 2 . . . B 4k+1 Ak < ✏

A direct consequence of Theorem 2, is that if the number of diagonal-circulant factors is set to a value K, we can represent all linear transform A whose rank is K 1 4 . Compared to Huhtanen & Perämäki (2015) , this result shows that structured matrices with fewer than 2n diagonal-circulant matrices (as it is the case in practice) can still represent a large class of matrices. As we will show in the following section, this result will be useful to analyze the expressivity of neural networks based on diagonal and circulant matrices.

First, we introduce some necessary definitions regarding neural networks and we provide a theoretical analysis of their approximation capabilities.

Definition 1 (Deep ReLU network). Given L weight matrices W = (W 1 , . . . , W L ) with W i 2 C n⇥n and L bias vectors b = (b 1 , . . . , b L ) with b i 2 C n , a deep ReLU network is a function f W L ,b L : C n ! C n such that f W,b (x) = (f W L ,b L . . . f W1,b1 )(x) where f Wi,bi (x) = (W i x + b i ) and (.)

is a ReLU non-linearity1 In the rest of this paper, we call L and n respectively the depth and the width of the network. Moreover, we call total rank k, the sum of the ranks of the matrices W 1 . . . W L . i.e. k = P L i=1 rank(W i ).

We also need to introduce DCNNs, similarly to Moczulski et al. (2015) .

Definition 2 (Diagonal Circulant Neural Networks). Given L diagonal matrices D = (D 1 , . . . , D L ) with D i 2 C n⇥n , L circulant matrices C = (C 1 , . . . , C L ) with C i 2 C n⇥n and L bias vectors b = (b 1 , . . . , b L ) with b i 2 C n , a Diagonal Circulant Neural Networks (DCNN) is a function f W L ,b L : C n ! C n such that f D,C,b (x) = (f D L ,C L ,b L . . . f D1,C1,b1 )(x) where f Di,Ci,bi (x) = i (D i C i x + b i )

and where i (.) is a ReLU non-linearity or the identity function.

We can now show that bounded-width DCNNs can approximate any Deep ReLU Network, and as a corollary, that they are universal approximators.

Lemma 1. Let N be a deep ReLU network of width n and depth L, and let X ⇢ C n be a bounded set. For any ✏ > 0, there exists a DCNN N 0 of width n and of depth (2n 1)L such that kN (x)

N 0 (x)k < ✏ for all x 2 X .

The proof is in the supplemental material. We can now state the universal approximation corollary:

Corollary 1. Bounded width DCNNs are universal approximators in the following sense: for any continuous function f :

[0, 1] n ! R + of bounded supremum norm, for any ✏ > 0, there exists a DCNN N ✏ of width n + 3 such that 8x 2 [0, 1] n+3 , |f (x 1 . . . x n ) (N ✏ (x)) 1 | < ✏, where (•) i represents the i th component of a vector.

This is a first result, however (2n + 5)L is not a small depth (in our experiments, n can be over 300 000), and a number of work provided empirical evidences that DCNN with small depth can offer good performances (e.g. Araujo et al. (2018) ; Cheng et al. (2015) ). To improve our result, we introduce our main theorem which studies the approximation properties of these small depth networks.

Theorem 3. (Rank-based expressive power of DCNNs) Let N be a deep ReLU network of width n, depth L and a total rank k and assume n is a power of 2. Let X ⇢ C n be a bounded set. Then, for any ✏ > 0, there exists a DCNN with ReLU activation N 0 of width n such that kN (x) N 0 (x)k < ✏ for all x 2 X and the depth of N 0 is bounded by 9k.

Remark that in the theorem, we require that n is a power of 2. We conjecture that the result still holds even without this condition.

This result refines Lemma 1, and answer our second question: a DCNN of bounded width and small depth can approximate a Deep ReLU network of low total rank. Note that the converse is not true: because n-by-n circulant matrix can be of rank n, approximating a DCNN of depth 1 can require a deep ReLU network of total rank equals to n.

Expressivity of DCNNs:

For the sake of clarity, we highlight the significance of these results with the two following properties.

Properties. Given an arbitrary fixed integer n, let R k be the set of all functions f : R n ! R n representable by a deep ReLU network of total rank at most k and let C l the set of all functions f : R n ! R n representable by deep diagonal-circulant networks of depth at most l, then:

8k, 9l R k ( C l (1) 8l, @k C l ✓ R k (2)

We illustrate the meaning of this properties using Figure 1 . As we can see, the set R k of all the functions representable by a deep ReLU network of total rank k is strictly included in the set C 9k of all DCNN of depth 9k (as by Theorem 3).

C 1,n . . . C 9,n . . . C 18,n R 1,n R 2,n

Figure 1: Illustration of Properties ( 1) and ( 2).

These properties are interesting for many reasons. First, Property (2) shows that diagonal-circulant networks are strictly more expressive than networks with low total rank. Second and most importantly, in standard deep neural networks, it is known that the most of the singular values are close to zero (see e.g. Sedghi et al. (2018) ; Arora et al. (2019) ). Property (1) shows that these networks can efficiently be approximated by diagonal-circulant networks. Finally, several publications have shown that neural networks can be trained explicitly to have low-rank weight matrices (Li & Shi, 2018; Goyal et al., 2019) . This opens the possibility of learning compact and accurate diagonal-circulant networks. Training DCNNs has revealed to be a challenging problem. We devise two techniques to facilitate the training of deep DCNNs. First, we propose an initialization procedure which guarantee the signal is propagated across the network without vanishing nor exploding. Secondly, we study the behavior of DCNNs with different non-linearity functions and determine the best parameters for different settings.

5. HOW TO TRAIN VERY DEEP DCNNS:



Initialization scheme:

The following initialization procedure which is a variant of Xavier initialization. First, for each circulant matrix

C = circ(c 1 . . . c n ), each c i is randomly drawn from N 0, 2 , with = q 2 n . Next, for each diagonal matrix D = diag(d 1 . . . d n )

, each d i is drawn randomly and uniformly from { 1, 1} for all i. Finally, all biases in the network are randomly drawn from N 0, 02 , for some small value of 0 . The following proposition states that the covariance matrix at the output of any layer in a DCNN, independent of the depth, is constant. Proposition 4. Let N be a DCNN of depth L initialized according to our procedure, with 0 = 0. Assume that all layers 1 to L 1 have ReLU activation functions, and that the last layer has the identity activation function. Then, for any x 2 R n , the covariance matrix of N (x) is 2.Id n kxk 2 2 . Moreover, note that this covariance does not depend on the depth of the network.

Non-linearity function We empirically found that reducing the number of non-linearities in the networks simplifies the training of deep neural networks. To support this claim, we conduct a series of experiments on various DCNNs with a varying number of ReLU activations (to reduce the number of non-linearities, we replace some ReLU activations with the identity function). In a second experiment, we replace the ReLU activations with Leaky-ReLU activations and vary the slope of the Leaky ReLU (a higher slope means an activation function that is closer to a linear function). The results of this experiment are presented in Figure 2 (a) and 2(b). In 2(a), "ReLU(DC)" means that we interleave on ReLU activation functions between every diagonal-circulant matrix, whereas ReLU(DCDC) means we interleave a ReLU activation every other block etc. In both Figure 2 (a) and Figure 2 (b), we observe that reducing the non-linearity of the networks can be used to train deeper networks. This is an interesting result, since we can use this technique to adjust the number of parameters in the network, without facing training difficulties. We obtain a maximum accuracy of 0.56 with one ReLU every three layers and leaky-ReLUs with a slope of 0.5. We hence rely on this setting in the experimental section.

6. EMPIRICAL EVALUATION:

This experimental section aims at answering the following questions: Comparison with ACDC Moczulski et al. (2015) . In Section 2, we have discussed the differences between the ACDC framework and our approach from a theoretical perspective. In this section, we conduct experiments to compare the performance of DCNNs with neural networks based on ACDC layers. We first reproduce the experimental setting from Moczulski et al. (2015) , and compare both approaches using only linear networks (i.e. networks without any ReLU activations). The results are presented in Figure 3 (a). On this simple setting, both architectures demonstrate good performance, however, DCNNs offer better convergence rate. In Figure 3 (b), we compare neural networks with ReLU activations on CIFAR-10. The synthetic dataset has been created in order to reproduce the experiment on the regression linear problem proposed by Moczulski et al. (2015) . We draw X, Y and W from a uniform distribution between [-1, +1] and ✏ from a normal distribution with mean 0 and variance 0.01. The relationship between X and Y is define by Y = XW + ✏.

We found that networks which are based only on ACDC layers are difficult to train and offer poor accuracy on CIFAR. (We have tried different initialization schemes including the one from the original paper, and the one we propose in this paper.) Moczulski et al. (2015) manage to train a large VGG network however these networks are generally highly redundant, the contribution of the structured layer is difficult to quantify. We also observe that adding a single dense layer improves the convergence rate of ACDC in the linear case networks, which explain the good results of Moczulski et al. (2015) . However, it is difficult to characterize the true contribution of the ACDC layers when the network involved a large number of other expressive layers.

In contrast, deep DCNNs can be trained and offer good performance without additional dense layers (these results are in line with our experiments on the YouTube-8M dataset). We can conclude that DCNNs are able to model complex relations at a low cost. Comparison with Dense networks, Toeplitz networks and Low Rank networks. We now compare DCNNs with other state-of-the-art structured networks by measuring the accuracy on a flattened version of the CIFAR-10 dataset. Our baseline is a dense feed-forward network with a fixed number of weights (9 million weights). We compare with DCNNs and with DTNNs (see below), Toeplitz networks, and Low-Rank networks Yu et al. (2017) . We first consider Toeplitz networks which are stacked Toeplitz matrices interleaved with ReLU activations since Toeplitz matrices are closely related to circulant matrices. Since Toeplitz networks have a different structure (they do not include diagonal matrices), we also experiment using DTNNs, a variant of DCNNs where all the circulant matrices have been replaced by Toeplitz matrices. Finally we conduct experiments using networks based on low-rank matrices as they are also closely related to our work. For each approach, we report the accuracy of several networks with a varying depth ranging from 1 to 40 (DCNNs, Toeplitz networks) and from 1 to 30 (from DTNNs). For low-rank networks, we used a fixed depth network and increased the rank of each matrix from 7 to 40. We also tried to increase the depth of low rank matrices, but we found that deep low-rank networks are difficult to train so we do not report the results here. We compare all the networks based on the number of weights from 21K (0.2% of the dense network) to 370K weights (4% of the dense network) and we report the results in Figure 4 (a). First we can see that the size of the networks correlates positively with their accuracy which demonstrate successful training in all cases. We can also see that the DCNNs achieves the maximum accuracy of 56% with 20 layers (⇠ 200K weights) which as as good as the dense networks with only 2% of the number of weights. Other approaches also offer good performance but they are not able to reach the accuracy of a dense network.

Comparison with LDR networks Thomas et al. (2018) . We now compare DCNNs with the LDR framework using the network configuration experimented in the original paper: a single LDR structured layer followed by a dense layer. In the LDR framework, we can change the size of a network by adjusting the rank of the residual matrix, effectively capturing matrices with a structure that is close to a known structure but not exactly (e.g. in the LDR framework, Toeplitz matrices can be encoded with a residual matrix with rank=2, so a matrix that can be encoded with a residual of rank=3 can be seen as Toeplitz-like.). The results are presented in Table 1 and demonstrate that DCNNs outperforms all LDR networks both in terms in size and accuracy.

Exploiting image features. Dense layers and DCNNs are not designed to capture task-specific features such as the translation invariance inherently useful in image classification. We can further improve the accuracy of such general purpose architectures on image classification without dramatically increasing the number of trained parameters by stacking them on top of fixed (i.e. non-trained) transforms such as the scattering transform (Mallat, 2010) . In this section we compare the accuracy of various structured networks, enhanced with the scattering transform, on an image classification task, and run comparative experiments on CIFAR-10.

Our test architecture consists of 2 depth scattering on the RGB images followed by a batch norm and LDR or DC layer. To vary the number of parameters of Scattering+LDR architecture, we increase the rank of the matrix (stacking several LDR matrices quickly exhausted the memory). The Figure 4 (b) and 2 shows the accuracy of these architectures given the number of trainable parameters.

First, we can see that the DCNN architecture very much benefits from the scattering transform and is able to reach a competitive accuracy over 78%. We can also see that scattering followed by a DC layer systematically outperforms scattering + LDR or scattering + Toeplitz-like with less parameters.

6.2 COMPARISON WITH OTHER COMPRESSION BASED APPROACHES (Q6.2) The YouTube-8M includes two datasets describing 8 million labeled videos. Both datasets contain audio and video features for each video. In the first dataset (aggregated) all audio and video features have been aggregated every 300 frames. The second dataset (full) contains the descriptors for all the frames. To compare the models we use the GAP metric (Global Average Precision) proposed by Abu-El-Haija et al. (2016b) . On the simpler aggregated dataset we compared off-the-shelf DCNNs with a dense baseline with 5.7M weights. On the full dataset, we designed three new compact architectures based on the state-of-the-art architecture introduced by Abu- El-Haija et al. (2016b) .

Experiments on the aggregated dataset with DCNNs: We compared DCNNs with a dense baseline with 5.7 millions weights. The goal of this experiment is to discover a good trade-off between depth and model accuracy. To compare the models we use the GAP metric (Global Average Precision) following the experimental protocol in Abu- El-Haija et al. (2016b) , to compare our experiments.

Table 4 shows the results of our experiments on the aggrgated YouTube-8M dataset in terms of number of weights, compression rate and GAP. We can see that the compression ratio offered by the circulant architectures is high. This comes at the cost of a little decrease of GAP measure. The 32 layers DCNN is 46 times smaller than the original model in terms of number of parameters while having a close performance. Table 5 shows the results in terms of number of weights, size of the model (MB) and GAP on the full dataset, replacing the DBoF block reduces the size of the network without impacting the accuracy. We obtain the best compression ratio by replacing the MoE block with DCNNs (26%) of the size of the original dataset with a GAP score of 0.805 (95% of the score obtained with the original architecture). We conclude that DCNN are both theoretically sound and of practical interest in real, large scale applications.

Embedding Dim Reduction Classification:



Video:



7. CONCLUSION:

This paper deals with the training of diagonal circulant neural networks. To the best of our knowledge, training such networks with a large number of layers had not been done before. We also endowed this kind of models with theoretical guarantees, hence enriching and refining previous theoretical work from the literature. More importantly, we showed that DCNNs outperform their competing structured alternatives, including the very recent general approach based on LDR networks. Our results suggest that stacking diagonal circulant layers with non linearities improves the convergence rate and the final accuracy of the network. Formally proving these statements constitutes the future directions of this work. As future work, we would like to generalize the good results of DCNNs to convolutions neural networks. We also believe that circulant matrices deserve a particular attention in deep learning because of their strong ties with convolutions: a circulant matrix operator is equivalent to the convolution operator with circular paddings (as shown in [5] ). This fact makes any contribution to the area of circulant matrices particularly relevant to the field of deep learning with impacts beyond the problem of designing compact models. As future work, we would like to generalize our results to deep convolutional neural networks.

SUPPLEMENTAL MATERIAL -UNDERSTANDING AND TRAINING DEEP DIAGONAL CIRCULANT NEURAL NETWORKS:



Anonymous authors:

Paper under double-blind review

1. NOTATIONS & DEFINITION:

We note R(z) and I(z) the real and imaginary parts the complex number z. We note (•) t is the t th component of a vector. Let i be the imaginary number defined by i 2 = 1. Define 1 n as the n-vector of ones. Also, we note [n] = {1, . . . , n}. The rectified linear unit on the complex domain is defined by ReLU (z) = max (0, R(z)) + i max (0, I(z)). The notation |•| refers to the complex modulus. Finally, define the cyclic shift matrix S 2 R n⇥n as follows:

S = 2 6 6 6 6 6 4 0 1 1 0 1 . . . . . . 0 1 0 3 7 7 7 7 7 5

We introduce some necessary definitions regarding neural networks.

Definition 1 (Deep ReLU network). Given L weight matrices W = (W 1 , . . . , W L ) with W i 2 C n⇥n and L bias vectors b = (b 1 , . . . , b L ) with b i 2 C n , a deep ReLU network is a function f W L ,b L : C n ! C n such that f W,b (x) = (f W L ,b L . . . f W1,b1 )(x) where f Wi,bi (x) = (W i x + b i ) and (.) is a ReLU non-linearity 1

In the rest of this paper, we call L and n respectively the depth and the width of the network. Moreover, we call total rank k, the sum of the ranks of the matrices W 1 . . . W L . i.e. k = P L i=1 rank(W i ). In the rest of this paper, we call L and n respectively the depth and the width of the network. Moreover, we call total rank k, the sum of the ranks of the matrices W 1 . . . W L . i.e. k = P L i=1 rank(W i ).

2. PROOFS OF SECTION 3:

Theorem 1. (Reformulation Huhtanen & Perämäki (2015) ) For any given matrix A 2 C n⇥n , for any ✏ > 0, there exists a sequence of matrices B 1 . . . B 2n 1 where B i is a circulant matrix if i is odd, and a diagonal matrix otherwise, such that kB 1 B 2 . . . B 2n 1 Ak < ✏. Moreover, if A can be decomposed as

A = P k i=1 D i S i 1

where S is the cyclic-shift matrix and D 1 . . . D k are diagonal matrices, then A can be written as a product B 1 B 2 . . . B 2k 1 where B i is a circulant matrix if i is odd, and a diagonal matrix otherwise. Theorem 2. (Rank-based circulant decomposition) Let A 2 C n⇥n be a matrix of rank at most k. Assume that n can be divided by k. For any ✏ > 0, there exists a sequence of 4k + 1 matrices B 1 , . . . , B 4k+1 , where B i is a circulant matrix if i is odd, and a diagonal matrix otherwise, such that kB 1 B 2 . . . B 4k+1 Ak < ✏ Proof. (Theorem 2) Let U ⌃V T be the SVD decomposition of M where U, V and ⌃ are n ⇥ n matrices. Because M is of rank k, the last n k columns of U and V are null. In the following, we will first decompose U into a product of matrices W RO, where R and O are respectively circulant and diagonal matrices, and W is a matrix which will be further decomposed into a product of diagonal and circulant matrices. Then, we will apply the same decomposition technique to V . Ultimately, we will get a product of 4k + 2 matrices alternatively diagonal and circulant.

Let R = circ(r 1 . . . r n ). Let O be a n ⇥ n diagonal matrix where O i,i = 1 if i  k and 0 otherwise. The k first columns of the product RO will be equal to that of R, and the n k last colomns of RO will be zeros. For example, if k = 2, we have:

RO = 0 B B B B B @ r 1 r n 0 • • • 0 r 2 r 1 r 3 r 2 . . . . . . . . . . . . r n r n 1 0 • • • 0 1 C C C C C A Let us define k diagonal matrices D i = diag(d i1 . . . d in ) for i 2 [k].

For now, the values of d ij are unknown, but we will show how to compute them. Let W = P k i=1 D i S i 1 . Note that the n k last columns of the product W RO will be zeros. For example, with k = 2, we have:

W = 2 6 6 6 6 6 4 d 1,1 d 2,1 d 2,2 d 1,2 d 2,3 . . . . . . d 2,n d 1,n 3 7 7 7 7 7 5 W RO = 0 B B B B B @ r 1 d 11 + r n d 21 r n d 11 + r n 1 d 21 0 • • • 0 r 2 d 12 + r 1 d 22 r 1 d 12 + r n d 22 . . . . . . . . . . . . r n d 1n + r n 1 d 2n r n 1 d 1n + r n 2 d 2n 0 • • • 0 1 C C C C C A

We want to find the values of d ij such that W RO = U . We can formulate this as linear equation system. In case k = 2, we get:

0 B B B B B B B B B B B @ r n r 1 r n 1 r n r 1 r 2 r n r 1 r 2 r 3 r 1 r 2 . . . . . . 1 C C C C C C C C C C C A ⇥ 0 B B B B B B B B B B B @ d 2,1 d 1,1 d 2,2 d 1,2 d 2,3 d 1,3 . . . . . . 1 C C C C C C C C C C C A = 0 B B B B B B B B B B @ U 1,1 U 1,2 U 2,1 U 2,2 . . . 1 C C C C C C C C C C A

The i th bloc of the bloc-diagonal matrix is a Toeplitz matrix induced by a subsequence of length k of (r 1 , . . . r n , r 1 . . . r n ). Set r j = 1 for all j 2 {k, 2k, 3k, . . . n} and set r j = 0 for all other values of j. Then it is easy to see that each bloc is a permutation of the identity matrix. Thus, all blocs are invertible. This entails that the block diagonal matrix above is also invertible. So by solving this set of linear equations, we find d 1,1 . . . d k,n such that W RO = U . We can apply the same idea to factorize V = W 0 .R.O for some matrix W 0 . Finally, we get

A = U ⌃V T = W RO⌃O T R T W 0 T

Thanks to Theorem 1, W and W 0 can both be factorized in a product of 2k 1 circulant and diagonal matrices. Note that O⌃O T is diagonal, because all three are diagonal. Overall, A can be represented with a product of 4k + 2 matrices, alternatively diagonal and circulant.

3. PROOFS OF SECTION 4:

Lemma 1. Let W L , . . . W 1 2 C n⇥n , b 2 C n and let X ⇢ C n be a bounded set. There exists L . . . 1 2 C n such that for all x 2 X we have

f W L , L . . . f W1, 1 (x) = ReLU (W L W L 1 . . . W 1 x + b). Proof. (Lemma 1) Define S = n⇣⇣ Q j k=1 W k ⌘ x ⌘ t : x 2 X , t 2 [n], j 2 [L] o . Let ⌦ = max {R(v) : v 2 S} + i max {I(v) : v 2 S}.

Intuitively, the real and imaginary parts of ⌦ are the largest any activation in the network can have. Define h j (x) = W j x + j . Let 1 = ⌦1 n .

Clearly, for all x 2 X we have h 1 (x) 0, so ReLU h 1 (x) = h 1 (x). More generally, for all j < n 1 define j+1 = 1 n ⌦ W j+1 j . It is easy to see that for all j < n we have h j . . . h 1 (x) = W j W j 1 . . . W 1 x + 1 n ⌦. This guarantees that for all j < n, h j . . . h 1 (x) = ReLU h j . . . ReLU h 1 (x). Finally, define

L = b A L L 1 . We have, ReLU h L . . . ReLU h 1 (x) = ReLU (W j . . . W 1 x + b).

Lemma 2. Let N be a deep ReLU network of width n and depth L, and let X ⇢ C n be a bounded set. For any ✏ > 0, there exists a DCNN N 0 of width n and of depth (2n 1)L such that kN (x)

N 0 (x)k < ✏ for all x 2 X . Proof. (Lemma 2) Assume N = f W L ,b L . . . f W1,b1

. By theorem 1, for any ✏ 0 > 0, any matrix W i , there exists a sequence of 2n 1 matrices

C i,n D i,n 1 C i,n 1 . . . D i,1 C i,1 such that Q n 1 j=0 D i,n j C i,n j W i < ✏ 0

, where D i,1 is the identity matrix. By lemma 1, we know that there exists

{ ij } i2[L],j2[n] such that for all i 2 [L], f DinCin, in . . . f Di1Ci1, i1 (x) = ReLU (D in C in . . . C i1 x + b i ). Now if ✏ 0 tends to zero, kf DinCin, in . . . f Di1Ci1, i1 ReLU (W i x + b i )k

will also tend to zero for any x 2 X , because the ReLU function is continuous and X is bounded. Let N 0 = f D1nC1n, 1n . . . f Di1Ci1, i1 . Again, because all functions are continuous, for all x 2 X , kN (x) N 0 (x)k tends to zero as ✏ 0 tends to zero.

Corollary 1. Bounded width DCNNs are universal approximators in the following sense: for any continuous function f : [0, 1] n ! R + of bounded supremum norm, for any ✏ > 0, there exists a DCNN N ✏ of width n + 3 such that 8x 2 [0, 1] n+3

, |f (x 1 . . . x n ) (N ✏ (x)) 1 | < ✏, where (•) i represents the i th component of a vector.

Proof. (Corollary 1) It has been shown recently in Hanin (2017) that for any continuous function f : [0, 1] n ! R + of bounded supremum norm, for any ✏ > 0, there exists a dense neural network N with an input layer of width n, an output layer of width 1, hidden layers of width n + 3 and ReLU activations such that 8x 2

[0, 1] n , |f (x) N (x)| < ✏. From N , we can easily build a deep ReLU network N 0 of width exactly n + 3, such that 8x 2 [0, 1] n+3 , |f (x 1 . . . x n ) (N 0 (x)) 1 | < ✏.

Thanks to lemma 2, this last network can be approximated arbitrarily well by a DCNN of width n + 3. Theorem 3. (Rank-based expressive power of diagonal circulant neural networks) Let N : f W L ,b L . . . f W1,b1 be a deep ReLU network of width n, depth L and a total rank k. Assume n is a power of 2. Let X ⇢ C n be a bounded set. For any ✏ > 0, there exists a DCNN N 0 of width n such that kN (x) N 0 (x)k < ✏ for all x 2 X . In addition, the depth of N 0 is bounded by 9k. Moreover, if the rank of each matrix A i divides n, then the depth of N 0 is bounded by L + 4k.

Proof. (Theorem 3) Let k 1 . . . k L be the ranks of matrices W 1 . . . W L , which are n-by-n matrices. For all i, there exists k 0 i 2 {k i . . . 2k i } such that k 0 i is a power of 2. Due to the fact that n is also a power of 2, k 0 i divides n. By theorem 2, for all i each matrix W i can be decomposed as an alternating product of diagonal-circulant matrices B i,1 . . . B i,4k 0 i +1 such that W i B i,1 ⇥ . . . ⇥ B i,4k 0 i +1 < ✏. Using the exact same technique as in lemma 2, we can build a DCNN N 0 using matrices B 1,1 . . . B L,4k 0 L +1 , such that kN (x) N 0 (x)k < ✏ for all x 2 X. The total number of layers is

P i (4k 0 i + 1)  L + 8 P i k i  L + 8.total rank  9.total rank.

Finally, what if we choose to use small depth networks to approximate deep ReLU networks where matrices are not of low rank? To answer this question, we first need to show the negative impact of replacing matrices by their low rank approximators in neural networks:

Proposition 4. Let N = f W L ,b L . . . f W1,b1 be a Deep ReLU network, where W i 2 C n⇥n , b i 2 C n for all i 2 [L].

Let Wi be the matrix obtained by an SVD approximation of rank k of matrix W i . Let i,j be the j th singular value of W i . Define Ñ = f WL ,b L . . . f W1,b1 . Then, for any x 2 C n , we have:

EQUATION

where R is an upper bound on norm of the output of any layer in N , and max,j = max i i,j .

Proof. (Proposition 4) Let x 0 2 C n and x0 = x 0 . For all i 2 [L], define

x i = ReLU (W i x i 1 + b) and xi = ReLU ⇣ Wi xi 1 + b ⌘

. By lemma 3, we have

kx i xi k  i,k+1 kx i 1 k + i,1 kx i 1 xi 1 k

Observe that for any sequence a 0 , a 1 . . . defined recurrently by a 0 = 0 and a i = ra i 1 + s, the recurrence relation can be unfold as follows:

a i = s(r i 1)

r 1 . We can apply this formula to bound our error as follows:

kx l xl k  l max,1 1 max,k max i kx i k max,1 1 Lemma 3. Let W 2 C n⇥n

with singular values 1 . . . n , and let x, x 2 C n . Let W be the matrix obtained by a SVD approximation of rank k of matrix W . Then we have:

ReLU (W x + b) ReLU ⇣ W x + b ⌘  k+1 kxk + 1 kx xk Proof. (Lemma 3) Recall that kW k 2 = sup z kW zk 2 kzk 2 = 1 = W 2

, because 1 is the greatest singular value of both W and W . Also, note that W W 2 = k+1 . Let us bound the formula without ReLUs: , where each Wi is the matrix obtained by an SVD approximation of rank k of matrix W i . With Proposition 4, we have an error bound on kN (x) Ñ (x) k. Now each matrix Wi can be replaced by a product of k diagonal-circulant matrices. By theorem 3, this product yields a DCNN of depth m = L(4k + 1), strictly equivalent to Ñ on X . The result follows.

(W x + b) ⇣ W x + b ⌘ = (W x + b) ⇣ W x + b ⌘ = W x W x W (x x)  ⇣ W W ⌘ x + W 2 kx xk  kxk k+1 + 1 kx xk

4. PROOF OF SECTION 5:

Proposition 5. Let N be a DCNN of depth L initialized according to our procedure, with 0 = 0. Assume that all layers 1 to L 1 have ReLU activation functions, and that the last layer has the identity activation function. Then, for any x 2 R n , the covariance matrix of N (x) is 2.Id n kxk 2 2 . Moreover, note that this covariance does not depend on the depth of the network.

Proof. (Proposition 5) Let N = f D L ,C L . . . f D1,C1 be a L layer DCNN. All matrices are initialized as described in the statement of the proposition. Let y = D 1 C 1 x. Lemma 4 shows that cov(y i , y i 0 ) = 0 for i 6 = i 0 and var(y i ) = 2 n kxk 2 2 . For any j  L, define z j = f Dj ,Cj . . . f D1,C1 (x). By a recursive application of lemma 4, we get that then cov(z j i , z j i 0 ) = 0 and var(z j i ) = 2 n kxk Then, for all i, the p.d.f. of y i , ȳi , z i and zi are symmetric. Also:

• Assume u 1 . . . u n is fixed. Then, we have for i 6 = i 0 : cov(y i , y i 0 ) = cov(z i , z i 0 ) = cov(ȳ i , ȳi 0 ) = cov(z i , zi 0 ) = 0 var(y i ) = var(z i ) = • Let x 1 . . . x n be random variables in R such that the p.d.f. of x i is symmetric for all i, and let u i = ReLU (x i ). We have for i 6 = i 0 : cov(y i , y i 0 ) = cov(z i , z i 0 ) = cov(ȳ i , ȳi 0 ) = cov(z i , zi 0 ) = 0 var(y i ) = var(z i ) = 1 2

X j var(x i ). 2 var(ȳ i ) = var(z i ) = 02 + 1 2 X j var(x i ). 2

Proof. (Lemma 4) By an abuse of notation, we write c 0 = c n , c 1 = c n 1 and so on. First, note that: y i = P n j=1 c j i u j d j and z i = P n j=1 c j i u j d i . Observe that each term c j i u j d j and c j i u j d i have symmetric p.d.f. because of d i and d j . Thus, y i and z i have symmetric p.d.f. Now let us compute the covariance. cov(y i , y i 0 ) = n X j,j 0 =1 cov (c j i u j d j , c j 0 i 0 u j 0 d j 0 ) = n X j,j 0 =1 E [c j i u j d j c j 0 i 0 u j 0 d j 0 ] E [c j i u j d j ] E [c j 0 i 0 u j 0 d j 0 ]

Observe that E [c j i u j d j ] = E [c j i u j ] E [d j ] = 0 because d j is independent from c j i u j . Also, observe that if j 6 = j 0 then E [d j d j 0 ] = 0 and thus E [c j i u j d j c j 0 i 0 u j 0 d j 0 ] = 

:

ANALYSIS OF DIAGONAL CIRCULANT NEURAL NETWORKS (DCNNS)Zhao et al. (2017) have shown that circulant networks with 2 layers and unbounded width are universal approximators. However, results on unbounded networks offer weak guarantees and two important questions have remained open until now: 1) Can we approximate any function with a bounded-width circulant networks? 2) What function can we approximate with a circulant network that has a bounded width and a small depth? We answer these two questions in this section.

Because our networks deal with complex numbers, we use an extension of the ReLU function to the complex domain. The most straightforward extension defined inTrabelsi et al. (2018) is as follows: ReLU(z) = ReLU (R(z)) + iReLU (I(z)), where R and I refer to the real and imaginary parts of z.

Remark: the numbers may differ from the original experiments by Thomas et al. because we use the original dataset instead of a monochrome version)

Figures and Tables:

Figure 2: Experiments on training DCNNs and other structured neural networks on CIFAR-10. Figure 2(a): impact of increasing the number of ReLU activations in a DCNN. Deep DCNNs with fewer ReLUs are easier to train. Figure 2(b): impact of increasing the slope of a Leaky-ReLU in DCNNs. Deep DCNNs with a larger slope are easier to train.

Figure 3: Comparison of DCNNs and ACDC networks on two different tasks. Figure 3(a) shows the evolution of the training loss on a regression task with synthetic data. Figure 3(b) shows the test accuracy on the CIFAR-10 dataset.

Figure 4: Figure 4(a): network size vs. accuracy compared on Dense networks, DCNNs (our approach), DTNNs (our approach), neural networks based on Toeplitz matrices and neural networks based on Low Rank-based matrices. DCNNs outperforms alternatives structured approaches. Figure 4(b) shows the accuracy of different structured architecture given the number of trainable parameters.

Figure 5: This figure shows the state-of-the-art neural network architecture, initially proposed by Abu-El-Haija et al. (2016b) and later improved by Miech et al. (2017), used in our experiment.Experiments with DCNNs Deep Bag-of-Frames Architecture: The Deep Bag-of-Frames architecture can be decomposed into three blocks of layers, as illustrated in Figure5. The first block of layers, composed of the Deep Bag-of-Frames embedding (DBoF), is meant to model an embedding of these frames in order to make a simple representation of each video. A second block of fully connected layers (FC) reduces the dimensionality of the output of the embedding and merges the resulting output with a concatenation operation. Finally, the classification block uses a combination of Mixtures-of-Experts (MoE)Jordan & Jacobs (1993); Abu-El-Haija et al. (2016a)  and Context GatingMiech et al. (2017) to calculate the final class probabilities.

easy to see that for any pair of vectors a, b 2 C n , we have kReLU (a) ReLU (b)k  ka bk. This concludes the proof. Corollary 2. Consider any deep ReLU network N = f W L ,b L . . . f W1,b1 of depth L and width n.Let max,j = max i i,j where i,j is the j th singular value of W i . Let X ⇢ C n be a bounded set. Let k be an integer dividing n. There exists a DCNN N 0 = f DmCm,b 0 m . . . f D1C1,b 0 1 of width n and of depth m = L(4k + 1), such that for any x 2 X :kN (x) N 0 (x)k < L max,1 1 R max,k max,1 1where R is an upper bound on the norm of the outputs of each layer in N . Proof. (Corollary 2) Let Ñ = f WL ,b L . . . f W1,b1

Let c 1 . . . c n , d 1 . . . d n , b 1 . . . b n be random variables in R such that c i ⇠ N (0, 2 ), b i ⇠ N (0, 02 ) and d i ⇠ { 1, 1} uniformly. Define C = circ(c 1 . . . c n ) and D = diag(d 1 . . . d n ).Define y = DCu and z = CDu for some vector u in R n. Also define ȳ = y + b and z = z + b.

LDR networks compared with DCNNs on a flattend version of CIFAR-10. DCNNs outperform all LDR configurations with fewer weights. 2

Table content: <table><tr><td>Architectures</td><td>#Params</td><td>Acc.</td></tr><tr><td>Dense DCNN (5 layers) DCNN (2 layers)</td><td>9.4M 49K 21K</td><td>0.562 0.543 0.536</td></tr><tr><td>LDR-TD (r = 2)</td><td>64K</td><td>0.511</td></tr><tr><td>LDR-TD (r = 3)</td><td>70K</td><td>0.473</td></tr><tr><td>Toeplitz-like (r = 2)</td><td>46K</td><td>0.483</td></tr><tr><td>Toeplitz-like (r = 3)</td><td>52K</td><td>0.496</td></tr></table>

Two depths scattering on CIFAR-10 followed by LDR or DC layer. Networks with DC layers outperform all LDR configurations with fewer weights.

Table content: <table><tr><td>Architectures</td><td>#Params</td><td>Acc.</td></tr><tr><td>DC (1 layers)</td><td>124K</td><td>0.757</td></tr><tr><td>DC (3 layers)</td><td>217K</td><td>0.785</td></tr><tr><td>Ensemble x5 DC (3 layers)</td><td>1.08M</td><td>0.811</td></tr><tr><td>LDR-SD (r = 1)</td><td>140K</td><td>0.701</td></tr><tr><td>LDR-SD (r = 10)</td><td>420K</td><td>0.728</td></tr><tr><td>Toeplitz-like (r = 1)</td><td>110K</td><td>0.711</td></tr><tr><td>Toeplitz-like (r = 10)</td><td>388K</td><td>0.720</td></tr></table>

Comparison with compression based approaches

Table content: <table><tr><td>Architecture</td><td>Settings</td><td colspan="2">#Params Error (%)</td></tr><tr><td>LeNet Lecun et al. (1998)</td><td>-</td><td>4 257 674</td><td>0.61</td></tr><tr><td>DCNN</td><td>8 DC layers 10 DC layers</td><td>25 620 31 764</td><td>1.74 1.60</td></tr><tr><td>Fast Food (FF) Yang et al. (2015)</td><td>Conv + FF 1024 Softmax layer Conv + FF 2048 Softmax Layer</td><td>38 821 52 124</td><td>0.71 0.71</td></tr><tr><td>HashNet Chen et al. (2015)</td><td>3 layers, 1/64 compress. factor 5 layers, 1/64 compress. factor</td><td>46 875 78 125</td><td>2.79 1.99</td></tr><tr><td>Dark Knowledge Hinton et al. (2015)</td><td>3 layers, 1/64 compress.factor 5 layers, 1/64 compress. factor</td><td>46 875 78 125</td><td>6.32 2.16</td></tr><tr><td colspan="4">We provide a comparison with other compression based approaches such as HashNet Chen et al.</td></tr></table>

This table shows the GAP score for the YouTube-8M dataset with DCNNs. We can see a large increase in the score with deeper networks.

Table content: <table><tr><td>Architecture</td><td>#Weights</td><td>GAP@20</td></tr><tr><td>original</td><td>5.7M</td><td>0.773</td></tr><tr><td>4 DC</td><td>25 410 (0.44)</td><td>0.599</td></tr><tr><td>32 DC</td><td>122 178 (2.11)</td><td>0.685</td></tr><tr><td>4 DC + 1 FC</td><td>4.46M (77)</td><td>0.747</td></tr></table>

This table shows the GAP score for the To understand the performance of deep DCNNs on large scale applications, we conducted experiments on the YouTube-8M video classification with 3.8 training examples introduced by Abu-El-Haijaet al. (2016b). Notice that we favour this experiment over ImageNet applications because modern image classification architectures involve a large number of convolutional layers, and compressing convolutional layers is out of our scope. Also, as mentioned earlier, testing the performance of DCNN architectures mixed with a large number of expressive layers makes little sense.

Table content: <table><tr><td colspan="3">YouTube-8M dataset with different layer represented</td></tr><tr><td colspan="2">with our DC decomposition.</td><td/></tr><tr><td>Architecture</td><td colspan="2">#Weights GAP@20</td></tr><tr><td>original</td><td>45M</td><td>0.846</td></tr><tr><td colspan="2">DBoF with DC 36M (80)</td><td>0.838</td></tr><tr><td>FC with DC</td><td>41M (91)</td><td>0.845</td></tr><tr><td>MoE with DC</td><td>12M (26)</td><td>0.805</td></tr></table>

Marko Huhtanen and Allan Perämäki. Factoring matrices into the product of circulant and diagonal matrices. Journal of Fourier Analysis and Applications, 21(5):1018-1033, Oct 2015. ISSN 1531-5851. doi: 10.1007/s00041-015-9395-0. Antoine Miech, Ivan Laptev, and Josef Sivic. Learnable pooling with context gating for video classification. CoRR, abs/1706.06905, 2017. Chiheb Trabelsi, Olexa Bilaniuk, Ying Zhang, Dmitriy Serdyuk, Sandeep Subramanian, João Felipe Santos, Soroush Mehri, Negar Rostamzadeh, Yoshua Bengio, and Christopher J. Pal. Deep complex networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 -May 3, 2018, Conference Track Proceedings, 2018.

Table content: <table/>

Peer review (iclr2020):
This paper proposes a method to replace dense networks with structured (a combination of diagonal and circulant) weight matrices which only uses 2n coefficients instead of n^2 for dense networks. The authors propose a tighter bound for the number of DC (diagonal-circulant) matrices required to approximate a dense network (of depth L), which is dependent on the sum of the rank of matices used in the neural network, as compared to previously used bounds which were dependent only on the dimension of the matrix. They also prove that any DCNN of bounded width and small depth (9k where k is the total rank of all weight matrices used in the deep network) can approximate a deep ReLU network of low rank with comparable accuracy on the downstream tasks. The authors perform experiments to compare with existing compression based methods and outperform them with almost half the total parameters used in the next best approach. Furthermore, they extend their setup to train deep networks with an initialization scheme to avoid vanishing/exploding gradients. Comments: The paper is well organized and seems to carry out substantial experimental work. However, I have some issues with the paper. The proposed rank dependent bound (4k + 1) is useful only if the rank of matrix A (the matrix of dimensions n*n to be approximated) is < n/2. Although the authors have cited papers that claim to explicitly train networks to have low-rank weight matrices, it would be useful to have some guarantees about how low a rank these deep networks can have. The authors claim to have come up with a method to smartly use non-linear functions to train DCNNs. However, the paper doesn*t seem to reflect anything in these lines. The experimental results shown in Figure 2 requires a more in depth study. It would be useful to have a baseline without any sort of non-linearity (with just DCDC pairs in Fig. 2) to have a better understanding of the proposed claims. Some more questions to the authors: 1) It is not very clear as to how the initialization (and the corresponding variance of each layer being independent of the depth) relates to vanishing/exploding gradient problem. Doesn*t the bound have to be on the gradients? Additonally, in the Proofs of Section 5 (of Supplemental Material), how do you account for the decrease in variance due to the use of ReLU? 2) In Figure 3, the convergence of the DCNN model occurs instantly (around the 1st step). Does it mean, it doesn*t require training at all? 3) Is it a standard practise to use ReLU as a nonlinearity in experiments? 4) The results in Table 3 suggest that Convolutions with Fast Food (FF) perform far better than DCNN, with a very small difference in the number of parameters used. It would be interesting to see if the convolution net can be rolled out in the form of dense networks and approximated using a DCNN. The authors can add this baseline to their results.