通常，我们会遇到数据来自一个嵌入在高维欧氏空间的低维流形的情况。有一些帮助我们找到这些低维嵌入（embedding）的方法，如多维尺度变换（Multiple Dimensional Scaling，MDS），局部线性嵌入（Locally Linear Embedding，LLE），临域保持嵌入（Neighborhood Preserving Projection，NPE），等距离特征映射（ISOMAP），拉普拉斯特征映射（Laplacian Eigenmap，LE），等等。

多维尺度变换（MDS）

给定 $n$ 个训练样本以及它们对应的距离矩阵 $\mathbf{D}$ ，其元素 $d_{ij}$ 是第 $i$ 个样本和第 $j$ 个样本的距离。假设 $n$ 个样本的内积矩阵是 $\mathbf{B}$ 。我们可以在给定 $\mathbf{D}$ 的情况下计算 $\mathbf{B}$ ，反过来也是对的。

MDS 的核心思想是在低维的 embedding 中保持样本之间的距离。因此，假设 embedding 的数据矩阵是 $\mathbf{Z}$ ，那么 $\mathbf{Z} \mathbf{Z}^T$ 需要尽可能接近 $\mathbf{B}$ 。

为此，我们对 $\mathbf{B}$ 做一个特征值分解，

\mathbf{B} = \mathbf{V} \mathbf{\Lambda} \mathbf{V}^T,

那么

\mathbf{Z} = \mathbf{V}_r \mathbf{\Lambda}_r^{\frac{1}{2}}

就是一个很好的近似，同时满足 embedding 的各列之间正交。

局部线性嵌入（LLE）

LLE 的思想是在降维时尽可能保持局部结构。

对于任一样本，LLE 首先寻找一个它的邻居样本的仿射组合（affine combination），使得这个组合能尽可能地重建该样本。随后，重建每个样本的仿射组合系数可以构成一个权重矩阵 $\mathbf{W}$ ，其中 $W_{ij}$ 是第 $j$ 个样本重建第 $i$ 个样本的权重，注意 $W_{ij} = 0$ 如果 $j$ 不是 $i$ 的邻居。这里，邻居由 $k$ 近邻方法来决定。

随后，LLE 求解下式的优化问题（注意，这里 $\mathbf{Z}$ 的):

\begin{align*} \underset{\mathbf{Z}}{\min} && & \mathrm{tr}\left( \mathbf{Z}^T (\mathbf{I} - \mathbf{W})^T (\mathbf{I} - \mathbf{W}) \mathbf{Z} \right) \\ \mathrm{subject~to}&& & \mathbf{Z Z}^T = \mathbf{I}. \end{align*}

临域保持嵌入（NPE）

NPE 可以看作是 LLE 的线性近似版本。它寻找一个线性投影方向来完成从 $\mathbf{X}$ 到 $\mathbf{Z}$ 的转换：

\begin{align*} \underset{\boldsymbol{a}}{\min} && & \mathrm{tr}\left( \boldsymbol{a}^T \mathbf{X} (\mathbf{I} - \mathbf{W})^T (\mathbf{I} - \mathbf{W}) \mathbf{X}^T \boldsymbol{a} \right) \\ \mathrm{subject~to}&& & \boldsymbol{a}^T \mathbf{X} \mathbf{X}^T \boldsymbol{a} = 1. \end{align*}

易得 $\boldsymbol{a}$ 为下面的广义特征向量问题的最小特征值对应的特征向量：

\mathbf{XMX}^T \boldsymbol{a} = \lambda \mathbf{XX}^T \boldsymbol{a},

后续的其它 embedding 投影方向可以由剩下的和最小特征值对应的广义特征向量求得。

等距离特征映射（ISOMAP）

顾名思义，ISOMAP 尝试保持样本点之间的度量（距离）。

ISOMAP 的算法步骤如下：

使用 kNN 构建一个无向图，其中图的连接权重是样本点在原始空间的距离。
使用 Dijkstra 算法寻找图上每一对样本之间的最短距离。把这个两两之间的距离作为流形上样本之间的测地线距离（geodesdic distance）。
基于这个距离，采用 MDS 算法来计算低维 embedding。

拉普拉斯特征映射（LE）

考虑这个一个问题：把一个带权无向图 $\mathcal{G}$ 映射到一条线上，并让相连接的节点尽可能接近，以保持图的结构从而保持流形的局部结构）。图上有较大连接权重的两个节点应该有更小的距离。基于这个思想，我们可以得到下面的优化问题。

\begin{align*} \frac{1}{2} \sum_{i,j} w_{ij} (y_i - y_j)^2 = \boldsymbol{y}^T \mathbf{L} \boldsymbol{y}, \end{align*}

其中， $y_i$ 是第 $i$ 个样本点在线上的位置， $\mathbf{L}$ 是图拉普拉斯矩阵。

为了对上面的目标函数做优化，我们需要加一些限定条件，

\boldsymbol{y}^T \mathbf{D} \boldsymbol{y} = 1.

这个限定条件把图上各个节点的重要性因素考虑在内。

随后，我们就可以得到 LE 的优化问题：

\begin{align*} \min_{\mathbf{Y}} && & \mathrm{tr}\big( \mathbf{Y}^T \mathbf{L Y} \big) \\ \mathrm{subject~to} && & \mathbf{Y}^T \mathbf{D} \mathbf{Y} = \mathbf{I} \\ && & \mathbf{Y}^T \mathbf{D} \boldsymbol{1} = \boldsymbol{0}. \end{align*}

最后一个等式约束是为了除去这个问题的一个平凡解，即常数向量。上面这个优化问题的解是下述广义特征向量问题的最小的特征值对应的特征向量（除去平凡特征值 0）

\mathbf{L} \boldsymbol{y} = \lambda \mathbf{D} \boldsymbol{y}.

样本外扩展

LE 的一个不足是它不能应用到图之外的样本上。为了解决这个问题，我们可以采用流形约束的框架对其做样本外扩展：

\begin{align*} \min_{f \in \mathcal{H}_K} && & \gamma \| f \|_{\mathcal{H}_K}^2 + \boldsymbol{f}^T \mathbf{L} \boldsymbol{f} \\ \mathrm{subject~to} && & \boldsymbol{f}^T \mathbf{D} \boldsymbol{f} = 1 \\ && & \boldsymbol{f}^T \mathbf{D} \boldsymbol{1} = 0. \end{align*}

这里，我们假设映射是一个函数，这个函数来自于核函数 $K$ 所诱导的再生核希尔伯特空间。基于表示定理，这个优化问题有下面形式的解：

f^*(x) = \sum_{i=1}^N \alpha_i K(x_i, x).

因此， $\boldsymbol{f} = \mathbf{K} \boldsymbol{\alpha}$ 。进一步地，我们假设图拉普拉斯矩阵 $\mathbf{L}$ 是归一化之后的，即 $\tilde{\mathbf{L}} = \mathbf{I} - \mathbf{D}^{1/2} \mathbf{W} \mathbf{D}^{1/2}$ 且 $\tilde{\mathbf{D}} = \mathbf{I}$ 。那么，我们有

\begin{align*} \min_{\boldsymbol{\alpha} \in \mathbb{R}^N} && & \gamma \boldsymbol{\alpha}^T \mathbf{K} \boldsymbol{\alpha} + \boldsymbol{\alpha}^T \mathbf{KLK} \boldsymbol{\alpha} \\ \mathrm{subject~to} && & \boldsymbol{\alpha}^T \mathbf{K}^2 \boldsymbol{\alpha} = 1 \\ && & \boldsymbol{1}^T \mathbf{K} \boldsymbol{\alpha} = 0. \end{align*}

这是一个二次项约束二次规划 (QCQP) 问题。