Efficient Identification of Butterfly Sparse Matrix Factorizations

Fast transforms correspond to factorizations of the form Z = X(1) ldots 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 = 2J), 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=2J. Computing such factorizations costs O(N2), which is of the order of dense matrix-vector multiplication, while the obtained factorizations enable fast O(N log N) matrix-vector multiplications and have the potential to be applied to compress deep neural networks.