A patch framework consists of a bipartite graph between $n$ points and $m$ local views (patches) and the $d$-dimensional local coordinates of the points due to the views containing them. Given a patch framework, we consider the problem of finding a rigid alignment of the views, identified with an element of the product of $m$ orthogonal groups, $\mathbb{O}(d)^m$, that minimizes the alignment error. In the case when the views are noiseless, a perfect alignment exists, resulting in a realization of the points that respects the geometry of the views. The affine rigidity of such realizations, its connection with the overlapping structure of the views, and its consequences in spectral and semidefinite algorithms has been studied in related work [Zha and Zhang; Chaudhary et al.]. In this work, we characterize the non-degeneracy of a rigid alignment, consequently obtaining a characterization of the local rigidity of a realization, and convergence guarantees on Riemannian gradient descent for aligning the views. Precisely, we characterize the non-degeneracy of an alignment of (possibly noisy) local views based on the kernel and positivity of a certain matrix. Thereafter, we work in the noiseless setting. Under a mild condition on the local views, we show that the non-degeneracy and uniqueness of a perfect alignment, up to the action of $\mathbb{O}(d)$, are equivalent to the local and global rigidity of the resulting realization, respectively. This also yields a characterization of the local rigidity of a realization. We also provide necessary and sufficient conditions on the overlapping structure of the noiseless local views for their realizations to be locally/globally rigid. Finally, we focus on the Riemannian gradient descent for aligning the local views and obtain a sufficient condition on an alignment for the algorithm to converge (locally) linearly to it.
翻译:一个贴片框架包括一个 $n$ 个点和 $m$ 个局部视图(贴片)之间的二分图以及由这些视图包含的点的 $d$ 维局部坐标。给定一个贴片框架,我们考虑找到一个刚性对齐,被视为 $\mathbb{O}(d)^m$ 上的一个元素,以此最小化对齐误差。在视图没有噪声的情况下,存在完美的对齐,从而得到尊重视图几何的点的实现。视图重叠结构的仿射刚度以及它与实现在谱和半正定算法中的连接在相关工作中得到了研究[Zha和Zhang;Chaudhary等]。在这项工作中,我们表征了刚性对齐的非退化性,从而得到了实现的局部坚固性的表征,并获得了在 Riemannian梯度下降中对齐视图的收敛保证。准确地说,我们基于某个矩阵的核和正定性来表征局部视图的(可能是有噪声的)对齐的非退化性。在此之后,我们在没有噪音的情况下进行工作。在局部视图上施加一个温和的条件下,我们表明,在理想的对齐,忽略 $\mathbb{O}(d)$ 的作用下的情况下,完美对齐的非退化性和唯一性等价于实现的局部和全局刚性,分别。这也得到了实现局部坚固性的表征。我们还提供了在没有噪声的局部视图的重叠结构上的必要和充分条件,以使它们的实现成为局部/全局坚固。最后,我们重点关注用于对齐局部视图的 Riemannian gradient descent,并获得了一个对齐的充分条件,以使算法朝着这个方向线性收敛。