Finding the rank median of three matrices
Leonid Chindelevitch - Simon Fraser University
Feb. 2, 2018, 2:30 p.m. - Feb. 2, 2018, 3:30 p.m.
ENGMC 103
Hosted by: Jérôme Waldispühl
The rank of their difference is a natural measure of distance between two matrices, that has been previously used in coding theory and cryptography. The median of three problem asks to find, given three matrices A, B, and C, the matrix M that minimizes the total rank distance to A, B and C. Despite its apparent simplicity, this linear algebra-based problem presents a rich structure with intriguing connections to graph and hypergraph theory, as well as permutation group theory.
This work is inspired by an application in computational biology, where matrices can be used to represent genomes, and the rank distance counts a weighted number of genome rearrangements events through evolution. The median of three problem, which is NP-hard for most models, can only be solved efficiently for a handful of them. However, it also has applications in ranking problems, where a consensus ranking is to be established between a number of rankings over the same collection of objects. In this talk we present some results on the median of three problem for matrices, including an exact polynomial-time solution for the orthogonal case, which encompasses both permutations and genomes. We conclude with some open problems and conjectures on their solutions. This work is in collaboration with Joao Meidanis.
