# Constructing the origin position by transforming distance information

Suppose a set of $n$ points, $n\in M$, is given in some $d-$dimensional space, $X\in\mathbb{R}^{n\times d}$. Among these $n$ points, some $k\in K$ are selected, so $k<n$, and the distances from these $k$ points to a all other points are calculated and stored in $D\in\mathbb{R}^{n\times k}$.

Now, given only this distance information, $D$, following the cosine law one is able to construct the matrix of inner-products between all points from $M$ and points from $K$, with respect to an origin $s\in K$, $$x_ik_j=d_{si}d_{sj}\cdot cos(\alpha)= -\frac{1}{2}\left(d_{ij}^2 - d_{si}^2 - d_{sj}^2\right),~~~~~~i\in\{1, \dots, n\}, ~~j\in\{\ 1, \dots, k\} \tag 1.$$ I'm interested in the restrictions of the origin positions in this case when only distances are supplied. With the above approach, for instance, I could not specify some point that is not in $K$ to be the origin, since not all points would have distance information to it. I think that I could specify a linear combination of points from $K$ to be the origin (or?)

In case only coordinates are given, then, by a simple shift, I could specify an arbitrary origin position. But, with the distance information to only a subset of points, I suppose the set of origin choices is more restricted. Is it, and if so, it what way?

To simplify the matters: given the above distance info, what would be the restrictions on the choice of origin? Am I right to state that not all points could be chosen as the origin, because of insufficient distance information?

If you know the Gram matrix $G_{ik}=(x_i-x_0,x_k-x_0)$ of inner products with respect to the origin $x_0$, you can get the shifted Gram matrix $G_{ik}'=(x_i-x,x_k-x)$ with respect to any affine combination $x=x_0+\sum a_j (x_j-x_0)$ by expanding the inner products using $x_i-x=x_i-x_0-\sum a_j (x_j-x_0)$ and expressing the result in terms of the $G_{ik}$.
If only the part $G_{K:}$ of $G$ is known and the points indexed by $K$ span togeher with $x_0$ the full space then one can reconstruct the whole of $G$. Indeed, under these assumptions, $G_{KK}$ has the same rank $d$ as $G_{K:}$, and they span the same column space. The full Gram matrix is now $G=G_{K:}^TG_{KK}^+G_{K:}$, with $+$ denoting the pseudo inverse. (Numerically, one must think about ho2w to get this numerically stable.)
• I want to construct the Gram matrix of inner-products wrt origin by considering distances to a certain node set only. So, no Gram matrix is known in advance. For instance, how would the the calculation from 1) above read in case I want the origin to be some point $l\notin K$, $l\in M$? – usero Apr 16 '12 at 20:16