Convex Relaxations for Permutation Problems.
TITLE: Convex Relaxations for Permutation Problems.
AUTHORS: Fajwel Fogel, Rodolphe Jenatton, Francis Bach, Alexandre d'Aspremont
ABSTRACT: 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 2sum 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 2sum 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 semisupervised
seriation problems. We present numerical experiments on archeological data,
Markov chains and gene sequences.
STATUS: Preprint.
ArXiv PREPRINT: 1306.4805
PAPER: Convex Relaxations for Permutation Problems in pdf
