Suppose a matrix $D\in\mathbb{R}^{n\times n}$ of Euclidean distances between $n$ points is given. To obtain a Gram matrix (matrix of inner-products of points that give rise to distances in $D$), one performs $$G=-1/2\cdot PD^{(2)}P^T,$$ where $D^{(2)}$ contains squared entries of $D$, and $P=(I_n-1_nw^T)$, $w^T1_n=1$. It is known (see http://www.sciencedirect.com/science/article/pii/0024379585901879) that in case $w^T1_n=1$, the rank of all Gram matrices is identical, and corresponds to true dimensionality of the data.

However, I wonder what happens when $w^T1_n\neq 1$. Could there be a choice of two different $P$ for which the ranks of associated $G$ are different?

also, why is the constraint $w^T1_n=1$ imposed?


1 Answer 1


The only formulas that give the correct Gram matrix is the one derived from the relation $d_{ik}^2=g_{ii}-2g_{ik}+g_{kk}$. The simplest version declares a point (wlog with index $0$) to be the zero point; thus $g_{0k}=0$ for all $i$, which gives $g_{kk}=d_{i0}^2$ and then $g_{ik}=(g_{ii}-d_{ik}^2+g_{kk})/2$.

Using this you can probably answer your questions by yourself.

  • $\begingroup$ Such solution would correspond to $w$ (in the formula above) being a column of identity matrix. However, Gram matrix could be constructed with any $w$, $w^T1_n=1$, but the reconstruction would place the origin at different location (linear combination of positions of other points). Still, I wonder what happens if $w^T1_n\neq 1$; could it be that the rank of such obtain Gram matrix is different than from those obtained with a point-origin (as you described). $\endgroup$
    – usero
    Oct 10, 2012 at 9:39
  • $\begingroup$ @usero: Why should it be a Gram matrix at all when $w^T1\ne 1$? You can test your ideas easily by playing with two or three points only. $\endgroup$ Oct 10, 2012 at 9:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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