黎曼流形聚类与降维：理论、算法与应用

### 黎曼流形聚类与降维：理论、算法与应用 #### 1. 线性流形下的局限性 在处理包含 $m - m_1$ 个非线性流形和 $m_1$ 个维度为 $\{d_j\}_{j = 1}^{m_1}$ 的线性流形的数据时，有 $\{v_j\}_{j = 1}^{m}$ 和 $\{e_j\}_{j = 1}^{m_1}$ 属于矩阵 $M$ 的核空间，且核空间的维度为 $m + \sum_{j = 1}^{m_1} d_j$。由于核空间中的任意向量是成员向量和嵌入向量的线性组合，所以在存在线性流形的情况下，我们无法直接从 $ker(M)$ 中获得数据的分割或每个子空间的嵌入。这是算法的一个局限性，后续我们假设数据不位于线性流形上。 #### 2. 基于黎曼度量的流形聚类与降维 传统的非线性降维（NLDR）技术适用于结构未知的流形，由于度量未知，每个操作都通过相应的欧几里得操作来近似。然而，对于具有良好研究几何性质的黎曼流形，通常可以得到黎曼操作的闭式公式。因此，我们需要将 NLDR 技术扩展到黎曼流形，同时考虑适当的黎曼结构。 ##### 2.1 黎曼流形回顾 - **基本概念**：光滑流形是局部微分同胚于欧几里得空间的拓扑空间。对于流形 $M$ 上的一点 $x$，其切空间 $T_xM$ 定义为所有通过 $x$ 的可能曲线 $\gamma$ 的切向量的张成。黎曼度量是连续的点积集合 $\langle\cdot,\cdot\rangle_x$。 - **曲线长度与测地线**：两点 $x_i, x_j \in M$ 之间曲线的长度定义为： \[L_{a}^{b}(\gamma) = \int_{a}^{b} \sqrt{\langle\dot{\gamma}(t), \dot{\gamma}(t)\rangle_{\gamma(t)}} dt\] 其中 $\gamma(a) = x_i$ 且 $\gamma(b) = x_j$。长度最小的曲线称为测地线，两点之间的距离定义为测地线的长度： \[dist(x_i, x_j) = L_{0}^{1}(\gamma), \quad \gamma(0) = x_i, \gamma(1) = x_j\] - **指数映射与对数映射**：设 $v$ 是 $T_xM$ 中的单位长度切向量，指数映射 $\exp_x : T_xM \to M$ 将每个切向量 $tv$ 映射到沿着以 $x$ 为起点、方向为 $v$ 的测地线移动距离 $t$ 所得到的点 $\gamma(t)$。集合 $C_x \subset M$ 定义为所有满足 $\gamma = \exp(tv)$ 是 $t \in [0, t_0]$ 上长度最小测地线的点 $x_i = \exp(t_0v)$ 的集合，其边界称为割迹。指数映射在 $C_x$ 的内部是可逆的，对数映射 $\log_x : C_x \to T_xM$ 定义为 $\log_x = \exp_x^{-1}$。对于任意 $x_i \in C_x$ 且 $x_i = \exp_x(tv)$，有 $\|\log_x(x_i)\|_x = \|tv\|_x = dist(x, x_i) = t$。 - **线性测地插值**：线性测地插值利用指数和对数映射定义为 $\hat{x} = \exp_{x_i}(w \log_{x_i}(x_j))$，其中 $w \in [0, 1]$，$\hat{x}$ 是 $x_i$ 和 $x_j$ 在 $t = w$ 处的线性插值。 - **均值与主成分计算**： - **内在均值**：内在均值 $\bar{x}$ 定义为以下最小化问题的解： \[\bar{x} = \arg\min_{x \in M} \sum_{i = 1}^{n} dist(x, x_i)^2 = \arg\min_{x \in M} \sum_{i = 1}^{n} \|\log_x(x_i)\|_x^2\] 通常没有闭式解，且存在性和唯一性不能保证。但当数据位于足够小的邻域内时，可以证明其存在性和唯一性。内在均值的计算可以通过以下算法实现： ```plaintext 算法 2：内在均值 输入：数据点 $x_1, \ldots, x_n \in M$，预定义阈值 $\epsilon$，最大迭代次数 $T$ 步骤： 1. 初始化 $t = 1$，随机选择 $i$ 令 $\bar{x}_1 = x_i$，$v \neq 0 \in T_{\bar{x}_1}M$ 2. 当 $t \leq T$ 或 $\|v\|_{\bar{x}} \geq \epsilon$ 时： (a) 计算切向量 $v = \frac{1}{n} \sum_{i = 1}^{n} \log_{\bar{x}_t}(x_i)$ (b) 设置 $\bar{x}_{t + 1} = \exp_{\bar{x}_t}(v)$ ``` - **主测地分析**：计算黎曼流形上的主成分不像欧几里得空间那样直接，需要将点投影到测地线上。主测地分析（PGA）算法如下： ```plaintext 算法 3：主测地分析 输入：数据点 $x_1, \ldots, x_n \in M$ 步骤： 1. 按照算法 2 计算内在均值 $\bar{x}$ 2. 计算关于 $\bar{x}$ 的切向量 $v_i = \log_{\bar{x}}(x_i)$ 3. 构造样本协方差矩阵 $cov(x) = \frac{1}{n} \sum_{i = 1}^{n} v_iv_i^{\top}$ 4. 对矩阵 $cov(x)$ 进行特征分析，特征向量 $\{u_i\}_{i = 1}^{d}$ 给出主方向，$\{u_i\}_{i = 1}^{d}$ 构成 $T_{\bar{x}}M$ 的正交基 ``` 欧几里得空间和黎曼空间的标准操作对比如下： | 操作 | 欧几里得空间 | 黎曼空间 | | ---- | ---- | ---- | | 减法 $\overrightarrow{x_ix_j}$ | $x_j - x_i$ | $\lo