Regroupement discriminatif robuste avec des régularisateurs épars.

Résumé La mise en grappes de données à haute dimension nécessite souvent une certaine forme de réduction de la dimensionnalité, où les variables mises en grappes sont séparées des variables " bruyantes ". Ce problème consiste à trouver une projection à faible dimension des données qui sont bien groupées. Cela donne une projection unidimensionnelle dans la situation la plus simple avec deux clusters, et s'étend naturellement à un scénario multi-label pour plus de deux clusters. Dans cet article, (a) nous montrons d'abord que cette formulation conjointe de clustering et de réduction de dimension est équivalente aux cadres de clustering discriminatif proposés précédemment, ce qui conduit à des relaxations convexes du problème. (b) Nous proposons une nouvelle extension éparse, qui reste une relaxation convexe et permet l'estimation dans des dimensions supérieures. (c) Nous proposons une extension naturelle pour le scénario multi-labels. (d) nous fournissons une nouvelle analyse théorique de la performance de ces formulations avec un modèle probabiliste simple, conduisant à des mises à l'échelle de la forme d = O(√ n) pour le cas affine invariant et d = O(n) pour le cas clairsemé, où n est le nombre d'exemples et d la dimension ambiante. et enfin, (e) nous proposons un algorithme itératif efficace avec une complexité de temps d'exécution proportionnelle à O(nd 2), améliorant les algorithmes précédents qui avaient une complexité quadratique dans le nombre d'exemples.