×

Global registration of multiple point clouds using semidefinite programming. (English) Zbl 1322.90058

Summary: Consider \(N\) points in \(\mathbb{R}^d\) and \(M\) local coordinate systems that are related through unknown rigid transforms. For each point, we are given (possibly noisy) measurements of its local coordinates in some of the coordinate systems. Alternatively, for each coordinate system, we observe the coordinates of a subset of the points. The problem of estimating the global coordinates of the \(N\) points (up to a rigid transform) from such measurements comes up in distributed approaches to molecular conformation and sensor network localization, and also in computer vision and graphics. The least-squares formulation of this problem, although nonconvex, has a well-known closed-form solution when \(M=2\) (based on the singular value decomposition (SVD)). However, no closed-form solution is known for \(M\geq 3\). In this paper, we demonstrate how the least-squares formulation can be relaxed into a convex program, namely, a semidefinite program (SDP). By setting up connections between the uniqueness of this SDP and results from rigidity theory, we prove conditions for exact and stable recovery for the SDP relaxation. In particular, we prove that the SDP relaxation can guarantee recovery under more adversarial conditions compared to earlier proposed spectral relaxations, and we derive error bounds for the registration error incurred by the SDP relaxation. We also present results of numerical experiments on simulated data to confirm the theoretical findings. We empirically demonstrate that (a) unlike the spectral relaxation, the relaxation gap is mostly zero for the SDP (i.e., we are able to solve the original nonconvex least-squares problem) up to a certain noise threshold, and (b) the SDP performs significantly better than spectral and manifold-optimization methods, particularly at large noise levels.

MSC:

90C22 Semidefinite programming
52C25 Rigidity and flexibility of structures (aspects of discrete geometry)
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] P.-A. Absil, R. Mahony, and R. Sepulchre, {\it Optimization Algorithms on Matrix Manifolds}, Princeton University Press, Princeton, NJ, 2009. · Zbl 1147.65043
[2] K. S. Arun, T. S. Huang, and S. D. Blostein, {\it Least-squares fitting of two \(3\) d point sets}, IEEE Trans. Pattern Anal. Mach. Intell., (1987), pp. 698-700.
[3] A. S. Bandeira, C. Kennedy, and A. Singer, {\it Approximating the Little Grothendieck Problem over the Orthogonal Group}, preprint, arXiv:1308.5207, 2013. · Zbl 1356.90101
[4] A. S. Bandeira, A. Singer, and D. A. Spielman, {\it A Cheeger inequality for the graph connection Laplacian}, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 1611-1630. · Zbl 1287.05081
[5] S. R. Becker, E. J. Candès, and M. C. Grant, {\it Templates for convex cone problems with applications to sparse signal recovery}, Math. Program. Comput., 3 (2011), pp. 165-218. · Zbl 1257.90042
[6] P. J. Besl and N. D. McKay, {\it A method for registration of 3d shapes}, IEEE Trans. Pattern Anal. Mach. Intell., 14 (1992), pp. 239-256.
[7] R. Bhatia, {\it Matrix Analysis}, Grad. Texts in Math. 169, Springer-Verlag, New York, 1997.
[8] P. Biswas, T.-C. Liang, K.-C. Toh, Y. Ye, and T.-C. Wang, {\it Semidefinite programming approaches for sensor network localization with noisy distance measurements}, IEEE Trans. Automat. Sci. Engrg., 3 (2006), pp. 360-371.
[9] P. Biswas, K.-C. Toh, and Y. Ye, {\it A distributed SDP approach for large-scale noisy anchor-free graph realization with applications to molecular conformation}, SIAM J. Sci. Comput., 30 (2008), pp. 1251-1277. · Zbl 1161.49028
[10] N. Boumal, B. Mishra, P.-A. Absil, and R. Sepulchre, {\it Manopt: A MATLAB toolbox for optimization on manifolds}, J. Mach. Learn. Res., 15 (2014), pp. 1455-1459. · Zbl 1319.90003
[11] S. Burer and R. D. C. Monteiro, {\it A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization}, Math. Program., 95 (2003), pp. 329-357. · Zbl 1030.90077
[12] E. Candes and B. Recht, {\it Exact matrix completion via convex optimization}, Found. Comput. Math., 9 (2009), pp. 717-772. · Zbl 1219.90124
[13] E. J. Candes, T. Strohmer, and V. Voroninski, {\it Phaselift: Exact and stable signal recovery from magnitude measurements via convex programming}, Comm. Pure Appl. Math., 66 (2013), pp. 1241-1274. · Zbl 1335.94013
[14] F. R. K. Chung, {\it Spectral Graph Theory}, CBMS Regional Conf. Ser. in Math. 92, American Mathematical Society, Providence, RI, 1997. · Zbl 0867.05046
[15] R. Connelly, {\it Rigidity and energy}, Invent. Math., 66 (1982), pp. 11-33. · Zbl 0485.52001
[16] M. Cucuringu, Y. Lipman, and A. Singer, {\it Sensor network localization by eigenvector synchronization over the Euclidean group}, ACM Trans. Sensor Networks, 8 (2012), 19.
[17] M. Cucuringu, A. Singer, and D. Cowburn, {\it Eigenvector synchronization, graph rigidity and the molecule problem}, Inform. Inference, 1 (2012), pp. 21-67. · Zbl 1278.05231
[18] A. Edelman, T. A. Arias, and S. T. Smith, {\it The geometry of algorithms with orthogonality constraints}, SIAM J. Matrix Anal. Appl., 20 (1998), pp. 303-353. · Zbl 0928.65050
[19] K. Fan and A. J. Hoffman, {\it Some metric inequalities in the space of matrices}, Proc. Amer. Math. Soc., 6 (1955), pp. 111-116. · Zbl 0064.01402
[20] X. Fang and K.-C. Toh, {\it Using a distributed SDP approach to solve simulated protein molecular conformation problems}, in Distance Geometry, Springer, Berlin, 2013, pp. 351-376. · Zbl 1271.68233
[21] O. D. Faugeras and M. Hebert, {\it The representation, recognition, and locating of 3d objects}, Internat. J. Robotics Res., 5 (1986), pp. 27-52.
[22] D. Garber and E. Hazan, {\it Approximating semidefinite programs in sublinear time}, in Advances in Proceedings of Neural Information Processing Systems 2011, Neural Inform. Process. Systems 24, Neural Information Processing Systems (NIPS) Foundation, La Jolla, CA, pp. 1080-1088.
[23] M. X. Goemans and D. P. Williamson, {\it Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming}, J. ACM, 42 (1995), pp. 1115-1145. · Zbl 0885.68088
[24] G. H. Golub and C. F. Van Loan, {\it Matrix Computations}, 3rd ed., Johns Hopkins University Press, Baltimore, 1996. · Zbl 0865.65009
[25] S. Gortler, C. Gotsman, L. Liu, and D. Thurston, {\it On affine rigidity}, J. Comput. Geom., 4 (2013), pp. 160-181. · Zbl 1404.05136
[26] S. J. Gortler, A. D. Healy, and D. P. Thurston, {\it Characterizing generic global rigidity}, Amer. J. Math., 132 (2010), pp. 897-939. · Zbl 1202.52020
[27] S. J. Gortler and D. P. Thurston, {\it Characterizing the Universal Rigidity of Generic Frameworks}, preprint, arXiv:1001.0172, 2009. · Zbl 1298.05303
[28] J. C. Gower and G. B. Dijksterhuis, {\it Procrustes Problems}, vol. 3, Oxford University Press Oxford, UK, 2004. · Zbl 1057.62044
[29] M. Grant, S. Boyd, and Y. Ye, {\it CVX: MATLAB Software for Disciplined Convex Programming}, http://cvxr.com/cvx/. Accessed January 22, 2015.
[30] C. Helmberg, F. Rendl, R. J. Vanderbei, and H. Wolkowicz, {\it An interior-point method for semidefinite programming}, SIAM J. Optim., 6 (1996), pp. 342-361. · Zbl 0853.65066
[31] B. Hendrickson, {\it Conditions for unique graph realizations}, SIAM J. Comput., 21 (1992), pp. 65-84. · Zbl 0756.05047
[32] N. J. Higham, {\it Computing the polar decomposition–with applications}, SIAM J. Sci. Statist. Comput., 7 (1986), pp. 1160-1174. · Zbl 0607.65014
[33] N.-D. Ho and P. Van Dooren, {\it On the pseudo-inverse of the Laplacian of a bipartite graph}, Appl. Math. Lett., 18 (2005), pp. 917-922. · Zbl 1080.05059
[34] B. K. P. Horn, {\it Closed-form solution of absolute orientation using unit quaternions}, J. Opt. Soc. Am. A, 4 (1987), pp. 629-642.
[35] S. D. Howard, D. Cochran, W. Moran, and F. R. Cohen, {\it Estimation and Registration on Graphs}, preprint, arXiv:1010.2983, 2010.
[36] Q.-X. Huang and L. Guibas, {\it Consistent shape maps via semidefinite programming}, in Proceedings of the Eleventh Eurographics/ACMSIGGRAPH Symposium on Geometry Processing (SGP ’13), ACM, New York, 2013, pp. 177-186.
[37] A. Javanmard and A. Montanari, {\it Localization from incomplete noisy distance measurements}, Found. Comput. Math., 13 (2013), pp. 297-345. · Zbl 1269.05098
[38] M. Journée, F. Bach, P.-A. Absil, and R. Sepulchre, {\it Low-rank optimization on the cone of positive semidefinite matrices}, SIAM J. Optim., 20 (2010), pp. 2327-2351. · Zbl 1215.65108
[39] J. B. Keller, {\it Closest unitary, orthogonal and Hermitian operators to a given operator}, Math. Mag., 48 (1975), pp. 192-197. · Zbl 0357.47019
[40] S. Krishnan, P. Y. Lee, J. B. Moore, and S. Venkatasubramanian, {\it Global registration of multiple 3d point sets via optimization-on-a-manifold}, in Proceedings of the Third Eurographics Symposium on Geometry Processing (SGP ’05), ACM, New York, 2005, 187.
[41] G. Lerman, M. McCoy, J. A. Tropp, and T. Zhang, {\it Robust Computation of Linear Models, or How to Find a Needle in a Haystack}, preprint, arXiv:1202.4044, 2012.
[42] R.-C. Li, {\it New perturbation bounds for the unitary polar factor}, SIAM J. Matrix Anal. Appl., 16 (1995), pp. 327-332. · Zbl 0817.15012
[43] L. Lovász and A. Schrijver, {\it Cones of matrices and set-functions and \(0-1\) optimization}, SIAM J. Optim., 1 (1991), pp. 166-190. · Zbl 0754.90039
[44] L. Mirsky, {\it Symmetric gauge functions and unitarily invariant norms}, Quart. J. Math., 11 (1960), pp. 50-59. · Zbl 0105.01101
[45] N. J. Mitra, N. Gelfand, H. Pottmann, and L. Guibas, {\it Registration of point cloud data from a geometric optimization perspective}, in Proceedings of the 2004 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing (SGP ’04), ACM, New York, 2004, pp. 22-31.
[46] A. Naor, O. Regev, and T. Vidick, {\it Efficient rounding for the noncommutative rothendieck inequality}, in Proceedings of the 45th Annual ACM Symposium on Theory of Computing, ACM, New York, 2013, pp. 71-80. · Zbl 1293.68151
[47] A. Nemirovski, {\it Sums of random symmetric matrices and quadratic optimization under orthogonality constraints}, Math. Programming, 109 (2007), pp. 283-317. · Zbl 1156.90012
[48] Y. Nesterov, {\it Semidefinite relaxation and nonconvex quadratic optimization}, Optim. Methods Software, 9 (1998), pp. 141-160. · Zbl 0904.90136
[49] H. Pottmann, Q.-X. Huang, Y.-L. Yang, and S.-M. Hu, {\it Geometry and convergence analysis of algorithms for registration of \(3\) d shapes}, Internat. J. Comput. Vision, 67 (2006), pp. 277-296. · Zbl 1478.68426
[50] G. Ranjan, Z.-L. Zhang, and D. Boley, {\it Incremental Computation of Pseudo-inverse of Laplacian: Theory and Applications}, preprint, arXiv:1304.2300, 2013.
[51] S. Rusinkiewicz and M. Levoy, {\it Efficient variants of the ICP algorithm}, in Proceedings of the Third International Conference on 3-D Digital Imaging and Modeling (Quebec City, QC), IEEE Press, Piscataway, NJ, 2001, pp. 145-152.
[52] G. C. Sharp, S. W. Lee, and D. K. Wehe, {\it Multiview registration of \(3\) d scenes by minimizing error between coordinate frames}, in Proceedings of the 7th European Conference on Computer Vision–Part II, Springer-Verlag, Berlin, 2002, pp. 587-597. · Zbl 1039.68720
[53] A. Singer, {\it Angular synchronization by eigenvectors and semidefinite programming}, Appl. Comput. Harmon. Anal., 30 (2011), pp. 20-36. · Zbl 1206.90116
[54] A. Singer and M. Cucuringu, {\it Uniqueness of low-rank matrix completion by rigidity theory}, SIAM J. Matrix Anal. Appl., 31(2010), pp. 1621-1641. · Zbl 1221.15038
[55] A. M.-C. So, {\it Moment inequalities for sums of random matrices and their applications in optimization}, Math. Programming, 130 (2011), pp. 125-151. · Zbl 1231.60007
[56] A. M.-C. So and Y. Ye, {\it Theory of semidefinite programming for sensor network localization}, Math. Programming, 109 (2007), pp. 367-384. · Zbl 1278.90482
[57] D. A. Spielman and S.-H. Teng, {\it Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems}, in Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, ACM, New York, 2004, pp. 81-90. · Zbl 1192.65048
[58] K.-C. Toh, M. J. Todd, and R. H. Tutuncu, {\it SDPT3–A MATLAB software package for semidefinite programming, version 1.3}, Optim. Methods Software, 11 (1999), pp. 545-581. · Zbl 0997.90060
[59] T. Tzeneva, {\it Global Alignment of Multiple 3-D Scans Using Eigenvector Synchronization}, Senior thesis, Department of Mathematics, Princeton University, Princeton, NJ, 2011.
[60] L. Vandenberghe and S. Boyd, {\it Semidefinite programming}, SIAM Rev., 38 (1996), pp. 49-95. · Zbl 0845.65023
[61] N. K. Vishnoi, {\it \({Lx=b}\)}, Found. Trends Theoret. Comput. Sci., 8 (2012), pp. 1-141.
[62] I. Waldspurger, A. d’Aspremont, and S. Mallat, {\it Phase recovery, MaxCut and complex semidefinite programming}, Math. Program. Ser. A, 149 (2015), pp. 47-81. · Zbl 1329.94018
[63] L. Wang and A. Singer, {\it Exact and stable recovery of rotations for robust synchronization}, Inform.Inference, 2 (2013), pp. 145-193. · Zbl 1309.65070
[64] Z. Wen, D. Goldfarb, S. Ma, and K. Scheinberg, {\it Block coordinate descent methods for semidefinite programming}, in Handbook on Semidefinite, Conic and Polynomial Optimization, Springer, Berlin, 2012, pp. 533-564. · Zbl 1334.90118
[65] J. A. Williams and M. Bennamoun, {\it Simultaneous registration of multiple point sets using orthonormal matrices}, in Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (Istanbul), vol. 4, IEEE Press, Piscataway, NJ, 2000, pp. 2199-2202.
[66] H. Wolkowicz and M. F. Anjos, {\it Semidefinite programming for discrete optimization and matrix completion problems}, Discrete Appl. Math., 123 (2002), pp. 513-577. · Zbl 1060.90059
[67] H. Wolkowicz, R. Saigal, and L. Vandenberghe, eds., {\it Handbook of Semidefinite Programming: Theory, Algorithms, and Applications}, Internat. Ser. Oper. Res. Management Sci. 27, Springer, Berlin, 2000. · Zbl 0951.90001
[68] H. Zha and Z. Zhang, {\it Spectral properties of the alignment matrices in manifold learning}, SIAM Rev., 51 (2009), pp. 545-566. · Zbl 1180.15012
[69] L. Zhang, L. Liu, C. Gotsman, and S. Gortler, {\it An as-rigid-as-possible approach to sensor network localization}, ACM Trans. Sensor Networks, 6 (2010), 35.
[70] L. Zhi-Quan, M. Wing-Kin, A.M.-C. So, Y. Ye, and S. Zhang, {\it Semidefinite relaxation of quadratic optimization problems}, IEEE Signal Process. Mag., 27 (2010), pp. 20-34.
[71] Z. Zhu, A. M.-C. So, and Y. Ye, {\it Universal rigidity and edge sparsification for sensor network localization}, SIAM J. Optim., 20 (2010), pp. 3059-3081. · Zbl 1211.90166
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.