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

DOI10.1007/S40314-018-0613-7MaRDI QIDQ1993487zbMATH OpenOpenAlexWikidataFDO

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)

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

zbMATH Keywords

matrix completionEuclidean distance matrix

Mathematics Subject Classification ID

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

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.

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

Cites work

• scientific article; zbMATH DE number 4213315 (Why is no real title available?)
• A Singular Value Thresholding Algorithm for Matrix Completion
• Affine matrix rank minimization problem via non-convex fraction function penalty
• Assigned and unassigned distance geometry: applications to biological molecules and nanostructures
• Euclidean distance geometry and applications
• Exact matrix completion via convex optimization
• Semidefinite Programming
• Spectral regularization algorithms for learning large incomplete matrices

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

Describes a project that uses

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)