论文标题
与嘈杂的甲骨文的成对差异的联合对齐
Joint Alignment From Pairwise Differences with a Noisy Oracle
论文作者
论文摘要
In this work we consider the problem of recovering $n$ discrete random variables $x_i\in \{0,\ldots,k-1\}, 1 \leq i \leq n$ (where $k$ is constant) with the smallest possible number of queries to a noisy oracle that returns for a given query pair $(x_i,x_j)$ a noisy measurement of their modulo $k$成对差异，即$ y_ {ij} =（x_i-x_j）\ mod k $。这是一个关节离散的问题，在计算机视觉，图形挖掘和光谱成像中的重要应用。我们的主要结果是一种多项式时间算法，它使用$ O（n^{1+o（1）}）$ queries准确地以高概率学习（直至某些无法恢复的偏移）。
In this work we consider the problem of recovering $n$ discrete random variables $x_i\in \{0,\ldots,k-1\}, 1 \leq i \leq n$ (where $k$ is constant) with the smallest possible number of queries to a noisy oracle that returns for a given query pair $(x_i,x_j)$ a noisy measurement of their modulo $k$ pairwise difference, i.e., $y_{ij} = (x_i-x_j) \mod 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^{1+o(1)})$ queries.
