{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T12:27:44Z","timestamp":1672576064622},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2017,11,20]],"date-time":"2017-11-20T00:00:00Z","timestamp":1511136000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2017,12,31]]},"abstract":"Correspondence problems are often modelled as quadratic optimization problems over permutations. Common scalable methods for approximating solutions of these NP-hard problems are the spectral relaxation for non-convex energies and the doubly stochastic (DS) relaxation for convex energies. Lately, it has been demonstrated that semidefinite programming relaxations can have considerably improved accuracy at the price of a much higher computational cost.<\/jats:p>\n We present a convex quadratic programming relaxation which is provably stronger than both DS and spectral relaxations, with the same scalability as the DS relaxation. The derivation of the relaxation also naturally suggests a projection method for achieving meaningful integer solutions which improves upon the standard closest-permutation projection. Our method can be easily extended to optimization over doubly stochastic matrices, injective matching, and problems with additional linear constraints. We employ recent advances in optimization of linear-assignment type problems to achieve an efficient algorithm for solving the convex relaxation.<\/jats:p>\n We present experiments indicating that our method is more accurate than local minimization or competing relaxations for non-convex problems. We successfully apply our algorithm to shape matching and to the problem of ordering images in a grid, obtaining results which compare favorably with state of the art methods.<\/jats:p>\n We believe our results indicate that our method should be considered the method of choice for quadratic optimization over permutations.<\/jats:p>","DOI":"10.1145\/3130800.3130826","type":"journal-article","created":{"date-parts":[[2017,11,22]],"date-time":"2017-11-22T16:25:08Z","timestamp":1511367908000},"page":"1-14","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":34,"title":["DS++"],"prefix":"10.1145","volume":"36","author":[{"given":"Nadav","family":"Dym","sequence":"first","affiliation":[{"name":"Weizmann Institute of Science"}]},{"given":"Haggai","family":"Maron","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science"}]},{"given":"Yaron","family":"Lipman","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science"}]}],"member":"320","published-online":{"date-parts":[[2017,11,20]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Warren P Adams and Terri A Johnson. 1994. Improved linear programming-based lower bounds for the quadratic assignment problem. DIMACS series in discrete mathematics and theoretical computer science 16 (1994) 43--75. Warren P Adams and Terri A Johnson. 1994. Improved linear programming-based lower bounds for the quadratic assignment problem. DIMACS series in discrete mathematics and theoretical computer science 16 (1994) 43--75.","DOI":"10.1090\/dimacs\/016\/02"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1401651112"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00011402"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/141000439"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2014.491"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2016.09.018"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Ken Chatfield Karen Simonyan Andrea Vedaldi and Andrew Zisserman. 2014. Return of the devil in the details: Delving deep into convolutional nets. arXiv preprint arXiv:1405.3531 (2014). Ken Chatfield Karen Simonyan Andrea Vedaldi and Andrew Zisserman. 2014. Return of the devil in the details: Delving deep into convolutional nets. arXiv preprint arXiv:1405.3531 (2014).","DOI":"10.5244\/C.28.6"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2015.236"},{"key":"e_1_2_1_9_1","unstructured":"Marco Cuturi. 2013. Sinkhorn distances: Lightspeed computation of optimal transport. In Advances in Neural Information Processing Systems. 2292--2300. Marco Cuturi. 2013. Sinkhorn distances: Lightspeed computation of optimal transport. In Advances in Neural Information Processing Systems. 2292--2300."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1360612.1360697"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1090.0419"},{"key":"e_1_2_1_12_1","unstructured":"Nadav Dym and Yaron Lipman. 2016. Exact Recovery with Symmetries for Procrustes Matching. arXiv preprint arXiv:1606.01548 (2016). Nadav Dym and Yaron Lipman. 2016. Exact Recovery with Symmetries for Procrustes Matching. arXiv preprint arXiv:1606.01548 (2016)."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/83.623193"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00371-012-0674-3"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1093\/imaiai\/iav002"},{"key":"e_1_2_1_16_1","unstructured":"Fajwel Fogel Rodolphe Jenatton Francis Bach and Alexandre d'Aspremont. 2013. Convex relaxations for permutation problems. In Advances in Neural Information Processing Systems. 1016--1024. Fajwel Fogel Rodolphe Jenatton Francis Bach and Alexandre d'Aspremont. 2013. Convex relaxations for permutation problems. In Advances in Neural Information Processing Systems. 1016--1024."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/130947362"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12549"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1162\/neco.1994.6.1.161"},{"key":"e_1_2_1_20_1","unstructured":"Daniela Giorgi Silvia Biasotti and Laura Paraboschi. 2007. Shape retrieval contest 2007: Watertight models track. SHREC competition 8 (2007). Daniela Giorgi Silvia Biasotti and Laura Paraboschi. 2007. Shape retrieval contest 2007: Watertight models track. SHREC competition 8 (2007)."},{"key":"e_1_2_1_22_1","first-page":"5","article-title":"Tight Relaxation of Quadratic","volume":"34","author":"Kezurer Itay","year":"2015","journal-title":"Matching. Comput. Graph. Forum"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2010324.1964974"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2006.200"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0893-6080(94)90081-7"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2005.20"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1531326.1531378"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2009.5206744"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Eliane Maria Loiola Nair Maria Maia de Abreu Paulo Oswaldo Boaventura-Netto Peter Hahn and Tania Querido. 2007. A survey for the quadratic assignment problem. European journal of operational research 176 2 (2007) 657--690. Eliane Maria Loiola Nair Maria Maia de Abreu Paulo Oswaldo Boaventura-Netto Peter Hahn and Tania Querido. 2007. A survey for the quadratic assignment problem. European journal of operational research 176 2 (2007) 657--690.","DOI":"10.1016\/j.ejor.2005.09.032"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2015.2424894"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925913"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCVW.2015.112"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Facundo M\u00e9moli. 2011. Gromov-Wasserstein distances and the metric approach to object matching. Foundations of computational mathematics 11 4 (2011) 417--487. Facundo M\u00e9moli. 2011. Gromov-Wasserstein distances and the metric approach to object matching. Foundations of computational mathematics 11 4 (2011) 417--487.","DOI":"10.1007\/s10208-011-9093-5"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/3115504.3115930"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/GLOCOM.1990.116718"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185526"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5244\/C.29.41"},{"key":"e_1_2_1_38_1","unstructured":"Novi Quadrianto Le Song and Alex J Smola. 2009. Kernelized sorting. In Advances in neural information processing systems. 1289--1296. Novi Quadrianto Le Song and Alex J Smola. 2009. Kernelized sorting. In Advances in neural information processing systems. 1289--1296."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1162\/neco.1996.8.5.1041"},{"key":"e_1_2_1_40_1","unstructured":"Anand Rangarajan Alan L Yuille Steven Gold and Eric Mjolsness. 1997. A convergence proof for the soft assign quadratic assignment algorithm. Advances in neural information processing systems (1997) 620--626. Anand Rangarajan Alan L Yuille Steven Gold and Eric Mjolsness. 1997. A convergence proof for the soft assign quadratic assignment algorithm. Advances in neural information processing systems (1997) 620--626."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/2354409.2354702"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2014.532"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/648286.756110"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2462003"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766963"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2012.03167.x"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925903"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMM.2014.2306183"},{"key":"e_1_2_1_49_1","volume-title":"Computer Graphics Forum","author":"Kaick Oliver Van"},{"key":"e_1_2_1_50_1","doi-asserted-by":"crossref","unstructured":"Lingyu Wei Qixing Huang Duygu Ceylan Etienne Vouga and Hao Li. 2016. Dense Human Body Correspondences Using Convolutional Networks. In Computer Vision and Pattern Recognition (CVPR). Lingyu Wei Qixing Huang Duygu Ceylan Etienne Vouga and Hao Li. 2016. Dense Human Body Correspondences Using Convolutional Networks. In Computer Vision and Pattern Recognition (CVPR).","DOI":"10.1109\/CVPR.2016.171"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2007.1036"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1080\/10556780701843405"},{"key":"e_1_2_1_53_1","volume-title":"2010 IEEE conference on. IEEE, 3485--3492","author":"Xiao Jianxiong","year":"2010"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2008.245"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2010.5540189"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009795911987"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2015.7298976"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3130800.3130826","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,31]],"date-time":"2022-12-31T10:48:41Z","timestamp":1672483721000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3130800.3130826"}},"subtitle":["a flexible, scalable and provably tight relaxation for matching problems"],"short-title":[],"issued":{"date-parts":[[2017,11,20]]},"references-count":56,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2017,12,31]]}},"alternative-id":["10.1145\/3130800.3130826"],"URL":"http:\/\/dx.doi.org\/10.1145\/3130800.3130826","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":["Computer Graphics and Computer-Aided Design"],"published":{"date-parts":[[2017,11,20]]},"assertion":[{"value":"2017-11-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}