Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
In this paper, we propose kinetic Euclidean distance matrices (KEDMs) a new algebraic tool for localization of moving points from spatio temporal distance measurements. KEDMs are inspired by the well-known Euclidean distance matrices (EDM) which model static points. When objects move, trajectory models may enable better localization from fewer samples by trading off samples in space for samples in time. We develop the theory for polynomial trajectory models used in tracking and simultaneous localization and mapping. Concretely, we derive a semidefinite relaxation for KEDMs inspired by similar algorithms for the usual EDMs, and propose a new spectral factorization algorithm adapted to trajectory reconstruction. Numerical experiments show that KEDMs and the new semidefinite relaxation accurately reconstruct trajectories from incomplete, noisy distance observations, scattered over multiple time instants. In particular, they show that temporal oversampling can considerably reduce the required number of measured distances at any given time.
Michael Christoph Gastpar, Sung Hoon Lim, Adriano Pastore, Chen Feng