Efficient Identification of Butterfly Sparse Matrix Factorizations
SIAM Journal on Mathematics of Data Science · 31.03.2023 · 5 (1) · 22-49
DOI: 10.1137/22m1488727 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Mathematics of Data Science, online erschienen am 28.01.2023. Verfasst von Léon Zheng und 2 weiteren Autor:innen. Die Arbeit wurde bisher 10-mal zitiert (Crossref) und nennt 63 Literaturangaben. Gefördert von: Agence Nationale de la Recherche, CIFRE Fellowship.
Abstract (Originalsprache)
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.
Förderung
- Agence Nationale de la Recherche
- CIFRE Fellowship
Zitieren
APA
Zheng, L., Riccietti, E., & Gribonval, R. (2023). Efficient Identification of Butterfly Sparse Matrix Factorizations. SIAM Journal on Mathematics of Data Science, 5(1), 22-49. https://doi.org/10.1137/22m1488727
Vancouver
Zheng L, Riccietti E, Gribonval R. Efficient Identification of Butterfly Sparse Matrix Factorizations. SIAM Journal on Mathematics of Data Science. 2023;5(1):22-49. doi:10.1137/22m1488727
BibTeX
@article{Zheng2023,
author = {Zheng, Léon and Riccietti, Elisa and Gribonval, Rémi},
title = {Efficient Identification of Butterfly Sparse Matrix Factorizations},
journal = {SIAM Journal on Mathematics of Data Science},
year = {2023},
volume = {5},
number = {1},
pages = {22--49},
doi = {10.1137/22m1488727}
}
EUVIMED