A Nyström method with missing distances
Samuel Lichtenberg Abiy Tasissa
We study the problem of determining the configuration of $n$ points, referred
to as mobile nodes, by utilizing pairwise distances to $m$ fixed points known
as anchor nodes. In the standard setting, we have information about the
distances between anchors (anchor-anchor) and between anchors and mobile nodes
(anchor-mobile), but the distances between mobile nodes (mobile-mobile) are not
known. For this setup, the Nystr\"om method is a viable technique for
estimating the positions of the mobile nodes. This study focuses on the setting
where the anchor-mobile block of the distance matrix contains only partial
distance information. First, we establish a relationship between the columns of
the anchor-mobile block in the distance matrix and the columns of the
corresponding block in the Gram matrix via a graph Laplacian. Exploiting this
connection, we introduce a novel sampling model that frames the position
estimation problem as low-rank recovery of an inner product matrix, given a
subset of its expansion coefficients in a special non-orthogonal basis. This
basis and its dual basis--the central elements of our model--are explicitly
derived. Our analysis is grounded in a specific centering of the points that is
unique to the Nystr\"om method. With this in mind, we extend previous work in
Euclidean distance geometry by providing a general dual basis approach for
points centered anywhere.