Timezone: »

Convex Relaxations for Permutation Problems
Fajwel Fogel · Rodolphe Jenatton · Francis Bach · Alexandre d'Aspremont

Thu Dec 05 07:00 PM -- 11:59 PM (PST) @ Harrah's Special Events Center, 2nd Floor

Seriation seeks to reconstruct a linear order between variables using unsorted similarity information. It has direct applications in archeology and shotgun gene sequencing for example. We prove the equivalence between the seriation and the combinatorial 2-sum problem (a quadratic minimization problem over permutations) over a class of similarity matrices. The seriation problem can be solved exactly by a spectral algorithm in the noiseless case and we produce a convex relaxation for the 2-sum problem to improve the robustness of solutions in a noisy setting. This relaxation also allows us to impose additional structural constraints on the solution, to solve semi-supervised seriation problems. We present numerical experiments on archeological data, Markov chains and gene sequences.

Author Information

Fajwel Fogel (École Polytechnique)
Rodolphe Jenatton (Amazon Research)
Francis Bach (INRIA - Ecole Normale Superieure)
Alexandre d'Aspremont (CNRS - ENS)

More from the Same Authors