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 em circular order of the objects in a manner that is consistent with their dissimilarity. This problem is a generalization of the classical em linear seriation problem where the goal is to find a em linear order, and for which optimal cal O(n2) algorithms are known. Our contributions can be summarized as follows. First, we introduce em circular Robinson matrices as the natural class of dissimilarity matrices for the circular seriation problem. Second, for the case of em strict circular Robinson dissimilarity matrices we provide an optimal cal O(n2) 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.