Continuation methods for approximate large scale object sequencing

Evangelopoulos, X, Brockmeier, Austin, Mu, Tingting and Goulermas, JYI ORCID: 0000-0003-0381-124X
(2019) Continuation methods for approximate large scale object sequencing. Machine Learning, 108 (4). 595 - 626.

[img] Text
manuscript.pdf - Accepted Version

Download (4MB)


We propose a set of highly scalable algorithms for the combinatorial data analysis problem of seriating similarity matrices. Seriation consists of finding a permutation of data instances, such that similar instances are nearby in the ordering. Applications of the seriation problem can be found in various disciplines such as in bioinformatics for genome sequencing, data visualization and exploratory data analysis. Our algorithms attempt to minimize certain p-SUM objectives, which also arise in the problem of envelope reduction of sparse matrices. In particular, we present a set of graduated non-convexity algorithms for vector-based relaxations of the general p-SUM problem for p ∈ {2,1,½} that can scale to very large problem sizes. Different choices of p emphasize global versus local similarity pattern structure. We conduct a number of experiments to compare our algorithms to various state-of-the-art combinatorial optimization methods on real and synthetic datasets. The experimental results demonstrate that compared to other approaches, the proposed algorithms are very competitive and scale well with large problem sizes.

Item Type: Article
Uncontrolled Keywords: Combinatorial data analysis, Combinatorial optimization, Graduated non-convexity, Sequencing, Seriation
Depositing User: Symplectic Admin
Date Deposited: 20 Sep 2018 15:50
Last Modified: 19 Aug 2022 15:11
DOI: 10.1007/s10994-018-5764-7
Related URLs: