Aarhus University Seal

Optimal Learning of Joint Alignments with a Faulty Oracle

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Kasper Green Larsen
  • Michael Mitzenmacher, Harvard University
  • ,
  • Charalampos E. Tsourakakis, Boston University

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 1k + δ 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 the recent work by Chen and Candés [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.

Original languageEnglish
Title of host publication2020 IEEE International Symposium on Information Theory, ISIT 2020
Number of pages6
Publication year2020
ISBN (Electronic)9781728164328
Publication statusPublished - 2020
Event2020 IEEE International Symposium on Information Theory, ISIT 2020 - Los Angeles, United States
Duration: 21 Jul 202026 Jul 2020


Conference2020 IEEE International Symposium on Information Theory, ISIT 2020
LandUnited States
ByLos Angeles
SponsorIEEE Information Theory Society, The Institute of Electrical and Electronics Engineers
SeriesIEEE International Symposium on Information Theory - Proceedings

See relations at Aarhus University Citationformats

ID: 196721363