An Optimal Algorithm for Strict Circular Seriation

We study the problem of circular seriation, where we are given a matrix of pairwise dissimilarities between $n$ objects and the goal is to find a circular order of the objects in a manner that is consistent with their dissimilarity. This problem is a generalization of the classical linear seriation problem, where the goal is to find a linear order and for which optimal ${\cal O}(n^2)$ algorithms are known. Our contributions can be summarized as follows. First, we introduce circular Robinson matrices as the natural class of dissimilarity matrices for the circular seriation problem. Second, for the case of strict circular Robinson dissimilarity, matrices we provide an optimal ${\cal O}(n^2)$ algorithm for the circular seriation problem. Finally, we propose a statistical model to analyze the well-posedness of the circular seriation problem for large $n$. In particular, we establish ${\cal O}(\log(n)/n)$ rates on the distance between any circular ordering found by solving the circular seriation problem to the underlying order of the model in the Kendall-tau metric.