# Efficient Identification of Butterfly Sparse Matrix Factorizations

arXiv: https://arxiv.org/abs/2110.01230 · HTML: https://mlsanity.com/paper/2110.01230/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 74 references that are in the map.
- First posted on arXiv 4 Oct 2021.

## Builds on (most cited first, 12 of 12)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [MLP-Mixer: An all-MLP Architecture for Vision](https://mlsanity.com/paper/2105.01601/) (2021)
- [Learning Fast Algorithms for Linear Transforms Using Butterfly Factorizations](https://mlsanity.com/paper/1903.05895/) (2019)
- [Tunable Efficient Unitary Neural Networks (EUNN) and their application to RNNs](https://mlsanity.com/paper/1612.05231/) (2016)
- [Kaleidoscope: An Efficient, Learnable Representation For All Structured Linear Maps](https://mlsanity.com/paper/2012.14966/) (2020)
- [Quadrature-based features for kernel approximation](https://mlsanity.com/paper/1802.03832/) (2018)
- [Robust and Resource Efficient Identification of Two Hidden Layer Neural Networks](https://mlsanity.com/paper/1907.00485/) (2019)
- [Fast Approximation of Rotations and Hessians matrices](https://mlsanity.com/paper/1404.7195/) (2014)
- [Flexible Multi-layer Sparse Approximations of Matrices and Applications](https://mlsanity.com/paper/1506.07300/) (2015)
- [On the stable recovery of deep structured linear networks under sparsity constraints](https://mlsanity.com/paper/1706.00342/) (2017)
- [Lifting for Blind Deconvolution in Random Mask Imaging: Identifiability and Convex Relaxation](https://mlsanity.com/paper/1501.00046/) (2014)

## Built on by (most cited first, 2 of 2)

- [Efficient Unrolled Networks for Large-Scale 3D Inverse Problems](https://mlsanity.com/paper/2601.02141/) (2026)
- [Fast Inference with Kronecker-Sparse Matrices](https://mlsanity.com/paper/2405.15013/) (2024)

## Abstract (arXiv)

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.