Kinetic Euclidean Distance Matrices

Puoya Tabaghi, Ivan Dokmanić, Martin Vetterli

Research output: Contribution to journalArticlepeer-review


Euclidean distance matrices (EDMs) are a major tool for localization from distances, with applications ranging from protein structure determination to global positioning and manifold learning. They are, however, static objects which serve to localize points from a snapshot of distances. If the objects move, one expects to do better by modeling the motion. In this paper, we introduce Kinetic Euclidean Distance Matrices (KEDMs) - a new kind of time-dependent distance matrices that incorporate motion. The entries of KEDMs become functions of time, the squared time-varying distances. We study two smooth trajectory models - polynomial and bandlimited trajectories - and show that these trajectories can be reconstructed from incomplete, noisy distance observations, scattered over multiple time instants. Our main contribution is a semidefinite relaxation, inspired by similar strategies for static EDMs. Similarly to the static case, the relaxation is followed by a spectral factorization step; however, because spectral factorization of polynomial matrices is more challenging than for constant matrices, we propose a new factorization method that uses anchor measurements. Extensive numerical experiments show that KEDMs and the new semidefinite relaxation accurately reconstruct trajectories from noisy, incomplete distance data and that, in fact, motion improves rather than degrades localization if properly modeled. This makes KEDMs a promising tool for problems in geometry of dynamic points sets.

Original languageEnglish (US)
Article number8930980
Pages (from-to)452-465
Number of pages14
JournalIEEE Transactions on Signal Processing
StatePublished - 2020


  • Euclidean distance matrix
  • localization
  • polynomial matrix factorization
  • positive semidefinite programming
  • spectral factorization
  • trajectory

ASJC Scopus subject areas

  • Signal Processing
  • Electrical and Electronic Engineering


Dive into the research topics of 'Kinetic Euclidean Distance Matrices'. Together they form a unique fingerprint.

Cite this