Convex Relaxations for Permutation Problems
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.
This paper considers the problem of minimizing a 
      quadratic form specified by a similarity matrix A over the class of 
      permutation matrices. The authors first show that when the similarity 
      matrix has a special structure (i.e. A is of the form A = C \circ C^T 
      where C is a pre-Q matrix), then the quadratic form is minimized by the 
      permutation that turns A into an R matrix. It is known that this 
      permutation can be found by computing the Fiedler vector of the Laplacian 
      matrix of A, so we can solve the optimization problem in polynomial time. 
      The second main result is a regularized convex relaxation of the 
      optimization problem in the noisy setting that also allows additional 
      structural constraints. The authors proceed to demonstrate empirically 
      that the convex relaxation is more robust to noise and can achieve a 
      better solution (i.e. a lower objective value) than the manual or spectral 
      solutions, given enough additional structural constraints. This is 
      a nicely written paper with interesting results, both theoretical and 
      practical. The introduction and exposition are mostly clear, although the 
      organization can be a bit improved. The two main results (the spectral 
      solution in the combinatorial case and the convex relaxation in the noisy 
      case) seem to be a bit disjointed. In Section 2, the connections between 
      the different matrices, as well as the various preliminary results, can be 
      confusing at times. Perhaps it would help if the main results (Proposition 
      2.6 and 2.11) are stated in the beginning of the section, or more 
      emphasized than the other preliminary results. Additional 
      comments/questions: * In Equation (2), why do we generalize \pi to 
      y_\pi? It seems the extent of generality considered in this paper is when 
      y is an affine transform of {1,…,n}, in which case (2) is clearly 
      equivalent to problem (1). Can we say anything about more general y? 
      Otherwise, it might help to stick with (1) to minimize notation and 
      confusion. * Although this has been stated in the introduction, it may 
      help to state the problem of seriation mathematically in Section 2 (in 
      terms of permuting A into an R matrix), so that the connection with the 
      combinatorial problem becomes more explicit. * L169-170 in the proof 
      of Proposition 2.6 ("all monotonic subsets of y of a given length have the 
      same (minimal) variance, attained by \Pi y") is not too clear to me. 
      Perhaps it would help to write the problem (2) in terms of the Laplacian 
      matrix (as in (3)) so it becomes more explicit what happens to the problem 
      when we permute A. * In Definition 2.8, what is the weight vector used 
      in the subsequent discussion? Is it w = 1? * L192: AB^T should be AB? 
      * In Proposition 2.11 (and 2.6), is the assumption that A = C \circ 
      C^T with C pre-Q necessary? What about the case when A is a pre-R matrix, 
      but not necessarily of the form A = C \circ C^T? And in practice, how can 
      we check whether the conditions in Proposition 2.11 are satisfied? * 
      Is there anything we can say about the quality of the spectral solution 
      when the assumptions of Proposition 2.11 do not hold exactly? * I 
      think Proposition 3.1 should be placed in Section 2. * In the convex 
      relaxation, how do we choose the values of \mu, p, and the perturbed Y in 
      practice? Is the performance sensitive to the choice of these parameters? 
      * In the caption following Table 1, I think 24% should be 47.5%. I was 
      also a bit confused about the claim that "the semi-supervised solution 
      actually improves on both Kendall's manual solution and on the spectral 
      ordering". Is this based on the combinatorial objective value? Is it clear 
      that this is the correct metric to use to assess performance? * 
      Section 2 and 3 should make it more clear that some of the results are 
      proved in the appendix, and state where in the appendix the results are 
      proved. * The additional experimental results in the appendix can also 
      be organized or labelled better to make clear which application the 
      results are for. * Some of the plots can also benefit from a bit more 
      explanation, such as what the ideal or best case is. For instance, what is 
      the ideal behavior of Figure 3 in the appendix? Should the line be roughly 
      diagonal? How do we compare the three matrices in Figure 5? And why are 
      the two rightmost plots in Figure 2 have different formats? * The 
      second row, third column of Table 2 seems to be missing a value.