在线性代数中我们接触到embedding(嵌入)这一术语，表示从高维到低维空间。考虑一个高维空间中的样本集在低维空间中的形态。 “embedding”也应用在计算机图形学的参数化领域中。
问题
给定高维空间\(\mathbb{R}^n\)中的\(m\)个样本点为\(\{X_i\}_{i=1}^m\)，考虑是否可以将\(m\)个样本嵌入到低维空间\(\mathbb{R}^{d}\)，\(d< n\)，使得高维空间中两样本点的度量距离在低维空间中保持不变。
分析
设高维空间中样本点\({ X}_i\)在低维空间中表示为\({ Z}_i\)，要保证度量距离不变，即： \[ \Vert {X}_i-{ X}_j\Vert=\Vert { Z}_i-{ Z}_j\Vert\qquad i,j=1,2,\dots,m \label{eq1} \] 将上式平方得到： \[ \Vert {X}_i-{ X}_j\Vert^2=\Vert { Z}_i\Vert^2+\Vert { Z}_j\Vert^2-2{ Z}_i^{ T}{ Z}_j \label{eq2} \] 令\({ B}={ Z}^{ T}{ Z}\in\mathbb{R}^{m\times m}\)表示低维空间中样本的内积矩阵，内积矩阵第\(i\)行第\(j\)列元素为\(B_{i,j}=Z_i^{\rm T}Z_j\)，用\(D\)表示样本在原始空间中的距离矩阵，其中\(D_{i,j}=\Vert X_i-X_j\Vert\)， \[ D_{i,j}^2=B_{i,i}+B_{j,j}-2B_{i,j} \label{eq3} \] 如果得到满足上式约束的矩阵\({ B}\)，假定\({ B}\)含有\(k\)个非零特征值，分别为\(\lambda_1,\lambda_2,\dots,\lambda_k\)且满足\(\lambda_i\ge\lambda_j,i< j\)，则有\({ B}={ V\Lambda V^T}\)，其中\({ \Lambda}=diag\{\lambda_1,\lambda_2,\dots,\lambda_k\}\)，\({ V}\)的第\(i\)列是特征值\(\lambda_i\)对应的特征向量。则有\({ Z}={ \Lambda}^{\frac{1}{2}}{ V}^{ T}\in\mathbb{R}^{k\times m}\)，如果\(k< n\)，则实现距离不变的降维。下面考虑如何求解满足上式约束的内积矩阵。
内积矩阵的推导
考虑低维样本的中心为原点，即\(\sum_iZ_i=0\)，根据第二等式有： \[ \sum_iD_{i,j}^2=\sum_iB_{i,i}+mB_{j,j} \]
\[ \sum_{i,j}D_{i,j}^2 =2m\sum_iB_{i,i} \]
有：
\[
B_{j,j}=\frac{\sum_iD_{i,j}^2}{m}-\frac{\sum_{i,j}D_{i,j}^2}{2m^2}
\] 代入公式有： \[
B_{i,j} =
-\frac{1}{2}(D_{i,j}^2-\frac{\sum_jD_{i,j}^2}{m}+\frac{\sum_{i,j}D_{i,j}^2}{m^2}-\frac{\sum_iD_{i,j}^2}{m})
\] 由此则可得到内积矩阵。
距离不必严格相等的嵌入
特别地，在现实应用为了降低维度，多数情况下会损失一部分信息。即，如果目标空间维度\(d\)小于非零特征值的个数，则做不到距离严格相等。此时取\({ \Lambda_*}=diag\{\lambda_1,\lambda_2,\dots,\lambda_d\}\)，对应的特征向量矩阵为\(V_*\)。即\(B\approx{ V_*\Lambda_*V^T_*}\)。低维空间中的样本可表示为 \[ Z=\Lambda_*^{\frac{1}{2}}V^T_*\in\mathbb{R}^{d\times m} \]
简单应用\(\mathbb{R}^3\longmapsto\mathbb{R}^2\)
