An optimal algorithm for strict circular seriation.

Abstract: Seriation is an exploratory combinatorial data analysis technique to reorder objects into a sequence along a one-dimensional continuum when the only available information among the objects is their pairwise similarity (or dissimilarity). Linear seriation aims at inferring an ordering (permutation) consistent with an underlying linear order of the data. In many cases however, the data objects may be arranged around a closed continuum yielding a rather circular underlying order. In a matrix representation, this can be visualized as a symmetric matrix of pairwise dissimilarities between objects where elements of each row/column increase monotonically while moving to the right/bottom until some specific element and then decrease again monotonically until the end of each row/column and fold back from the left/top of the matrix. Many approaches used in linear seriation algorithms involve computing the ball hypergraph associated to the dissimilarity. We show that a similar approach can be used in the circular case. In addition to the previous we present an optimal algorithm for strict seriation, which is a natural setting for continuous data.

Date: Nov 25, 2020 at 14:30:00 h
Venue: Modalidad Vía Online.
Speaker: Santiago Armstrong
Affiliation: Pontificia Universidad Católica
More info at:
Event website
Abstract:
PDF

Posted on Nov 23, 2020 in ACGO, Seminars