Projections euclidiennes efficaces en temps linéaire

Nous considérons le problème de calculer la projection euclidienne d'un vecteur de longueur n sur un ensemble convexe fermé incluant la boule l1 et les polyèdres spécialisés utilisés dans (Shalev-Shwartz & Singer, 2006). Ces problèmes ont joué des rôles fondamentaux dans la résolution de plusieurs problèmes d'apprentissage sparse basés sur la norme l1. Les méthodes existantes ont une complexité temporelle dans le pire des cas de O(n log n). Dans cet article, nous proposons de reformuler les projections euclidiennes comme des problèmes de recherche de racines associés à des fonctions auxiliaires spécifiques, qui peuvent être résolus en temps linéaire via la bisection. Nous tirons également parti de la structure spéciale des fonctions auxiliaires et proposons un algorithme de bisection amélioré. Des études empiriques montrent que les algorithmes proposés sont beaucoup plus efficaces que ceux de la concurrence pour le calcul des projections.