EUVIMEDEUVIMED entdecken
Crossref

Efficient Identification of Butterfly Sparse Matrix Factorizations

Léon Zheng, Elisa Riccietti, Rémi Gribonval

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →