0

While working on this topic, I came across the following matrix $$D=\begin{pmatrix} 0&1&1&2\\ 1&0&\sqrt 2&1\\ 1&\sqrt 2&0&1\\ 2&1&1&0 \end{pmatrix}$$ This matrix comes from the following: $$D_{ij}=D_{ji}=\sqrt{K_{ii}+K_{jj}-2|K_{ij}|},$$ where $K=XX^\top$ and $X=\begin{pmatrix}-1&-1\\1&0\\0&1\\1&-1\end{pmatrix}$.

Now, my question is: why $D$ is not a distance matrix ? It's obviously not a distance matrix, as its square has more than one positive eigenvalue. But at the same time:

  1. It is symmetric
  2. $D_{ij}=0 \iff i=j$
  3. The triangle inequality is obviously satisfied, since $D_{ij}\le 2 \le D_{ik}+D_{kj}$.

So, what's going on here ?

Community
  • 1
davcha
  • 1,745
  • Why can't it have more than 1 positive eigenvalue? – mathreadler Jul 10 '15 at 09:54
  • And what is diag supposed to mean? If working on a matrix it produces a vector with diagonal elements in it, no? You can't add a vector to a matrix. – mathreadler Jul 10 '15 at 09:59
  • Diag is a shortcut used in Matlab. Diag(K) is the column vector with entries equal to the diagonal of K. Sure you can't add vectors and matrix, I should have written $D_{ij} = K_{ii}^2+K_{jj}^2...$ – davcha Jul 10 '15 at 10:04
  • Also, distance matrices always have exactly one positive eigenvalue. If not, it means that $K$ is not positive semi definite, thus does not describe a metric. – davcha Jul 10 '15 at 10:06
  • What is $K$...? – mathreadler Jul 10 '15 at 10:08
  • $K=XX^\top$, the kernel matrix – davcha Jul 10 '15 at 10:24
  • Wait, $K_{ii}^2$? Then you are missing a square. If not $K^2 = XX^T$ – mathreadler Jul 10 '15 at 10:42
  • Ooooh... I made a mistake in the comments while answering on my phone. I edit the post for more clarity. – davcha Jul 10 '15 at 10:53
  • But now the absolute value on the last term disappeared, is it supposed to be there? – mathreadler Jul 10 '15 at 11:01
  • Sorry. I added it back. In fact, when you compute a distance using this kernel trick, there is no absolute value, of course. But the previous topic asked if $K\succeq 0 \implies |K|\succeq 0$. If the answer is yes, then $|K|$ should also be the kernel of some space. That's why you have the absoluve value here. – davcha Jul 10 '15 at 11:05

1 Answers1

2

The kernel is only positive semi-definite if the metric is Euclidean. And indeed, the distances in your matrix are not achievable in that case. But consider the following points in $\mathbb{R}^2$, equipped with the metric obtained from the maximum norm, $d(x,y) = max(|x_1-y_1|,|x_2-y_2|)$:

  • $p_1=(0,0)$,
  • $p_2=(1,\frac{\sqrt{2}}{2})$,
  • $p_3=(1,-\frac{\sqrt{2}}{2})$,
  • $p_4=(2,0)$.

These do achieve $d(p_i,p_j) = D_{ij}$.

Klaus Draeger
  • 874
  • So, basically, the data points are on a manifold. Is it possible to "unfold" this manifold ? – davcha Jul 10 '15 at 12:31
  • I'm not sure what you mean by "unfold". – Klaus Draeger Jul 10 '15 at 12:35
  • I know "unfold" is very vague. But, for example, you can obtain an Euclidean representation of a graph, that gives you the commute-time distance between nodes of this graph. In the example given by the matrix $D$, I don't really know what "unfold" would mean. I think I'm trying to figure what is the interpretation of the negative eigenvalues of the kernel associated with $D$. – davcha Jul 10 '15 at 12:39
  • Interesting question, but I'm not sure what can be done in this direction, sorry. – Klaus Draeger Jul 10 '15 at 12:44
  • Hi davcha, do you mean like to draw a map? To parametrize a curve or surface? – mathreadler Jul 11 '15 at 19:14