Distance matrix completion

Low-rank optimization for distance matrix completion

Authors

B. Mishra, G. Meyer, and R. Sepulchre

Abstract

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.

Downloads

• Status: Proceedings of the 50th IEEE Conference on Decision and Control, 2011
• Paper: [Publisher’s pdf] [arXiv:1304.6663]. In the equation (11), the factor “2” should be replaced by “4”.
• Matlab code: distcompletion_25jan_2013.zip
  • Updated low_rank_dist_completion_MMS.m on 30 August 2016. Corrected some logic flaws while plotting and storing rank information. A typo was also corrected.
  • low_rank_dist_completion_MMS.m is a generic wrapper function to be used with the Manopt toolbox (added July 2015). It leverages Manopt’s algorithms.
  • Current version: Jan 25, 2013: Minor updating + Helix example added.
  • Entry: April 4, 2011.

Example