Efficient Identification of Butterfly Sparse Matrix Factorizations
Résumé
Fast transforms correspond to factorizations of the form $\mathbf{Z} = \mathbf{X}^{(1)} \ldots \mathbf{X}^{(J)}$, where each factor $ \mathbf{X}^{(\ell)}$ 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 \times N$ matrix having the so-called butterfly structure admits an essentially unique factorization into $J$ butterfly factors (where $N = 2^{J}$), 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^J$. Computing such factorizations costs $\mathcal{O}(N^{2})$, which is of the order of dense matrix-vector multiplication, while the obtained factorizations enable fast $\mathcal{O}(N \log N)$ matrix-vector multiplications and have the potential to be applied to compress deep neural networks.
Fichier principal
main.pdf (730.58 Ko)
Télécharger le fichier
S_1.pdf (2.25 Ko)
Télécharger le fichier
S_2.pdf (2.29 Ko)
Télécharger le fichier
S_3.pdf (2.27 Ko)
Télécharger le fichier
S_4.pdf (2.31 Ko)
Télécharger le fichier
arbitrary_factor_bracketing.pdf (24.11 Ko)
Télécharger le fichier
balanced_factor_bracketing.pdf (22.02 Ko)
Télécharger le fichier
balanced_vs_unbalanced_large_dim.pdf (15.19 Ko)
Télécharger le fichier
balanced_vs_unbalanced_low_dim.pdf (14.31 Ko)
Télécharger le fichier
benchmark_hierarchical_balanced.pdf (17.84 Ko)
Télécharger le fichier
benchmark_hierarchical_unbalanced.pdf (17.79 Ko)
Télécharger le fichier
benchmark_svd_rectangle.pdf (17.01 Ko)
Télécharger le fichier
benchmark_svd_square.pdf (17.01 Ko)
Télécharger le fichier
symmetric_unbalanced_factor_bracketing.pdf (22.8 Ko)
Télécharger le fichier
unbalanced_factor_bracketing.pdf (28.13 Ko)
Télécharger le fichier
w_2_1.pdf (2.31 Ko)
Télécharger le fichier
w_3_1.pdf (1.31 Ko)
Télécharger le fichier
w_3_2.pdf (2.35 Ko)
Télécharger le fichier
w_4_2.pdf (2.32 Ko)
Télécharger le fichier
w_4_3.pdf (2.33 Ko)
Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Origine : Fichiers produits par l'(les) auteur(s)
Origine : Fichiers produits par l'(les) auteur(s)
Origine : Fichiers produits par l'(les) auteur(s)
Origine : Fichiers produits par l'(les) auteur(s)
Origine : Fichiers produits par l'(les) auteur(s)
Origine : Fichiers produits par l'(les) auteur(s)
Origine : Fichiers produits par l'(les) auteur(s)
Origine : Fichiers produits par l'(les) auteur(s)