Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

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?

share|improve this question

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.

share|improve this answer
    
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). –  usero Oct 10 '12 at 9:39
    
@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. –  Arnold Neumaier Oct 10 '12 at 9:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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