A Fast and Convergent Algorithm for Unassigned Distance Geometry Problems

2025/02/04 by Fan, Jun, Shan, Xiaoya, Xiu, Xianchao
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2502.02280

Abstract

In this paper, we propose a fast and convergent algorithm to solve unassigned distance geometry problems (uDGP). Technically, we construct a novel quadratic measurement model by leveraging ℓ₀-norm instead of ℓ₁-norm in the literature. To solve the nonconvex model, we establish its optimality conditions and develop a fast iterative hard thresholding (IHT) algorithm. Theoretically, we rigorously prove that the whole generated sequence converges to the L-stationary point with the help of the Kurdyka-Lojasiewicz (KL) property. Numerical studies on the turnpike and beltway problems validate its superiority over existing ℓ₁-norm-based method.

Related

• Nonlinear Mapping and Distance Geometry
• Riemannian Optimization for Non-convex Euclidean Distance Geometry with Global Recovery Guarantees
• An efficient algorithm for the ℓ_p norm based metric nearness problem
• Provable Non-Convex Euclidean Distance Matrix Completion: Geometry, Reconstruction, and Robustness
• Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimization