非负矩阵分解和图非负矩阵分解算法的模型、优化、收敛

非负矩阵分解（Non-negative matrix factorization, NMF）算法是一种矩阵分解方法，它可以将一个非负矩阵分解为两个非负矩阵的乘积，其中的因子矩阵可以用来表示原始矩阵的特征。

NMF算法的模型可以描述为：给定一个非负矩阵 $V \in \mathbb{R}_{+}^{m\times n}$，NMF算法的目标是寻找两个非负矩阵 $W \in \mathbb{R}_{+}^{m\times r}$ 和 $H \in \mathbb{R}_{+}^{r\times n}$，使得它们的乘积最接近原始矩阵 $V$，即：

$$\min_{W,H}\|V-WH\|_{F}^{2}$$

其中 $\|\cdot\|_{F}$ 表示矩阵的 Frobenius 范数。为了保证因子矩阵非负，通常还会加上一个非负约束条件：

$$W_{ij}\geq 0, H_{ij}\geq 0$$

NMF算法可以采用多种优化方法进行求解，如基于梯度下降的方法、基于交替最小二乘法的方法、基于贪心算法的方法等。其中，基于交替最小二乘法的方法是比较常用的一种方法，其优化过程可以描述为：

1. 初始化因子矩阵 $W$ 和 $H$；
2. 固定 $H$，求解 $W$，即：

$$W_{ij} \leftarrow W_{ij}\frac{(VH^T)_{ij}}{(WHH^T)_{ij}}$$

3. 固定 $W$，求解 $H$，即：

$$H_{ij} \leftarrow H_{ij}\frac{(W^TV)_{ij}}{(W^TWH)_{ij}}$$

4. 重复步骤2和步骤3，直到收敛。

图非负矩阵分解（Graph Non-negative Matrix Factorization, GNMF）算法是一种NMF算法的扩展，它在NMF算法中增加了图结构的约束条件。具体来说，在GNMF算法中，每个数据点都可以看做图中的一个节点，而数据点之间的相似度则可以用图中的边来表示。因此，GNMF算法可以用于图数据的聚类、降维等任务。

GNMF算法的模型可以描述为：给定一个非负矩阵 $V \in \mathbb{R}_{+}^{m\times n}$ 和一个图 $G=(V,E)$，其中 $V=\{v_{1},v_{2},\ldots,v_{n}\}$ 表示数据点集合，$E=\{e_{ij}\}$ 表示数据点之间的边集合，NMF算法的目标是寻找两个非负矩阵 $W \in \mathbb{R}_{+}^{m\times r}$ 和 $H \in \mathbb{R}_{+}^{r\times n}$，使得它们的乘积最接近原始矩阵 $V$，且同时满足以下约束条件：

1. $W$ 和 $H$ 都是非负矩阵；
2. $H$ 的每一列和为1，即：$\sum_{i=1}^{n}H_{ij}=1$；
3. $W$ 的每一行对应于图 $G$ 中的一个节点，即：$W_{i\cdot}$ 对应于节点 $v_{i}$；
4. $W$ 的每一行都是非负的，且相似的节点在 $W$ 中应该有相似的表示。

GNMF算法可以通过求解下面的优化问题来实现：

$$\min_{W,H}\|V-WH\|_{F}^{2}, s.t. W_{i\cdot}\geq 0, H_{ij}\geq 0, \sum_{i=1}^{n}H_{ij}=1, W_{i\cdot}\sim W_{j\cdot}, e_{ij}>0$$

其中 $e_{ij}$ 表示节点 $v_{i}$ 和节点 $v_{j}$ 之间的边权重。GNMF算法可以采用基于梯度下降的方法进行求解，其优化过程与NMF算法类似，只需在每次更新 $W$ 的时候加上图约束条件即可。