Recent results from linear algebra stating that any matrix can be decomposed into products of diagonal and circulant matrices has lead to the design of compact deep neural network architectures that perform well in practice. In this paper, we bridge the gap between these good empirical results 
 and the theoretical approximation capabilities of Deep diagonal-circulant ReLU networks. More precisely, we first demonstrate  that a Deep diagonal-circulant ReLU networks of
 bounded width and small depth can approximate a deep ReLU network in which the dense matrices are
 of low rank. Based on this result, we provide new bounds on the expressive power and universal approximativeness of this type of networks. We support our experimental results with thorough experiments on a large, real world video classification problem. Recent progress in deep neural networks came at the cost of an important increase of model sizes. Nowadays, state-of-the-art architectures for common tasks such as object recognition typically have tens of millions of parameters BID13 ) and up to a billion parameters in some cases BID10 . Best performing (ensemble) models typically combine dozens of such models, and their size can quickly add up to ten or twenty gigabytes. Large models are often more accurate, but training them requires time and large amounts of computational resources. Even when they are trained, they remain difficult to deploy, especially on mobile devices where memory or computational power is limited.In linear algebra, it is common to exploit structural properties of matrices to speedup computations, or reduce memory usage. BID7 have applied this principle in the context of deep neural networks, and proposed a network architecture in which large unstructured weight matrices have been replaced with more compact matrices with a circulant structure. Since any n-by-n circulant matrix can be represented in memory using only a vector of dimension n, the change resulted in a drastic reduction of the model size (from 230MB to 21MB). Furthermore, Cheng et al. have shown empirically that their network architecture can be almost as accurate as the original network. BID23 have proposed a more principled approach leveraging a result by BID16 stating that any matrix A ∈ C n×n can be decomposed into 2n − 1 diagonal and circulant matrices. They use this result to design Deep diagonal-circulant ReLU networks. However their experiments show good results even with a small number of factors (down to 2 factors), suggesting that Deep diagonal-circulant ReLU networks can achieve good approximation error, even with few factors.In this paper, we bridge the gap between the good empirical results observed by BID23 , and the theoretical approximation capabilities of Deep diagonal-circulant ReLU networks. We prove that Deep diagonal-circulant ReLU networks with bounded width and small depth can approximate any dense neural network. We obtain this result by showing that any matrix A can be decomposed into 4k + 1 diagonal and circulant matrices where k is the rank of the matrix A. In practice, this result is more useful than the one by Huhtanen & Perämäki since one can rely on a low rank SVD decomposition of A while controlling the approximation error.In addition to this theoretical contribution, we also conduct thorough experiments on synthetic and real datasets. In accordance with the theory, our experiments demonstrate that we can easily tradeoff accuracy for model size by adjusting the number of factors in the matrix decomposition. Finally we evaluate the applicability of this approach on state-of-the-art neural network architectures trained for video classification on the Youtube-8m Video dataset (over 1TB of training data). This experiment demonstrates that Deep diagonal-circulant ReLU networks can be used to train more compact neural networks on large scale, real world scenarios. In this paper we provided a theoretical study of the properties of Deep diagonal-circulant ReLU networks and demonstrated that they are bounded width universal approximators. The bound on this decomposition allowed us to calculate the error bound on any Deep diagonal-circulant ReLU networks given the depth on the network and the singular values associated with the weight matrices. Our empirical study demonstrate that we can trade-off model size for accuracy in accordance with the theory, and that we can use Deep diagonal-circulant ReLU networks in large scale machine learning applications.
We provide a theoretical study of the properties of Deep circulant-diagonal ReLU Networks and demonstrate that they are bounded width universal approximators. The paper proposes using circulant and diagonal matrices to speed up computation and reduce memory requirements in eural networks. This paper proves that bounded width diagonal-circulent ReLU networks (DC-ReLU) are universal approximators.