如果只說 idea 很簡單 -- pick a random vector r in unit sphere S_{d-1}, consider map f: x \mapsto \langle r, x\rangle, then
所以只要取"足夠"(無限)多的 sample 然後做 scaling, 就可以準確地 preserve 原本的 distance
加上因為 L_1^* \hookrightarrow L_1^{\binom{n}{2}}, 所以是存在 finite dimension 的 L_1 embedding
No comments:
Post a Comment