第44章 庞文清教授的请求

  自从答应要帮赵明远他们完善自適应图分割算法，肖宿便开始更多的研究计算数学了。

  他面前摊开的《计算几何与算法设计》已经翻到了第七章，高维空间中的近似最近邻搜索。

  此刻，他正盯著书中的一个证明，关於在高维空间中，隨机投影如何保持点间距离的詹森-林登史特劳斯引理。

  这个引理看似简单，却有著深刻的几何內涵。

  肖宿的笔在纸上移动：

  “设x???，|x|=m，对任意0＜e＜1/2，令k=o(e?2log m)，则存在线性映射f:??→??，使得对任意x,y∈x，有(1-e)‖x-y‖2≤‖f(x)-f(y)‖2≤(1+e)‖x-y‖2。”

  他停下笔，思考这个证明背后的直觉。

  为什么是o(e?2log m)这个形式？

  为什么对高维空间中的点集做隨机投影后，距离关係能大致保持？

  他的大脑开始自动推导。

  这本质上是一个集中不等式问题，与球面上的测度集中现象有关……

  就在这时，放在桌角的手机震动了。

  肖宿的思考被打断，眉头微微皱起，他不喜欢被打扰，尤其是沉浸在思考中的时候。

  屏幕上显示“顾叔叔”。

  肖宿犹豫了一秒，还是拿起手机，起身走向走廊。