17
$\begingroup$

I asked this question in Math Stack Exchange earlier here: https://math.stackexchange.com/questions/1199380/what-is-the-intuition-behind-how-can-we-interpret-the-eigenvalues-and-eigenvec and since I felt this was a better forum for the question, I have posted it here.

Given a set of points $x_1,x_2,...,x_m$ in the euclidean space $R^n$, we can form a $m$ x $m$ Euclidean Distance Matrix $D$ where $D_{ij}=||x_i−x_j||_2$.

We know a little bit about these matrices like :

  1. It is symmetric.
  2. Its Trace=0.
  3. It has (at most) n+2 non-zero eigenvalues;
  4. It has exactly n+2 non-zero eigenvalues whenever m>n;

Source : https://math.stackexchange.com/questions/1198895/relationship-between-eigenvalues-of-two-related-euclidean-distance-matrices

What is the intuition behind the eigenvalues and eigenvectors of such matrices ?

  1. In the case of a covariance matrix formed from data points, we can say that the eigenvectors are the directions in the the spread of data is maximum and these are called as principal components.

  2. In the case of adjacency matrices of graphs also, there seems to be an interpretation for the eigenvectors as given here : http://daylateanddollarshort.com/math/pdfs/spectral.pdf

Is there a similar interpretation for these Euclidean Distance Matrices (EDM's)?

Thank You.

Even partial answers, ideas and references are welcome.

$\endgroup$
1

1 Answer 1

11
$\begingroup$

If $D_{ij}=|v_i-v_j|^2$ encodes the squared distances between a set of vectors $\{v_1,v_2,\ldots v_n\}$ in $d$-dimensional Euclidean space, with $V=\sum_{i=1}^{n}v_i=0$, then [*] $G=-\tfrac{1}{2}JD J$ with centering matrix $J_{kl}=\delta_{kl}-1/n$ gives the inner-product matrix $G_{ij}=v_i\cdot v_j$, called the Gram matrix. The positive eigenvalues of $G$ are those of the covariance matrix, which have the usual interpretation of principal component analysis.


[*] check

$$-2G_{ij}=(JDJ)_{ij}=D_{ij}+n^{-2}\sum_{k,l=1}^n D_{kl}-n^{-1}\sum_{k=1}^n (D_{ik}+D_{kj})$$

substitute $D_{ij}=v_i^T v_i+v_j^T v_j-2v_i^T v_j$,

$$-2G_{ij}=v_i^T v_i+v_j^T v_j-2v_i^T v_j+n^{-2}\left(2n\sum_{k}v_k^T v_k-2V^T V\right)$$ $$\qquad\qquad -n^{-1}\left(nv_i^T v_i+nv_j^T v_j+2\sum_k v_k^T v_k-2V^T v_j-2v_i^TV\right)$$ $$\qquad =-2v_i^T v_j-2n^{-2}V^T V+2n^{-1}(V^T v_j+v_i^T V)$$

under the assumption $V=\sum_{i=1}^{n}v_i=0$, this gives the desired result $G_{ij}=v_i^T v_j$.

$\endgroup$
1
  • 1
    $\begingroup$ In this case PCA is functionally equivalent to metric multidimensional scaling. The latter, however, works directly on the distance matrix. $\endgroup$ Mar 25, 2015 at 20:28

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.