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