  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 (SDR), inspired by SDRs for static EDMs. Similarly to
the static case, the SDR 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.
