  Deep networks, especially convolutional neural networks (CNNs), have been
successfully applied in various areas of machine learning as well as to
challenging problems in other scientific and engineering fields. This paper
introduces Butterfly-Net, a low-complexity CNN with structured and sparse
cross-channel connections, together with a Butterfly initialization strategy
for a family of networks. Theoretical analysis of the approximation power of
Butterfly-Net to the Fourier representation of input data shows that the error
decays exponentially as the depth increases. Combining Butterfly-Net with a
fully connected neural network, a large class of problems are proved to be well
approximated with network complexity depending on the effective frequency
bandwidth instead of the input dimension. Regular CNN is covered as a special
case in our analysis. Numerical experiments validate the analytical results on
the approximation of Fourier kernels and energy functionals of Poisson's
equations. Moreover, all experiments support that training from Butterfly
initialization outperforms training from random initialization. Also, adding
the remaining cross-channel connections, although significantly increase the
parameter number, does not much improve the post-training accuracy and is more
sensitive to data distribution.
