Efficient Identification of Butterfly Sparse Matrix Factorizations

Code

• github.com/leonzheng2/efficient-butterfly
  OfficialIn papernone★ 3

Abstract

Fast transforms correspond to factorizations of the form Z = X^(1) X^(J), where each factor X^() is sparse and possibly structured. This paper investigates essential uniqueness of such factorizations, i.e., uniqueness up to unavoidable scaling ambiguities. Our main contribution is to prove that any N N matrix having the so-called butterfly structure admits an essentially unique factorization into J butterfly factors (where N = 2^J), and that the factors can be recovered by a hierarchical factorization method, which consists in recursively factorizing the considered matrix into two factors. This hierarchical identifiability property relies on a simple identifiability condition in the two-layer and fixed-support setting. This approach contrasts with existing ones that fit the product of butterfly factors to a given matrix via gradient descent. The proposed method can be applied in particular to retrieve the factorization of the Hadamard or the discrete Fourier transform matrices of size N=2^J. Computing such factorizations costs O(N^2), which is of the order of dense matrix-vector multiplication, while the obtained factorizations enable fast O(N N) matrix-vector multiplications and have the potential to be applied to compress deep neural networks.

Reproductions