User rankings from comparisons: Learning permutations in high dimensions

摘要: We consider the problem of learning users' preferential orderings for a set items when only limited number pairwise comparisons from users is available. This relevant in large collaborative recommender systems where overall rankings objects need to be predicted using partial information simple item preferences chosen users. two natural schemes obtaining — random and active (or intelligent) sampling. Under both these schemes, assuming that are constrained number, we develop efficient, low-complexity algorithms reconstruct all with provably order-optimal sample complexities. Finally, our shown outperform matrix completion based approach terms computational requirements numerical experiments.