前言

J-L定理是我在阅读关于汉明嵌入的文章时遇到最多的一次概念，其主要是说“一个 d <script type="math/tex" id="MathJax-Element-21">d</script>维空间中的n<script type="math/tex" id="MathJax-Element-22">n</script>个点可以近似等距地嵌入到一个 k≈O(logn) <script type="math/tex" id="MathJax-Element-23">k \approx O(logn)</script>维的空间”，所谓近似等距意思简单地理解就是保持任何两个点之间的相对远近关系，准确但不确切的说法是拓扑同构。该定理是1984年发现的，在压缩感知、流行学习和降维上被应用。ps:应该是个很牛逼的定理。

J-L定理

表述

对任意常数 0<ε<1 <script type="math/tex" id="MathJax-Element-4">0 < ε < 1</script> 和任意正整数 n <script type="math/tex" id="MathJax-Element-5">n</script>, 设k<script type="math/tex" id="MathJax-Element-6">k</script>为一个正整数

<script type="math/tex; mode=display" id="MathJax-Element-7">k\ge4(\epsilon^2/2-\epsilon^3/3)^{-1}\ln n</script>
那么对于任意 Rd <script type="math/tex" id="MathJax-Element-8">{R}^d</script>空间中的 n <script type="math/tex" id="MathJax-Element-9">n</script>个点构成的集合V，始终存在一个映射f:Rd→Rk使得对所有的u,v∈V,<script type="math/tex" id="MathJax-Element-10"> f:\mathbf{R}^d\rightarrow\mathbf{R}^k 使得对所有的 u,v\in V,</script>有
<script type="math/tex; mode=display" id="MathJax-Element-11">(1-\epsilon)\|u-v\|^2\le\|f(u)-f(v)\|^2\le(1+\epsilon)\|u-v\|^2.</script>
且该映射可以在多项式时间内找到。

从上述定理的表述中可以发现：
1.所使用的距离是低维空间中常用的欧氏距离。
2.原始空间中的点数充分决定了降维后空间可以达到的最小维数。
3.不管空间维数，假设原始空间有100万个点，可降维后的空间维数与 ε <script type="math/tex" id="MathJax-Element-12">ε</script>的关系如下，当取ε=0.5<script type="math/tex" id="MathJax-Element-13"> ε =0.5</script>，可以嵌入的最低维空间为664维。

4.降维时若要求保持等距关系越严格，则 ε <script type="math/tex" id="MathJax-Element-14">ε</script>应该越小，但是降维后的空间最低维数也会越大，这中间应该有个权衡（trade-off）。
5. J-L定理给出了低维空间嵌入的误差上界，但这种误差是相对误差。因为以下两个式子等价的。

<script type="math/tex; mode=display" id="MathJax-Element-15">(1-\epsilon)\|u-v\|^2\le\|f(u)-f(v)\|^2\le(1+\epsilon)\|u-v\|^2.</script>

<script type="math/tex; mode=display" id="MathJax-Element-16">\frac{(\|f(u)-f(v)\|^2-\|u-v\|^2)}{\|u-v\|^2}\le\epsilon.</script>

关于其证明，网上答案很多，此处就省了，只求会灵活运用就好。

映射

如何找到那个映射函数 f <script type="math/tex" id="MathJax-Element-17">f</script>是我们最为关心的，原始论文中给出了一个随机投影的方法，如下：
设 随机生成一个k×d的矩阵A，将Rd空间向量投影为一致随机的k维空间中的向量，做法是<script type="math/tex" id="MathJax-Element-18">随机生成一个 k\times d 的矩阵A，将 \mathbf{R}^d 空间向量投影为一致随机的k维空间中的向量，做法是</script>

<script type="math/tex; mode=display" id="MathJax-Element-19">对v\in\mathbf{R}^d，左乘矩阵A，然后乘以系数\sqrt{\frac{d}{k}}， 这时 \sqrt{\frac{d}{k}}Av \in \mathbf{R}^k。</script>
乘以系数 dk−−√是为了保证E[∥∥dk−−√Av∥∥2]=∥v∥2. <script type="math/tex" id="MathJax-Element-20"> \sqrt{\frac{d}{k}}是为了保证\mathbf{E}\left[\left\|\sqrt{\frac{d}{k}}Av\right\|^2\right]=\|v\|^2.</script>

看到这个映射的构造方法，让我想起了局部敏感哈希（LSH）~

参考资料：
[1]http://tcs.nju.edu.cn/wiki/index.php/%E9%9A%8F%E6%9C%BA%E7%AE%97%E6%B3%95_(Fall_2011)/Johnson-Lindenstrauss_Theorem
[2]https://www.douban.com/note/162173024/