多维放缩MDS算法

在线性代数中我们接触到embedding(嵌入)这一术语,表示从高维到低维空间。考虑一个高维空间中的样本集在低维空间中的形态。 “embedding”也应用在计算机图形学的参数化领域中。

问题

给定高维空间\(\mathbb{R}^n\)中的\(m\)个样本点为\(\{X_i\}_{i=1}^m\),考虑是否可以将\(m\)个样本嵌入到低维空间\(\mathbb{R}^{d}\)\(d< n\),使得高维空间中两样本点的度量距离在低维空间中保持不变。

embedding

分析

设高维空间中样本点\({ 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\)

embedding