nips nips2013 nips2013-300 nips2013-300-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Deepti Pachauri, Risi Kondor, Vikas Singh
Abstract: The problem of matching not just two, but m different sets of objects to each other arises in many contexts, including finding the correspondence between feature points across multiple images in computer vision. At present it is usually solved by matching the sets pairwise, in series. In contrast, we propose a new method, Permutation Synchronization, which finds all the matchings jointly, in one shot, via a relaxation to eigenvector decomposition. The resulting algorithm is both computationally efficient, and, as we demonstrate with theoretical arguments as well as experimental results, much more stable to noise than previous methods. 1
[1] R. E. Burkard, M. Dell’Amico, and S. Martello. Assignment problems. SIAM, 2009.
[2] D. Shen and C. Davatzikos. Hammer: hierarchical attribute matching mechanism for elastic registration. TMI, IEEE, 21, 2002.
[3] K. Duan, D. Parikh, D. Crandall, and K. Grauman. Discovering localized attributes for fine-grained recognition. In CVPR, 2012.
[4] M.F. Demirci, A. Shokoufandeh, Y. Keselman, L. Bretzner, and S. Dickinson. Object recognition as many-to-many feature matching. IJCV, 69, 2006.
[5] M. Goesele, N. Snavely, B. Curless, H. Hoppe, and S.M. Seitz. Multi-view stereo for community photo collections. In ICCV, 2007.
[6] A.C. Berg, T.L. Berg, and J. Malik. Shape matching and object recognition using low distortion correspondences. In CVPR, 2005.
[7] J. Petterson, T. Caetano, J. McAuley, and J. Yu. Exponential family graph matching and ranking. NIPS, 2009.
[8] S. Agarwal, Y. Furukawa, N. Snavely, I. Simon, B. Curless, S.M. Seitz, and R. Szeliski. Building Rome in a day. Communications of the ACM, 54, 2011.
[9] I. Simon, N. Snavely, and S.M. Seitz. Scene summarization for online image collections. In ICCV, 2007.
[10] P.A. Pevzner. Multiple alignment, communication cost, and graph matching. SIAM JAM, 52, 1992.
[11] S. Lacoste-Julien, B. Taskar, D. Klein, and M.I. Jordan. Word alignment via quadratic assignment. In Proc. HLT - NAACL, 2006.
[12] A.J. Smola, S.V.N. Vishwanathan, and Q. Le. Bundle methods for machine learning. NIPS, 20, 2008.
[13] I. Tsochantaridis, T. Joachims, T. Hofmann, Y. Altun, and Y. Singer. Large margin methods for structured and interdependent output variables. JMLR, 6, 2006.
[14] M. Volkovs and R. Zemel. Efficient sampling for bipartite matching problems. In NIPS, 2012.
[15] A. Singer and Y. Shkolnisky. Three-dimensional structure determination from common lines in cryo-EM by eigenvectors and semidefinite programming. SIAM Journal on Imaging Sciences, 4(2):543–572, 2011.
[16] R. Hadani and A. Singer. Representation theoretic patterns in three dimensional cryo-electron microscopy I — the intrinsic reconstitution algorithm. Annals of Mathematics, 174(2):1219–1241, 2011.
[17] R. Hadani and A. Singer. Representation theoretic patterns in three-dimensional cryo-electron microscopy II — the class averaging problem. Foundations of Computational Mathematics, 11(5):589–616, 2011.
[18] Qi-Xing Huang and Leonidas Guibas. Consistent shape maps via semidefinite programming. Computer Graphics Forum, 32(5):177–186, 2013.
[19] H.W. Kuhn. The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2, 1955.
[20] E.P. Wigner. On the distribution of the roots of certain symmetric matrices. Ann. Math, 67, 1958.
[21] Z. F¨ redi and J. Koml´ s. The eigenvalues of random symmetric matrices. Combinatorica, 1, 1981. u o
[22] F. Benaych-Georges and R.R. Nadakuditi. The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices. Advances in Mathematics, 227(1):494–521, 2011.
[23] S. Belongie, J. Malik, and J. Puzicha. Shape matching and object recognition using shape contexts. PAMI, 24(4):509–522, 2002.
[24] R. Roberts, S. Sinha, R. Szeliski, and D. Steedly. Structure from motion for scenes with large duplicate structures. In CVPR, 2011.
[25] T.S. Caetano, J.J. McAuley, L. Cheng, Q.V. Le, and A.J. Smola. Learning graph matching. PAMI, 31(6):1048–1058, 2009.
[26] M. Leordeanu, M. Hebert, and R. Sukthankar. An integer projected fixed point method for graph matching and map inference. In NIPS, 2009.
[27] T. Jebara, J. Wang, and S.F. Chang. Graph construction and b-matching for semi-supervised learning. In ICML, 2009.
[28] A. S. Bandeira, A. Singer, and D. A. Spielman. A Cheeger inequality for the graph connection Laplacian. SIAM Journal on Matrix Analysis and Applications, 34(4):1611–1630, 2013. 9