Vendredi 23 mai 2014 à 14h30 en salle C017

Eric Sibony (Télécom ParisTech)

Titre : Multiresolution Analysis of Incomplete Rankings

Résumé :

Incomplete rankings on a set of items {1, ..., n} are orderings of the form a1 < ... < ak, with {a1, ..., ak} \subset {1, ..., n} and k < n. Though they arise in many modern applications, only a few methods have been introduced to manipulate them, most of them consisting in representing any incomplete ranking by the set of all its possible linear extensions on {1, ..., n}. In this talk, I will introduce a completely novel approach, which allows to treat incomplete rankings directly, representing them as injective words over {1, ..., n}. Unexpectedly, operations on incomplete rankings have very simple equivalents in this setting and the topological structure of the complex of injective words can be interpretated in a simple fashion from the perspective of ranking. We exploit this connection here and use recent results from algebraic topology to construct a multiresolution analysis and develop a wavelet framework for incomplete rankings. Though purely combinatorial, this construction relies on the same ideas underlying multiresolution analysis on a Euclidean space, and permits to localize the information related to rankings on each subset of items. It can be viewed as a crucial step toward nonlinear approximation of distributions of incomplete rankings and paves the way for many statistical applications, including preference data analysis and the design of recommender systems.