Non-degenerate Rigid Alignment in a Patch Framework
- 18 March 2026
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 36 (1) , 434-465
Abstract
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, equivalently, for the resulting realization to be infinitesimally rigid.Keywords
All Related Versions
Funding Information
- Intel Corporation
- National Science Foundation (CCF-2217058)
- National Science Foundation (DMS-2012266)
- Kavli Institute for Brain and Mind, University of California, San Diego
This publication has 25 references indexed in Scilit:
- Near-optimal bounds for generalized orthogonal Procrustes problem via generalized power methodApplied and Computational Harmonic Analysis, 2023
- Convergence rate analysis for the higher order power method in best rank one approximations of tensorsNumerische Mathematik, 2018
- Quadratic optimization with orthogonality constraint: explicit Łojasiewicz exponent and linear convergence of retraction-based line-search and stochastic variance-reduced gradient methodsMathematical Programming, 2018
- Eigenvector synchronization, graph rigidity and the molecule problemInformation and Inference: A Journal of the IMA, 2012
- Symmetric Versions of Laman’s TheoremDiscrete & Computational Geometry, 2009
- Matrix Algebra2007
- On the pseudo-inverse of the Laplacian of a bipartite graphApplied Mathematics Letters, 2005
- Use of generalised Procrustes analysis for the photogrammetric block adjustment by independent modelsISPRS Journal of Photogrammetry and Remote Sensing, 2002
- Topological and energetic factors: what determines the structural details of the transition state ensemble and “en-route” intermediates for protein folding? an investigation for small globular proteinsJournal of Molecular Biology, 2000
- The rigidity of graphsTransactions of the American Mathematical Society, 1978