Optimal learning of joint alignments with a faulty oracle
Files
First author draft
Date
2019-09-21
DOI
Authors
Tsourakakis, Charalampos
Mitzenmacher, Michael
Green Larsen, Kasper
Version
First author draft
OA Version
Citation
Charalampos Tsourakakis, Michael Mitzenmacher, Kasper Green Larsen. "Optimal Learning of Joint Alignments with a Faulty Oracle." Arxiv preprint
Abstract
We consider the following problem, which is useful in applications such as joint image and
shape alignment. The goal is to recover n discrete variables gi ∈ {0, . . . , k − 1} (up to some
global offset) given noisy observations of a set of their pairwise differences {(gi − gj) mod k};
specifically, with probability 1
k + 𝛿 for some 𝛿> 0 one obtains the correct answer, and with
the remaining probability one obtains a uniformly random incorrect answer. We consider a
learning-based formulation where one can perform a query to observe a pairwise difference, and
the goal is to perform as few queries as possible while obtaining the exact joint alignment.
We provide an easy-to-implement, time efficient algorithm that performs O (n lg n
k𝛿^2 ) queries, and
recovers the joint alignment with high probability. We also show that our algorithm is optimal
by proving a general lower bound that holds for all non-adaptive algorithms. Our work improves
significantly recent work by Chen and Cand´es [CC16], who view the problem as a constrained
principal components analysis problem that can be solved using the power method. Specifically,
our approach is simpler both in the algorithm and the analysis, and provides additional insights
into the problem structure.