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 diagonalcirculant ReLU networks. More precisely, we first demonstrate that a Deep diagonalcirculant 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.
The experiments in the paper are similar to those explored in previous work! The main contribution claimed in the paper is the theoretical formulation for compact design of neural networks using circulant matrices instead of fully connected matrices. 
I do not think the claim is sufficiently justified by the theoretical results provided. 
Earlier result already shows how any matrix fully connected matrices can be approximated by 2n-1 circulant matrices. As the authors themselves point out, this theoretical result does not necessarily imply reduction in number of parameters since the for a depth l network, the equivalent diagonal-circulant-ReLU network will now require (2n-1)l depth, or 2n(2n-1)l parameters. 
The main results (Proposition 3, 4) show that if the fully connected networks of depth l network are parameterized by (approximately) rank k matrices, then the resultant depth of diagonal-circulant network required to approximate the original network is (4k+1)l, which results in a total of 8n(4k+1)l parameters. Similar to the case of full rank fully connected networks (proposition 2), this result does not necessarily indicate a compression of number of parameters either. In particular, if fully connected networks are indeed rank k, then we only need nkl parameters parameters to represent the matrix, which is lower than the number of parameters required by the diagonal-circulant network. 
So I do not see how the result can be seen as a justification for using diagonal-circulant networks as compact representations. 
Writing:
Theorem 1: The statement about approximability with B_1B_2…B_{2n-1} is independent of p and S. 
Proposition 3: The expression for depth should be \sum_{i=1}^l (4k_i+1)  — sum should go from i=1 to l and there should be no multiplicative factor l 
Other non-critical comments: Multiplication by circulant matrices amounts to circular convolution with full dimensional kernel. In this sense, replacing a fully connected layers by circulant matrices is similar to replacing it with convolutional layers.  May be this connection can be explicitly stated in the paper.