Lowrank optimization for distance matrix completion
Authors
B. Mishra, G. Meyer, and R. Sepulchre
Abstract
This paper addresses the problem of lowrank 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 highdimensional problems. We recast the considered problem into an optimization problem over the set of lowrank positive semidefinite matrices and propose two efficient algorithms for lowrank distance matrix completion. In addition, we propose a strategy to determine the dimension of the embedding space. The resulting algorithms scale to highdimensional 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
