Low-rank optimization for distance matrix completion

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.

In Proceedings of the 50th IEEE Conference on Decision and Control and European Control Conference, 2011

References in corpus (4)

• Low-rank optimization for semidefinite convex problems
• Low-rank optimization for distance matrix completion
• Regression on fixed-rank positive semidefinite matrices: a Riemannian approach
• A geometric Newton method for Oja's vector field

Cited by in corpus (17)

• Manopt, a Matlab toolbox for optimization on manifolds
• Low-rank optimization for distance matrix completion
• Riemannian preconditioning
• Dropping Convexity for Faster Semi-definite Optimization
• Radio Interferometric Calibration Using a Riemannian Manifold
• Network Topology Mapping from Partial Virtual Coordinates and Graph Geodesics
• Efficient Rigid Body Localization based on Euclidean Distance Matrix Completion for AGV Positioning under Harsh Environment
• Quartic First-Order Methods for Low-Rank Minimization
• Sensor Network Localization via Riemannian Conjugate Gradient and Rank Reduction: An Extended Version
• Low-rank optimization with trace norm penalty
• 3D genome reconstruction from partially phased Hi-C data
• Riemannian Optimization for Distance-Geometric Inverse Kinematics
• Noisy Euclidean distance realization: robust facial reduction and the Pareto frontier
• Two Newton methods on the manifold of fixed-rank matrices endowed with Riemannian quotient geometries
• Matrix Completion Based Localization in the Internet of Things Network
• Inverse Kinematics as Low-Rank Euclidean Distance Matrix Completion
• On Geometric Connections of Embedded and Quotient Geometries in Riemannian Fixed-rank Matrix Optimization