Papers › Efficient Identification of Butterfly Sparse Matrix Factorizations
Efficient Identification of Butterfly Sparse Matrix Factorizations
Léon Zheng, Elisa Riccietti, Rémi Gribonval
Fast transforms correspond to factorizations of the form 𝐙 = 𝐗⁽¹⁾ …𝐗⁽ᴶ⁾, where each factor 𝐗^((ℓ)) 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ᴶ), 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ᴶ. Computing such factorizations costs 𝒪(N²), which is of the order of dense matrix-vector multiplication, while the obtained factorizations enable fast 𝒪(N logN) matrix-vector multiplications and have the potential to be applied to compress deep neural networks.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Methods
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections