04.2.MDS.md

[toc]

MDS(Multidimentional Scaling)

目的是把 $P\subset R^d$ 降维到 $Q\subset R^k$, 保持点之间的距离不变.

算法

令 $D\in R^{n\times n}$ 为距离矩阵, $M_{ij}=\left<x_i,x_j\right>$ 为相似度矩阵, 则由 $|x_i-x_j|^2=|x_i|^2+|x_j|^2-2\left<x_i,x_j\right>$ 有 $\left<x_i,x_j\right>=\frac{1}{2}\left(|x_i-x_j|^2=|x_i|^2+|x_j|^2\right)$

令 $x_1=0$, 则 $|x_j|^2=|x_1-x_j|^2=D_{ij}^2$,

先根据 $D$ 求出 $[AA^T]{ij}=\frac{1}{2}\left(D{i1}^2+D_{j1}^2-D_{ij}^2\right)$, 然后对 $AA^T$ 特征值分解即可.