.png){kind=icon}
.png){kind=icon}
Return
NON-DEGENERATE RIGID ALIGNMENT IN A PATCH FRAMEWORK
.png){kind=icon}
PRE
AI
DOI：10.1137/23M1593280.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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:
non-degeneracy
rigid alignment
infinitesimal rigidity
local rigidity
affine rigidity
linear convergence
Riemannian gradient descent
quotient manifold
noise stability
Journal
IF:
2.3
Papers:
27
Citations:
1.0W
