Continuation methods for approximate large scale object sequencing

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

Text manuscript.pdf - Author Accepted Manuscript Download (4MB)

Abstract

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 Jan 2023 01:16
DOI:	10.1007/s10994-018-5764-7
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3026549