Reconstructing Point Sets from Distance Distributions
share
We study the problem of reconstructing the locations u_i of a set of points from their unlabeled pairwise distance measurements. Instead of recovering u_i directly, we represent the point-set by its indicator vector x∈{0,1}^M and search for an x that reproduces the observed distance distribution. We show that the integer constraint on x can be further relaxed, and recast the unassigned distance geometry problem into a constrained nonconvex optimization problem. We propose a projected gradient descent algorithm to solve it, and derive conditions under which the proposed method converges to a global optimizer x^* in both noiseless and noisy cases. In addition, we propose several effective initialization strategies that empirically perform well. Compared to conventional greedy build-up approaches that become inoperable in the face of measurement noise, the proposed distance distribution matching approach jointly reconstructs all the sample points and is robust to noise. We substantiate these claims with a number of numerical experiments.
READ FULL TEXT