{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:23:51Z","timestamp":1787340231078,"version":"build-2736575974"},"reference-count":41,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/100002418","name":"Intel Corporation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100002418","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2217058"],"award-info":[{"award-number":["CCF-2217058"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-2012266"],"award-info":[{"award-number":["DMS-2012266"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100012378","name":"Kavli Institute for Brain and Mind, University of California, San Diego","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100012378","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2026,3,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>Given a set of overlapping local views (patches) of a dataset, we consider the problem of finding a rigid alignment of the views that minimizes a 2-norm based alignment error. In general, the views are noisy and a perfect alignment may not exist. In this work, we characterize the non-degeneracy of an alignment in the noisy setting based on the kernel and positivity of a certain matrix. This leads to a polynomial time algorithm for testing the non-degeneracy of a given alignment. Subsequently, we focus on Riemannian gradient descent for minimizing the alignment error, providing a sufficient condition on an alignment for the algorithm to converge (locally) linearly to it. Additionally, we provide an exact recovery and noise stability analysis of the algorithm. In the case of noiseless views, a perfect alignment exists, resulting in a realization of the points that respects the geometry of the views. Under a mild condition on the views, we show that a non-degenerate perfect alignment characterizes the infinitesimally rigidity of a realization and thus the local rigidity of a generic realization. By specializing the non-degeneracy conditions to the noiseless case, we derive necessary and sufficient conditions on the overlapping structure of the views for a perfect alignment to be non-degenerate and,\u00a0equivalently, for the resulting realization to be infinitesimally rigid.<\/jats:p>","DOI":"10.1137\/23m1593280","type":"journal-article","created":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T07:28:15Z","timestamp":1773818895000},"page":"434-465","source":"Crossref","is-referenced-by-count":0,"title":["Non-degenerate Rigid Alignment in a Patch Framework"],"prefix":"10.1137","volume":"36","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0306-913X","authenticated-orcid":true,"given":"Dhruv","family":"Kohli","sequence":"first","affiliation":[{"name":"Department of Mathematics, UC San Diego, La Jolla, CA 92093 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5287-3626","authenticated-orcid":true,"given":"Gal","family":"Mishne","sequence":"additional","affiliation":[{"name":"Halicio\u011flu Data Science Institute, UC San Diego, La Jolla, CA 92093 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alexander","family":"Cloninger","sequence":"additional","affiliation":[{"name":"Department of Mathematics, UC San Diego, La Jolla, CA 92093 USA."},{"name":"Halicio\u011flu Data Science Institute, UC San Diego, La Jolla, CA 92093 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2026,3,18]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1515\/9781400830244"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1978-0511410-9"},{"key":"ref3","doi-asserted-by":"crossref","unstructured":"A. S. Bandeira, M. Charikar, A. Singer, and A. Zhu, Multireference alignment using semidefinite programming, in Proceedings of the 5th Conference on Innovations in Theoretical Computer Science, 2014, pp. 459\u2013470.","DOI":"10.1145\/2554797.2554839"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1162\/089976603321780317"},{"key":"ref5","volume-title":"Perturbation Analysis of Optimization Problems","author":"Bonnans J. F.","year":"2013"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1137\/130935458"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1006\/jmbi.2000.3693"},{"key":"ref8","unstructured":"R. L. Cohen, K. Iga, and P. Norbury, Topics in Morse theory, Lecture notes, 2006, http:\/\/math.stanford.edu\/\u223cralph\/morsecourse\/biglectures.pdf."},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1016\/S0924-2716(02)00043-6"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1145\/2240092.2240093"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1093\/imaiai\/ias002"},{"key":"ref12","unstructured":"S. Dong, B. Gao, W. Huang, and K. A. Gallivan, On the Analysis of Optimization with Fixed-Rank Matrices: A Quotient Geometric View, preprint, arXiv:2203.06765, 2022."},{"key":"ref13","first-page":"351","volume-title":"Distance Geometry: Theory, Methods, and Applications","author":"Fang X.","year":"2012"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-70873-7"},{"key":"ref15","unstructured":"S. J. Gortler, C. Gotsman, L. Liu, and D. P. Thurston, On Affine Rigidity, preprint, arXiv:1011.5553, 2010."},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1137\/0221008"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1016\/j.aml.2004.07.034"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-018-0981-3"},{"key":"ref19","first-page":"1","volume":"22","author":"Kohli D.","year":"2021","journal-title":"J. Mach. Learn. Res."},{"key":"ref20","first-page":"341","volume":"15","author":"Kovanic P.","year":"1979","journal-title":"Kybernetika"},{"key":"ref21","unstructured":"S. Krishnan, P. Y. Lee, J. B. Moore, S. Venkatasubramanian, et\u00a0al., Global registration of multiple 3d point sets via optimization-on-a-manifold., in Symposium on Geometry Processing, 2005, pp. 187\u2013196."},{"key":"ref22","volume-title":"Geometric Constraint Systems with Applications in CAD and Biology","author":"Lee A.","year":"2008"},{"key":"ref23","unstructured":"S. Ling, Generalized Power Method for Generalized Orthogonal Procrustes Problem:\u00a0Global Convergence and Optimization Landscape Analysis, preprint, arXiv:2106.15493, 2021."},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2023.04.008"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-018-1285-1"},{"key":"ref26","unstructured":"Y. Luo and N. G. Trillos, Nonconvex Matrix Factorization Is Geodesically Convex: Global Landscape Analysis for Fixed-Rank Matrix Optimization from a Riemannian Perspective, preprint, arXiv:2209.15130, 2022."},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1137\/140957822"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-009-9231-x"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2004.1354683"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.49"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1561\/0600000009"},{"key":"ref32","volume-title":"Handbook of Discrete and Computational Geometry","author":"Toth C. D.","year":"2017"},{"key":"ref33","volume-title":"Convex Functions and Optimization Methods on Riemannian Manifolds","volume":"297","author":"Udriste C.","year":"2013"},{"key":"ref34","series-title":"Johns Hopkins Stud. Math. Sci.","volume-title":"Matrix Computations","author":"Van Loan C. F.","year":"1996"},{"key":"ref35","doi-asserted-by":"crossref","unstructured":"J. A. Williams and M. Bennamoun, Simultaneous registration of multiple point sets using orthonormal matrices, in Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing, Vol. 4, 2000, pp. 2199\u20132202.","DOI":"10.1109\/ICASSP.2000.859274"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1137\/060676829"},{"key":"ref37","first-page":"35","volume":"6","author":"Zhang L.","year":"2010","journal-title":"ACM Trans. Sensor Netw. (TOSN)"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827502419154"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1137\/140967994"},{"key":"ref40","unstructured":"L. Zhu, C. Li, and A. M.C. So, Rotation Group Synchronization Via Quotient Manifold, preprint, arXiv:2306.12730, 2023."},{"key":"ref41","doi-asserted-by":"crossref","unstructured":"Z. Zhu, A. M.C. So, and Y. Ye, Universal rigidity: Towards accurate and efficient localization of wireless networks, in Proceedings of IEEE INFOCOM, 2010, pp. 1\u20139.","DOI":"10.1109\/INFCOM.2010.5462057"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/23M1593280","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:26:07Z","timestamp":1787336767000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/23M1593280"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,18]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3,31]]}},"alternative-id":["10.1137\/23M1593280"],"URL":"https:\/\/doi.org\/10.1137\/23m1593280","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,18]]}}}