Show simple item record

dc.contributor.authorTsourakakis, Charalamposen_US
dc.contributor.authorMitzenmacher, Michaelen_US
dc.contributor.authorGreen Larsen, Kasperen_US
dc.date.accessioned2020-05-13T16:09:24Z
dc.date.available2020-05-13T16:09:24Z
dc.date.issued2019-09-21
dc.identifier.citationCharalampos Tsourakakis, Michael Mitzenmacher, Kasper Green Larsen. "Optimal Learning of Joint Alignments with a Faulty Oracle." Arxiv preprint
dc.identifier.urihttps://hdl.handle.net/2144/40824
dc.description.abstractWe 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.en_US
dc.language.isoen_US
dc.titleOptimal learning of joint alignments with a faulty oracleen_US
dc.typeConference materialsen_US
dc.description.versionFirst author draften_US
pubs.elements-sourcemanual-entryen_US
pubs.notesEmbargo: Not knownen_US
pubs.organisational-groupBoston Universityen_US
pubs.organisational-groupBoston University, College of Arts & Sciencesen_US
pubs.organisational-groupBoston University, College of Arts & Sciences, Department of Computer Scienceen_US
pubs.publication-statusUnpublisheden_US
dc.identifier.mycv540416


This item appears in the following Collection(s)

Show simple item record