nips nips2013 nips2013-73 nips2013-73-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: 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 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. 1
[1] William S Robinson. A method for chronologically ordering archaeological deposits. American antiquity, 16(4):293–301, 1951.
[2] Stephen T Barnard, Alex Pothen, and Horst Simon. A spectral algorithm for envelope reduction of sparse matrices. Numerical linear algebra with applications, 2(4):317–334, 1995.
[3] D.R. Fulkerson and O. A. Gross. Incidence matrices and interval graphs. Pacific journal of mathematics, 15(3):835, 1965.
[4] Gemma C Garriga, Esa Junttila, and Heikki Mannila. Banded structure in binary matrices. Knowledge and information systems, 28(1):197–226, 2011.
[5] Jo˜ o Meidanis, Oscar Porto, and Guilherme P Telles. On the consecutive ones property. Discrete Applied a Mathematics, 88(1):325–354, 1998.
[6] David G Kendall. Abundance matrices and seriation in archaeology. Probability Theory and Related Fields, 17(2):104–112, 1971.
[7] Chris Ding and Xiaofeng He. Linearized cluster assignment via spectral ordering. In Proceedings of the twenty-first international conference on Machine learning, page 30. ACM, 2004.
[8] Niko Vuokko. Consecutive ones property and spectral ordering. In Proceedings of the 10th SIAM International Conference on Data Mining (SDM’10), pages 350–360, 2010.
[9] Innar Liiv. Seriation and matrix reordering methods: An historical overview. Statistical analysis and data mining, 3(2):70–91, 2010.
[10] Alan George and Alex Pothen. An analysis of spectral envelope reduction via quadratic assignment problems. SIAM Journal on Matrix Analysis and Applications, 18(3):706–732, 1997.
[11] Eugene L Lawler. The quadratic assignment problem. Management science, 9(4):586–599, 1963.
[12] Qing Zhao, Stefan E Karisch, Franz Rendl, and Henry Wolkowicz. Semidefinite programming relaxations for the quadratic assignment problem. Journal of Combinatorial Optimization, 2(1):71–109, 1998.
[13] A. Nemirovski. Sums of random symmetric matrices and quadratic optimization under orthogonality constraints. Mathematical programming, 109(2):283–317, 2007.
[14] Anthony Man-Cho So. Moment inequalities for sums of random matrices and their applications in optimization. Mathematical programming, 130(1):125–151, 2011.
[15] J.E. Atkins, E.G. Boman, B. Hendrickson, et al. A spectral algorithm for seriation and the consecutive ones problem. SIAM J. Comput., 28(1):297–310, 1998.
[16] F. Fogel, R. Jenatton, F. Bach, and A. d’Aspremont. Convex relaxations for permutation problems. arXiv:1306.4805, 2013.
[17] Erling D Andersen and Knud D Andersen. The mosek interior point optimizer for linear programming: an implementation of the homogeneous algorithm. High performance optimization, 33:197–232, 2000.
[18] M. Frank and P. Wolfe. An algorithm for quadratic programming. Naval research logistics quarterly, 3(1-2):95–110, 1956.
[19] L Portugal, F Bastos, J J´ dice, J Paixao, and T Terlaky. An investigation of interior-point algorithms for u the linear transportation problem. SIAM Journal on Scientific Computing, 17(5):1202–1223, 1996.
[20] Y. Nesterov. Introductory Lectures on Convex Optimization. Springer, 2003.
[21] D. Bertsekas. Nonlinear Programming. Athena Scientific, 1998.
[22] Frank Roy Hodson. The La T` ne cemetery at M¨ nsingen-Rain: catalogue and relative chronology, vole u ume 5. St¨ mpfli, 1968. a
[23] Thomas M Cover and Joy A Thomas. Elements of information theory. Wiley-interscience, 2012. 9