PhD 3: Old news is so exciting

近來看到一個「早該知道」但昨天才知道的 fact: if $X \subset L^d_2$ then $X$ isometric embeds to $L_1$
如果只說 idea 很簡單 -- pick a random vector $r$ in unit sphere $S_{d-1}$, consider map $f: x \mapsto \langle r, x\rangle$, then

$\mathbb{E}[|f(x) - f(y)|] = \mathbb{E}[|\langle r,x \rangle - \langle r,y\rangle  |] = \mathbb{E}[ |\langle r, x-y \rangle|] \propto ||x-y||_2$
所以只要取"足夠"(無限)多的 sample 然後做 scaling, 就可以準確地 preserve 原本的 distance
加上因為 $L_1^* \hookrightarrow L_1^{\binom{n}{2}}$, 所以是存在 finite dimension 的 $L_1$ embedding