|
How can a distance function be converted to a inner product? |
|
In general it might not be possible, e.g. the space with L1 norm is not an inner product space. You can check using the parallelogram law. |
|
To add to Ben Moran's answer, a nice way of seeing that this is impossible is to write down a norm like sqrt(x dot x), using it to derive distances (d(x,y) = sqrt((x-y) dot (x-y))), and then write down the squares of the distances in terms of the inner products (d^2(x,y) = (x dot x) - 2 (x dot y) + (y dot y)). This will give you have a linear system such that for N points you will have N(N-1)/2 equations (for all pairwise distances) over N + N(N-1)/2 variables (N variables for all possible (x dot x) combinations and N(N-1)/2 variables for all possible (x dot y) combinations). This is ridiculously underconstrained, and one way of seeing this is that no matter how many distance evaluations you perform you will never learn anything about the norm of a point, and for almost any setting of the norms of the points you can find some inner products of the points with each other that explain those distances. Restricting the dimensionality of the space will, of course, make things more constrained, but it's not at all guaranteed to help, as writing the dot products out will give you a hairy quadratic system that is no longer guaranteed to have any solutions at all (in two dimensions you can't have n >= 4 perfectly equidistant points, for example). I did not answer, Ben Moran did. I just made the link click-able using the markdown syntax in his answer :)
(Jan 21 '12 at 15:04)
ogrisel
Fixed this.
(Jan 21 '12 at 18:55)
Alexandre Passos ♦
A special case is if you have made sure that all inputs have l2-norm = 1. In that case, the squared error d^2(x,y) = 2 - 2 * (x dot y), i.e. the squared error distance and the dot product are essentially equivalent.
(Jan 26 '12 at 04:21)
Joseph Turian ♦♦
|
