A novel low-rank matrix completion approach to estimate missing entries in Euclidean distance matrix

DOI10.1007/S40314-018-0613-7zbMATH Open1400.15027arXiv1711.06182OpenAlexW2964317840WikidataQ62562094 ScholiaQ62562094MaRDI QIDQ1993487FDOQ1993487

Authors: Nilson J. M. Moreira, Cristiano Torezzan, Leonardo Tomazeli Duarte, Carlile Lavor 

Publication date: 5 November 2018

Published in: Computational and Applied Mathematics (Search for Journal in Brave)

Abstract: A Euclidean Distance Matrix (EDM) is a table of distance-square between points on a k- dimensional Euclidean space, with applications in many fields (e.g. engineering, geodesy, economics, genetics, biochemistry, psychology). A problem that often arises is the absence (or uncertainty) of some EDM elements. In many situations, only a subset of all pairwise distances is available and it is desired to have some procedure to estimate the missing distances. In this paper, we address the problem of missing data in EDM through low-rank matrix completion techniques. We exploit the fact that the rank of a EDM is at most k+2 and does not depend on the number of points, which is, in general, much bigger then k. We use a Singular Value Decomposition approach that considers the rank of the matrix to be completed and computes, in each iteration, a parameter that controls the convergence of the method. After performing a number of computational experiments, we could observe that our proposal was able to recover, with high precision, random EDMs with more than one thousand points and up to 98 percent of missing data in few minutes. Additionally, our method required a smaller number of iterations when compared to other competitive state-of-art technique.

Full work available at URL: https://arxiv.org/abs/1711.06182

Recommendations

• Euclidean distance matrix completion problems
• Approximate and exact completion problems for Euclidean distance matrices using semidefinite programming
• Some properties for the Euclidean distance matrix and positive semidefinite matrix completion problems
• Euclidean Distance Matrix Completion and Point Configurations from the Minimal Spanning Tree
• Solving Euclidean distance matrix completion problems via semidefinite progrmming

zbMATH Keywords

matrix completionEuclidean distance matrix

Mathematics Subject Classification ID

Matrix completion problems (15A83) General theory of distance geometry (51K05)

Cites Work

• Spectral regularization algorithms for learning large incomplete matrices
• A Singular Value Thresholding Algorithm for Matrix Completion
• Title not available (Why is that?)
• Exact matrix completion via convex optimization
• Semidefinite Programming
• Euclidean distance geometry and applications
• Assigned and unassigned distance geometry: applications to biological molecules and nanostructures
• Affine matrix rank minimization problem via non-convex fraction function penalty

Cited In (6)

• On the estimation of unknown distances for a class of Euclidean distance matrix completion problems with interval data
• Recent results on assigned and unassigned distance geometry with applications to protein molecules and nanostructures
• A two-phase rank-based algorithm for low-rank matrix completion
• Rank estimation in missing data matrix problems
• Unassigned distance geometry and molecular conformation problems
• Cloud-based ERP system selection based on extended probabilistic linguistic MULTIMOORA method and Choquet integral operator

Uses Software

• softImpute

This page was built for publication: A novel low-rank matrix completion approach to estimate missing entries in Euclidean distance matrix

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1993487)