Question

If we think of the l₁ distance as a grid-distance between points, then we can think of l₂ distance as what we get when we "shortcut" the grid by going "inside" a cell.

Making the grid finer doesn't change the l₁ distance, so there's no obvious sense in which the l₂ distance can be seen as a limiting version of the l₁.

So here's my question: is there any way to take an l₁-like distance and extract an l₂ like distance from it (possibly as a limiting case). I'm asking because i have a distance defined in a discrete space that has an l₁-like behaviour, and I'd like to generalize it as the discrete space gets finer and finer, but I want to end up with a distance that goes "directly" through the space like l₂.

apologies if this is way too vague.

Answer 1

L_2 can be viewed as the limit of a sequence of metrics whose metric balls are (in the plane) regular polygons with 2n sides, where n goes to infinity. In higher dimensions one doesn't have enough regular polytopes to make a limit out of them, but it works just as well to use irregular ones. This technique is sometimes useful in computational geometry, because the polygonal metrics allow for faster range searching data structures than the Euclidean one.

If you want a distance in some sort of discrete graph (the way that L_1 can be viewed as distance in a regular grid) but that approaches planar L_2 in the limit, try using the pinwheel tiling. If you measure the shortest path along tile edges between any two points on the edges of any two tiles, and then repeatedly subdivide to produce a finer pinwheel tiling, the shortest path distance will approach the Euclidean distance in the limit.

As for Kore min's suggestion of looking into metric embedding: any metric can be embedded into L_infinity with no distortion at all. And in the plane, L_1 is the same as L_infinity (though they are quite different in higher dimensions) so it might have something to do with what you're talking about. See e.g. this Wikipedia article.

Answer 2

In some cases, you can recover L_2 information in the limit by considering random walks, or said differently, basically by counting paths. When you say "discrete space with L_1-like behavior," I imagine a big grid of points (something like Z^d) that are connected to their nearest neighbors by edges, with the distance between two points being defined in the natural graph-theoretic way as the length of the shortest path between them. If that's the case, you can consider a uniform random walk along the edges of the graph, and then successively refine the grid. This is important: if you refine the grid, say, by a factor of two (so each step of the random walk becomes half as big), then you have to refine the walk by taking steps four times as fast. (In general, when you refine by a factor F, you have to take steps F^2 times as fast.) As you keep refining, the probability of the walk ending up near a particular point at a fixed time in the future may stabilize to something that looks like a function of L_2 distance from the starting point.

If this construction works in your case, then you can think of the logarithm of the probability of ending up in a small neighborhood as being roughly proportional to the volume of the neighborhood and the square of its L_2 distance from the starting point, but except in very special cases, the approximation probably won't be good for all pairs of points, especially if they aren't very close to one another. Note that computing such probabilities basically amounts to counting paths of particular lengths between points, as opposed to just finding the length of the shortest path (which would roughly corresponding to the L_1 distance).

How much that computation will actually resemble an L_2-like distance depends on many things. The construction will work basically as stated when you successively refine a grid like Z^d because of the central limit theorem. If your "discrete space" isn't very similar to that, then the construction might not work at all, or it might give you something that isn't quite right but is "close enough for government work," so to speak. You'll have to be the judge of that.

Answer 3

I guess you are thinking something about metric embedding. Any metric can be embedding into l_2 with the distortion bounded by O(log n), which is tight in general.

See this lecture notes for more information: http://www-math.mit.edu/~goemans/18409.html

Also, the Kashin’s decomposition is closely related to your problem, see http://www.cwru.edu/artsci/math/szarek/SzarekICMslides.pdf