{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:28:17Z","timestamp":1787340497439,"version":"3.56.0"},"reference-count":71,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>Consider $N$ points in ${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.<\/jats:p>","DOI":"10.1137\/130935458","type":"journal-article","created":{"date-parts":[[2015,3,4]],"date-time":"2015-03-04T13:24:14Z","timestamp":1425475454000},"page":"468-501","source":"Crossref","is-referenced-by-count":57,"title":["Global Registration of Multiple Point Clouds Using Semidefinite Programming"],"prefix":"10.1137","volume":"25","author":[{"given":"K. N.","family":"Chaudhury","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Y.","family":"Khoo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"A.","family":"Singer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,3,4]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"P.A. Absil, R. Mahony, and R. Sepulchre,\n                      Optimization Algorithms on Matrix Manifolds\n                      , Princeton University Press, Princeton, NJ, 2009.","DOI":"10.1515\/9781400830244"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"K. S. Arun, T. S. Huang, and S. D. Blostein,\n                      Least-squares fitting of two $3$d point sets\n                      , IEEE Trans. Pattern Anal. Mach. Intell. (1987), pp. 698-700.","DOI":"10.1109\/TPAMI.1987.4767965"},{"key":"atypb3","unstructured":"A. S. Bandeira, C. Kennedy, and A. Singer,\n                      Approximating the Little Grothendieck Problem over the Orthogonal Group\n                      , preprint, arXiv:1308.5207, 2013."},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/120875338"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-011-0029-5"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1109\/34.121791"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"R. Bhatia,\n                      Matrix Analysis\n                      , Grad. Texts in Math. 169, Springer-Verlag, New York, 1997.","DOI":"10.1007\/978-1-4612-0653-8"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1109\/TASE.2006.877401"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/05062754X"},{"key":"atypb10","first-page":"1455","volume":"15","author":"Boumal N.","year":"2014","journal-title":"J. Mach. Learn. Res."},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-002-0352-8"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-009-9045-5"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.21432"},{"key":"atypb14","unstructured":"F. R. K. Chung,\n                      Spectral Graph Theory\n                      , CBMS Regional Conf. Ser. in Math. 92, American Mathematical Society, Providence, RI, 1997."},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/BF01404753"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1145\/2240092.2240093"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1093\/imaiai\/ias002"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479895290954"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1955-0067841-7"},{"key":"atypb20","first-page":"351","author":"Fang X.","year":"2013","journal-title":"Berlin"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1177\/027836498600500302"},{"key":"atypb22","unstructured":"D. Garber and E. Hazan,\n                      Approximating semidefinite programs in sublinear time\n                      , 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."},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"atypb24","unstructured":"G. H. Golub and C. F. Van Loan,\n                      Matrix Computations\n                      , 3rd ed., Johns Hopkins University Press, Baltimore, 1996."},{"key":"atypb25","first-page":"160","volume":"4","author":"Gortler S.","year":"2013","journal-title":"J. Comput. Geom."},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1353\/ajm.0.0132"},{"key":"atypb27","unstructured":"S. J. Gortler and D. P. Thurston,\n                      Characterizing the Universal Rigidity of Generic Frameworks\n                      , preprint, arXiv:1001.0172, 2009."},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"J. C. Gower and G. B. Dijksterhuis,\n                      Procrustes Problems\n                      , vol. 3, Oxford University Press Oxford, UK, 2004.","DOI":"10.1093\/acprof:oso\/9780198510581.001.0001"},{"key":"atypb29","unstructured":"M. Grant, S. Boyd, and Y. Ye,\n                      CVX: MATLAB Software for Disciplined Convex Programming\n                      , http:\/\/cvxr.com\/cvx\/. Accessed January 22, 2015."},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1137\/0806020"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1137\/0221008"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1137\/0907079"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1016\/j.aml.2004.07.034"},{"key":"atypb34","first-page":"629","volume":"4","author":"B. K.","year":"1987","journal-title":"J. Opt. Soc. Am. A"},{"key":"atypb35","unstructured":"S. D. Howard, D. Cochran, W. Moran, and F. R. Cohen,\n                      Estimation and Registration on Graphs\n                      , preprint, arXiv:1010.2983, 2010."},{"key":"atypb36","first-page":"177","author":"Huang Q.-X.","year":"2013","journal-title":"New York"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-012-9129-5"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1137\/080731359"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.2307\/2690338"},{"key":"atypb40","first-page":"187","author":"Krishnan S.","year":"2005","journal-title":"New York"},{"key":"atypb41","doi-asserted-by":"crossref","unstructured":"G. Lerman, M. McCoy, J. A. Tropp, and T. Zhang,\n                      Robust Computation of Linear Models, or How to Find a Needle in a Haystack\n                      , preprint, arXiv:1202.4044, 2012.","DOI":"10.21236\/ADA563093"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479893256359"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1137\/0801013"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1093\/qmath\/11.1.50"},{"key":"atypb45","first-page":"22","author":"Mitra N. J.","year":"2004","journal-title":"New York"},{"key":"atypb46","first-page":"71","author":"Naor A.","year":"2013","journal-title":"New York"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0033-0"},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1080\/10556789808805690"},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-006-5167-2"},{"key":"atypb50","doi-asserted-by":"crossref","unstructured":"G. Ranjan, Z.L. Zhang, and D. Boley,\n                      Incremental Computation of Pseudo-inverse of Laplacian: Theory and Applications\n                      , preprint, arXiv:1304.2300, 2013.","DOI":"10.1007\/978-3-319-12691-3_54"},{"key":"atypb51","first-page":"145","author":"Rusinkiewicz S.","year":"2001","journal-title":"NJ"},{"key":"atypb52","first-page":"587","author":"Sharp G. C.","year":"2002","journal-title":"Berlin"},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2010.02.001"},{"key":"atypb54","doi-asserted-by":"publisher","DOI":"10.1137\/090750688"},{"key":"atypb55","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-009-0330-5"},{"key":"atypb56","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0040-1"},{"key":"atypb57","first-page":"81","author":"Spielman D. A.","year":"2004","journal-title":"New York"},{"key":"atypb58","doi-asserted-by":"publisher","DOI":"10.1080\/10556789908805762"},{"key":"atypb59","unstructured":"T. Tzeneva,\n                      Global Alignment of Multiple 3-D Scans Using Eigenvector Synchronization\n                      , Senior thesis, Department of Mathematics, Princeton University, Princeton, NJ, 2011."},{"key":"atypb60","doi-asserted-by":"publisher","DOI":"10.1137\/1038003"},{"key":"atypb61","doi-asserted-by":"publisher","DOI":"10.1561\/0400000054"},{"key":"atypb62","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-013-0738-9"},{"key":"atypb63","doi-asserted-by":"publisher","DOI":"10.1093\/imaiai\/iat005"},{"key":"atypb64","first-page":"533","author":"Wen Z.","year":"2012","journal-title":"Berlin"},{"key":"atypb65","doi-asserted-by":"crossref","unstructured":"J. A. Williams and M. Bennamoun,\n                      Simultaneous registration of multiple point sets using orthonormal matrices\n                      , in Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (Istanbul), vol. 4, IEEE Press, Piscataway, NJ, 2000, pp. 2199-2202.","DOI":"10.1109\/ICASSP.2000.859274"},{"key":"atypb66","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00352-3"},{"key":"atypb67","doi-asserted-by":"crossref","unstructured":"H. Wolkowicz, R. Saigal, and L. Vandenberghe, eds.\n                      Handbook of Semidefinite Programming: Theory, Algorithms, and Applications\n                      , Internat. Ser. Oper. Res. Management Sci. 27, Springer, Berlin, 2000.","DOI":"10.1007\/978-1-4615-4381-7"},{"key":"atypb68","doi-asserted-by":"publisher","DOI":"10.1137\/060676829"},{"key":"atypb69","first-page":"35","volume":"6","author":"Zhang L.","year":"2010","journal-title":"ACM Trans. Sensor Networks"},{"key":"atypb70","first-page":"20","volume":"27","author":"Zhi-Quan L.","year":"2010","journal-title":"IEEE Signal Process. Mag."},{"key":"atypb71","doi-asserted-by":"publisher","DOI":"10.1137\/090772009"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/130935458","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:37:12Z","timestamp":1787337432000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/130935458"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":71,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/130935458"],"URL":"https:\/\/doi.org\/10.1137\/130935458","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}