Butterfly Factorization and Butterfly-Net: from Numerical Linear Algebra to Machine Learning

Speaker: Zhongshu Xu (OSU)
Dates: 2022/10/06
Abstract: Butterfly Factorization is a data-sparse nearly optimal approximation for the discrete Fourier Integral Operator (FIO) matrices. It is constructed based on interpolative low-rank approximations of the complementary low-rank matrix. For an N √óN matrix, it takes O(N log N) operations and complexity to construct the factorization as a product of O(log N) sparse matrices, each with O(N) nonzero entries. After that, the discrete FIO matrix can be multiplicated to any vectors rapidly in O(N log N) operations.
Surprisingly, these sparse matrices in Butterfly Factorization can be viewed as convolutions! Therefore we can construct a simplified structured Convolutional Neural Network (CNN) based on it. This new algorithm, which we named Butterfly-Net, Inherits the advantages of CNN and reduces the computational effort. Together with Butterfly Initialization, which means simply using the elements in Butterfly Factorization matrices to initialize the neural networks, we can complete multiple tasks better and faster.