Scaling is all you need: quantization of butterfly matrix products via optimal rank-one quantization

Autor: Gribonval, Rémi, Mary, Theo, Riccietti, Elisa
Přispěvatelé: Optimisation, Connaissances pHysiques, Algorithmes et Modèles (OCKHAM), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut Rhône-Alpin des systèmes complexes (IXXI), École normale supérieure de Lyon (ENS de Lyon)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), GDR ISIS project MOMIGS, ANR-19-CHIA-0009,AllegroAssai,Algorithmes, Approximations, Parcimonie et Plongements pour l'IA(2019)
Jazyk: angličtina
Rok vydání: 2023
Předmět:
Popis: We consider the problem of quantizing the factors of butterfly factorizations. We show how the properties of butterfly supports can be exploited to reduce the problem to the solution of a series of rank-one quantization problems. We thus propose an algorithm that, exploiting the intrinsic scaling invariance of the problem, gives the optimal solution of the rank-one quantization problem. We employ this algorithm as a building block in a heuristic procedure to solve the quantization problem of butterfly factors, which we show can be much more accurate that the naive round-to-nearest startegy of quantizing each factor independently.; On s'intéresse à la quantification des facteurs dans un produit de matrices creuses à structure papillon. On montre que les propriétés particulières es supports des facteurs papillon permettent d'aborder le problème comme une séquence de problème de quantification de rang un. On propose un algorithme optimal de quantification de rang un utilisant les invariances du problème par remise à l'échelle. Cet algorithme sert de brique de base dans une approche heuristique pour la quantification de produits papillon, qui s'avère bien plus précis qu'une approche naive basée sur la quantification de chaque facteur au plus proche voisin indépendamment.
Databáze: OpenAIRE
Externí odkaz: