用极少距离样本高效还原几何结构，突破现有方法极限
Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimization
- 基于非凸优化与加权最小二乘法，实现低样本下的几何重构
- 在随机采样距离下，理论证明算法可收敛至正确解
- 适合数据稀缺场景，如生物分子构型、传感器网络定位
从点对间的欧几里得距离信息中恢复点集的嵌入或几何构型，是众多机器学习任务中的核心问题。本文针对距离样本极有限的情况，提出基于连续非凸秩最小化的求解方法，并为一种迭代重加权最小二乘（IRLS）变体建立了局部收敛性保证，前提是在随机采样的最小距离集合下。作为技术工具，我们建立了对对称低秩矩阵流形切空间上的受限等距性质（RIP），该性质在随机距离测量下成立，可能对其他非凸方法分析具有独立意义。通过模拟数据和真实数据的数值实验，我们评估了不同算法在数据效率、可扩展性和泛化能力方面的表现，结果表明所提算法能以更少的距离样本准确识别出底层几何结构，优于当前最优方法。
原文摘要 · Abstract (English)
The problem of finding suitable point embedding or geometric configurations given only Euclidean distance information of point pairs arises both as a core task and as a sub-problem in a variety of machine learning applications. In this paper, we aim to solve this problem given a minimal number of distance samples. To this end, we leverage continuous and non-convex rank minimization formulations of the problem and establish a local convergence guarantee for a variant of iteratively reweighted least squares (IRLS), which applies if a minimal random set of observed distances is provided. As a technical tool, we establish a restricted isometry property (RIP) restricted to a tangent space of the manifold of symmetric rank-$r$ matrices given random Euclidean distance measurements, which might be of independent interest for the analysis of other non-convex approaches. Furthermore, we assess data efficiency, scalability and generalizability of different reconstruction algorithms through numerical experiments with simulated data as well as real-world data, demonstrating the proposed algorithm's ability to identify the underlying geometry from fewer distance samples compared to the state-of-the-art.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。