Low-rank optimization for distance matrix completion

This paper addresses the problem of low-rank
distance matrix completion. This problem amounts to recover
the missing entries of a distance matrix when the dimension of
the data embedding space is possibly unknown but small compared to the number of considered data points. The focus is on
high-dimensional problems. We recast the considered problem
into an optimization problem over the set of low-rank positive
semidefinite matrices and propose two efficient algorithms for
low-rank distance matrix completion. In addition, we propose
a strategy to determine the dimension of the embedding space.
The resulting algorithms scale to high-dimensional problems
and monotonically converge to a global solution of the problem.
Finally, numerical experiments illustrate the good performance
of the proposed algorithms on benchmarks.