Learning sparse mixtures of permutations from noisy information

We study the problem of learning an unknown mixture of k permutations over n elements, given access to noisy samples drawn from the unknown mixture. We consider a range of different noise models, including natural variants of the “heat kernel” noise framework and the Mallows model. We give an algorithm which, for each of these noise models, learns the unknown mixture to high accuracy under mild assumptions and runs in $n^{O(log k)}$ time. Our approach is based on a new procedure that recovers an unknown mixture of permutations from noisy higher-order marginals.