Month: July 2011

Johnson–Lindenstrauss 定理是我在今晚的一个学术报告里听说的一个非常令人惊讶的定理。简单说来，它的结论是这样的：一个一百万维空间里的随便一万个点，一定可以几乎被装进一个几十维的子空间里！ 严格说来是这样：在 M 维空间中的 N 个点，几乎总是被包含在一个 D 维子空间里的。这里的 D 按照直觉应当等于 N 的阶，可是实际上我们只需要让 D 是 log(N) 的阶就可以了。这里「几乎被包含在」的确切含义是它在这个子空间上的投影几乎是等距的（允许有一个 ε 的误差，而常数 D/log(N) 就依赖于 ε）。很显然，这件事情在高维数据降维时有极重要的意义。 这个定理的证明很初等。它依赖于这样的一个基本概率事实：一个随机的 M 维单位向量到一个随机的 D 维子空间上的投影的长度几乎一定约等于 D/M。这件事情本身也有点不同寻常，虽然它可以通过简单的计算来证实。这是概率论计算中常常出现的由于高维度而导致的反直觉现象的一例。 这让我想起另一个高维度导致的悖论，是我在学大数定律时了解到的。在 M 维单位立方体中随机取一个点，当 M 充分大时根据大数定理容易算出这个点到立方体中心的距离几乎一定等于 √(M/3)/2。于是这就说明 M 维实心单位立方体几乎就完全位于一个半径为 √(M/3)/2 的球壳上。这里没有任何捣鬼之处，事实上就是如此。

上个周末去了一趟密苏里州的 St. Louis。这里一百年前还是美国的第四大都市，拜得天独厚的地理条件所赐，是整个美国的水陆交通枢纽。一百年后，这里已经变成了一个乡下小城。它最著名的地标建筑当然是上世纪六十年代建成的 Gateway Arch，是为纪念美国的西部大开发而树立的一座纪念碑，高 192 米，是至今为止全美最高的纪念碑。（下图转载自 wiki。） 直到到了现场我才意识到它真的非常高，高到看起来有点不自然的程度。而另一个让我到了现场才意识到的问题是，作为这么高的一个拱，要稳定地树立在那里，它的形状不可能是任意弯成的。事实上，它的曲线是在数学上被唯一确定的。我不知道这个事实在建筑从业者中是不是尽人皆知，但是我自己至少此前从来没有想到过。 确切来说，它的曲线一定是悬链线，也就是一根绳子固定两头后自然下垂得到的曲线（当然要经过一个上下反转）。 这个事实可以这样简单的推出：一根悬绳的曲线所满足的数学要求是每个质点所受到的三个力——即左侧和右侧的拉力以及自身的重力——必须刚好平衡。而这样的一个拱要想保持稳定，所需要满足的数学要求则是每一小段所受到的三个力——即左侧和右侧的推力以及自身的重力——必须刚好平衡。容易看出，这两种关系正好相差一个正负号，所以把悬链线翻过来就是拱的曲线。 悬链线早在文艺复兴时代之前就吸引了数学家的注意，伽利略曾经错误地以为悬链线就是抛物线（看起来确实很像），莱布尼茨、惠更斯和伯努利兄弟差不多同时在十七世纪末给出了悬链线的正确数学公式（即双曲余弦函数 cosh）。 确切说来，Gateway Arch 的曲线并不是严格的悬链线，因为它的粗细不匀，拱顶的宽度只有两脚的三分之一，所以它相当于把一根粗细不匀的绳子垂成的形状翻转过来。但是数学上它仍然是由双曲余弦函数来刻画的。 我不知道在建筑学上人们是什么时候意识到悬链线可以用来做拱的，似乎是胡克第一个严格指出了这一点，但是显然早在它之前就有更古老的建筑采用悬链线拱了。（不过更多的古代拱门还是半圆形的。悬链线作为数学曲线来说过于精巧，而半圆看起来似乎已经挺稳定了。有更好的解释么？）