4
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

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.)

Now the above recipe applies.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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$? $\endgroup$
    – usero
    Commented Apr 16, 2012 at 20:16
  • $\begingroup$ see my edited answer. $\endgroup$
    – Arnold Neumaier
    Commented Apr 17, 2012 at 10:15
  • $\begingroup$ Thanks. Is the method you propose known in the literature? It reminds me of some known approaches. $\endgroup$
    – usero
    Commented Apr 17, 2012 at 18:59
  • $\begingroup$ I don't know whether my specific recipe is in the literature. But it is an elementary consequence of properties of Gram matrices. (Implementing it in a numerically stable way may be more tricky.) But to go from a distance matrix to a Gram matrix is an old and well-studied result, beginning with work of Schoenberg. $\endgroup$
    – Arnold Neumaier
    Commented Apr 18, 2012 at 12:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.