Inferring Rankings under Constrained Sensing

Опубликовано 7 сентября 2016, 17:11

Motivated by applications like elections, network measurements, web-page ranking, revenue maximization etc., we consider the question of inferring popular rankings given constrained data. Specifically, we consider the problem of inferring a probability distribution over the space of permutations using its first order marginals. We characterize the precise conditions (in terms of the sparsity of the support of the distribution) under which the distribution can be recovered. The question considered in this talk is thematically related to Fourier Transforms over the symmetric group and the currently popular topic of compressed sensing. Time permitting we shall discuss certain extensions in terms of robust formulation of the problem with a specific application as well as the tradeoff between partial information and recoverability.