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,并获得了一个对齐的充分条件,以使算法朝着这个方向线性收敛。

0
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2020年12月14日
GNN 新基准!Long Range Graph Benchmark
图与推荐
0+阅读 · 2022年10月18日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
CVPR2019 | Stereo R-CNN 3D 目标检测
极市平台
27+阅读 · 2019年3月10日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【泡泡一分钟】RoomNet:端到端房屋布局估计
泡泡机器人SLAM
18+阅读 · 2018年12月4日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
1+阅读 · 2011年12月31日
Arxiv
0+阅读 · 2023年5月10日
Arxiv
12+阅读 · 2021年6月29日
VIP会员
相关VIP内容
专知会员服务
50+阅读 · 2020年12月14日
相关资讯
GNN 新基准!Long Range Graph Benchmark
图与推荐
0+阅读 · 2022年10月18日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
CVPR2019 | Stereo R-CNN 3D 目标检测
极市平台
27+阅读 · 2019年3月10日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【泡泡一分钟】RoomNet:端到端房屋布局估计
泡泡机器人SLAM
18+阅读 · 2018年12月4日
相关基金
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
1+阅读 · 2011年12月31日
Top
微信扫码咨询专知VIP会员