Efficient Identification of Butterfly Sparse Matrix Factorizations
Léon Zheng, Elisa Riccietti, Rémi Gribonval
Source abstract
Abstract. Fast transforms correspond to factorizations of the form [Formula: see text], where each factor [Formula: see text] 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 [Formula: see text] matrix having the so-called butterfly structure admits an essentially unique factorization into [Formula: see text] butterfly factors (where [Formula: see text]), 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 [Formula: see text]. Computing such factorizations costs [Formula: see text], which is on the order of dense matrix-vector multiplication, while the obtained factorizations enable fast [Formula: see text] matrix-vector multiplications and have the potential to be applied to compress deep neural networks.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.