Skip to content
Jan 21, 2011

出租车几何学及其它

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

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

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

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

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

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

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

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

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

2 Comments

  1. OriBeta / Jun 4 2016

    「L1度量及L∞度量之间的关系在更高维度的空间不成立。和一点有相等切比雪夫距离的点会形成一个立方体,各面都和坐标轴垂直,而和一点有相等曼哈顿距离的点会形成一个正八面体。」——维基百科

  2. OriBeta / Jun 4 2016

    突然发现你就是《长度是怎样炼成的》的作者!!
    P.S.:这种「巧合」是因为中文博客圈太小了么

Comments are closed.