Loading web-font TeX/Math/Italic

網頁

Wednesday, 12 November 2014

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

No comments:

Post a Comment