2018/04/30 by Shuai Huang, Ivan Dokmanić
Computer Science · Engineering · Mathematics · Medicine · #Advanced Vision and Imaging #Algorithm #Applied mathematics #Artificial intelligence #Computer science #Descent direction #Discretization #Distribution (mathematics) #Domain (mathematical analysis) #Gradient descent #Line search #Mathematical analysis #Mathematical optimization #Mathematics #Medical Imaging Techniques and Applications #Robotics and Sensor-Based Localization #cs.DS #cs.IT #cs.LG #math.IT
paper · pdf · doi:10.1109/tsp.2021.3063458
published as IEEE Transactions on Signal Processing, Vol. 69, 1181-1127, Mar. 2021
openalex publication_date 2021/01/01 · arxiv created 2021/04/26 · arxiv updated 2021/04/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
We address the problem of reconstructing a set of points on a line or a loop from their unassigned noisy pairwise distances. When the points lie on a line, the problem is known as the turnpike; when they are on a loop, it is known as the beltway. We approximate the problem by discretizing the domain and representing theNpoints via anN-hot encoding, which is a density supported on the discretized domain. We show how the distance distribution is then simply a collection of quadratic functionals of this density and propose to recover the point locations so that the estimated distance distribution matches the measured distance distribution. This can be cast as a constrained nonconvex optimization problem which we solve using projected gradient descent with a suitable spectral initializer. We derive conditions under which the proposed distance distribution matching approach locally converges to a global optimizer at a linear rate. Compared to the conventional backtracking approach, our method jointly reconstructs all the point locations and is robust to noise in the measurements. We substantiate these claims with state-of-the-art performance across a number of numerical experiments. Our method is the first practical approach to solve the large-scale noisy beltway problem where the points lie on a loop.