2
$\begingroup$

I am reading this note.

http://fourier.eng.hmc.edu/e176/lectures/MultidimensionScaling.pdf

P.17

it has a Distance matrix,

D = array([[0, 1,1,1], [1, 0, 1,1], [1, 1,0,1], [1,1,1,0]])

then it mentioned "leading to the gram matrix B(4×4) with eigenvalues (.5, .5, .5, 0)."

I would like to ask how get the gram matrix from D?

I tried to appl G = I -D/2(?).

(from here: https://math.stackexchange.com/questions/2240429/pairwise-distance-matrix)

But when i get the PCA, i got [ 0.062 0.062 0.062 0. ]

from sklearn.decomposition import PCA
G = 1-D/2
pca = PCA()
pca.fit(G)
print(pca.explained_variance_)

must be something wrong.

$\endgroup$

1 Answer 1

3
$\begingroup$

My understanding of the Gram matrix, is that it comes from a product $X^{T}X$ where $X$ is a $k\times n$ matrix of coordinates (assuming your points lie in k dimensions). In your case $n$ would be 4 since the distance matrix is $4\times 4$ (pairwise distances between four points). In order to find a/the Gram matrix, you first need to find the location of the 4 points (in your case $k=3$ since you have a tetrahedron) so that their pairwise distances give you the distance matrix you have.

Edit: Since this is a tetrahedron with all unit distances, you can fairly easily compute locations of those vertices by hand. Otherwise, if you don't want to (or can't) do it by hand, then use Multidimensional Scaling. Note: PCA doesn't do this.

Edit: To reproduce the eigenvalues demonstrated (computationally) you can do the following:

from sklearn.manifold import MDS
import numpy as np

# Given distance matrix
D = np.array( [ [0, 1, 1, 1], [1, 0, 1, 1], [1, 1, 0, 1], [1, 1, 1, 0]] )

# n_components = 3 says your are finding points in 3 dimensions
# dissimilarity = 'precomputed' alerts the algorithm that you are handing it a distance matrix
embedding = MDS(n_components=3, dissimilarity='precomputed')

# Fitting the distance matrix give you a list of points realizing the distances (note that this process is random and approximate).
Xt = embedding.fit_transform( D ) #Xt is a 4x3 matrix (so it's X^T)

# Get the transpose of that value (for computing X^T X)
X  = np.transpose( Xt )

# Compute the Gram Matrix
Gram_Matrix = np.matmul( Xt, X )

# Check the eigenvalues
print( np.linalg.eigvalsh( Gram_Matrix ) )
$\endgroup$
12
  • $\begingroup$ thx for answering, but i am confused, do you know how to get eigenvalues (.5, .5, .5, 0). based on the distance matrix on P17 of this slide? fourier.eng.hmc.edu/e176/lectures/MultidimensionScaling.pdf $\endgroup$ Oct 14, 2020 at 14:41
  • $\begingroup$ p.s. i know i can use sklearn.to do so, but i would like to know how to do the calculation, so i insisted to ask about P17 of the slide, many thx. $\endgroup$ Oct 14, 2020 at 14:43
  • $\begingroup$ Doing MDS by hand is terrible; but lucky for you, the points come from a tetrahedron (looking at the picture on your slide). So what you need to do is compute the x,y,z location of each of the 4 corners of the tetrahedron. Put those coordinates into a $3\times 4$ matrix $X$, then compute $X^T X$. $\endgroup$
    – TravisJ
    Oct 14, 2020 at 14:54
  • $\begingroup$ Edited my answer slightly. I'll leave it to you to determine the exact locations of those points... if your question is "how do I find the location of vertices of a unit tetrahedron?" then that's probably a separate question. $\endgroup$
    – TravisJ
    Oct 14, 2020 at 14:59
  • $\begingroup$ many thx for help, my refined question is, what is the step-by-step to get eigenvalues (.5, .5, .5, 0)? why the slide showed (.5, .5, .5, 0)? $\endgroup$ Oct 14, 2020 at 15:25

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.