11.9 賦距空間與 L1 嵌入的 Bourgain 定理

圖上的距離也滿足賦距空間(metric space)的定義：非負距離、對稱性、遞移律、三角不等式。
如果我們將圖上的點對應到 k 維的向量空間，那麼只要 k 足夠小，就可以很有效率地計算近似距離。

k 維向量空間的 L1距離是這樣定義的：把每一個維度數字相差的絕對值累加起來，就是距離。
今天來說說一個把任意賦距空間投射到 O(log^2 n) 維度的 L1距離之向量空間，且距離的誤差不超過原先的 O(log n) 倍的 Bourgain 定理(證明略)：

對於所有 i=1, 2, …, log n 以及 j = 1, 2, …, 1000 log n；我們以 2^{-i} 的機率(這個機率只與 i 有關、與 j 無關) 均勻取樣圖上的點集合 A_ij。接著，對於圖上每一個點 x，我們定義 k=1000 * log^2 n 維度的向量：第 (i, j) 維度的數值就是 x 到 A_ij 之間的點集合任一點的最短距離 dist(x, A_ij)。

這個方法建構出來的向量，要表達它也需要 O(log^3 n)-bits，誤差在計算距離且除以 log n 之後也為 O(log n)，不過它不只適用於任何圖，也適用於任何 n 筆資料的賦距空間，相當巧妙。

除了 L1 距離，Bourgain 的定理也適用於任何的 Lp-距離 (只有誤差要稍微調整一下，但仍為 O(log n))。

參考資料：
https://lucatrevisan.github.io/teaching/expanders2016/lecture10.pdf