Joint Alignment From Pairwise Differences with a Noisy Oracle

In this work we consider the problem of recovering n discrete random variables xᵢ∈ \0,…,k-1\, 1 ≤ i ≤ n (where k is constant) with the smallest possible number of queries to a noisy oracle that returns for a given query pair (xᵢ,xⱼ) a noisy measurement of their modulo k pairwise difference, i.e., yᵢⱼ = (xᵢ-xⱼ) k. This is a joint discrete alignment problem with important applications in computer vision, graph mining, and spectroscopy imaging. Our main result is a polynomial time algorithm that learns exactly with high probability the alignment (up to some unrecoverable offset) using O(n¹⁺ᵒ⁽¹⁾) queries.