出租车几何学及其它

在 matrix67 的一篇 blog 里提到了所谓的「出租车几何学」，也就是在一个完全是棋盘格街道的城市里，两点之间的距离由其横纵两个方向上的差距之和所决定的这种情况。很显然，这正好是一个标准的赋予 L1 度量的  空间。

和标准的 L2 欧氏度量相比，这个度量有很多好玩的性质，比如这个度量下的「圆」其实是一个正方形。

这个平面上两个点的「垂直平分线」（也就是到两个点的 L1 距离相等的点集）其实是一条折线。

但是有些区别是更本质也更有意义的。比方说，假定有一条街道是斜着的，并且倾斜角不等于 45°，那么从街道外任何一点出发，到这条街道上的最短路径一定是全水平或者全竖直的。

这件事情有其重要的价值：抽象地说，这意味着在给定的线性约束下， L1 距离的最小值是在某个单一的维度上取到的。在高维的情形下，这个最小值不一定是取在某个单一的维度上，但是差不多一定是集中在很少的几个维度上。这就是「稀疏重建」这件事情的的理论基础。

稀疏重建的意思是说，假定我们知道有一个高维信号中有很大一部分维度上的值是零（但是并不知道具体哪些是零），这种性质就称为「稀疏的」，我们需要通过关于这个信号的一些线性条件来重构它。而上述性质就告诉我们，只要去寻找满足线性条件约束的 L1 度量的最小值，这个解多半会集中在很少几个维度上，剩下很大一部分维度上就自然是零，这就实现了我们所要求的目标。由于自然界中很大一部分信息都可以在某种意义上看做是稀疏的，这一理论就显得特别有价值。

关于 L1 度量空间有一些有趣的数学问题，比如：在 n 维空间里，最多能有多少个点的 L1 距离两两相等？容易看出至少可以有 2n 个，比如取所有坐标形如 (0,0,…,±1,…,0,0) 的点即可。但是这是不是最优情形呢？目前还没有人知道。与此相对的，如果是在常规的 L2 度量（即欧氏距离）空间下，这问题的解显然是 n+1。

与 L1 距离相对应的（确切说来是相对偶的）是所谓 L∞ 距离。在平面上，它不是定义为横纵两个方向上的差距之和，而是两个差距中较大的一个。在这种距离下的「圆」也是正方形，不过方向不同。

L1 度量空间所具有的性质，L∞ 度量空间大多以另一种形式也具备。只不过由于种种原因，它的应用并不如前者那么广泛，至少目前看来是如此。