Algorithme de Lloyd-Max

En algorithmique et en traitement du signal, l’algorithme de Lloyd-Max est un algorithme qui permet de construire le quantifieur scalaire optimal. C'est donc une méthode pour quantifier un signal en une dimension de manière à minimiser la distorsion, mesurée par l'erreur quadratique moyenne. L'optimalité du quantifieur est assurée par deux conditions sur les niveaux de reconstruction et de décision, découvertes par Lloyd en 1957. Il fournit aussi un algorithme, qui permet de construire itérativement le quantifieur optimal. L'algorithme peut être étendu à la quantification de vecteurs (algorithme de Linde-Buzo-Gray). L'algorithme fut développé par Lloyd en 1957, mais n'a pas été publié en revue scientifique. Il fut présenté à l'Institut de Statistiques Mathématiques et la seule version imprimée est un mémorandum technique des laboratoires Bell. L'algorithme resta donc peu connu pendant plusieurs années. Les résultats exposés dans le mémorandum furent redécouverts indépendamment par plusieurs chercheurs. Cependant toutes ces redécouvertes utilisèrent des dérivations différentes de celle utilisée par Lloyd, indispensable pour l'extension du théorème à la quantification de vecteurs et pour plusieurs procédures d'optimisation de quantificateurs.