多视角-4-Latent Multi-view Subspace Clustering

原文地址：https://www.onacademic.com/detail/journal_1000040248521410_5407.html

Abstract

论文提出了一种新的潜在多视点聚类方法，该方法对具有潜在表示的数据点进行聚类，同时从多个视点中挖掘潜在的互补信息。与现有的利用原始特征重构数据点的单视图子空间聚类方法不同，我们的方法寻找潜在的潜在表示，并在学习到的潜在表示的基础上进行数据重构。
由于多视图的互补性，潜在表示可以比单个视图更全面地描述数据本身，从而提高子空间表示的准确性和鲁棒性。该方法具有直观、高效的特点，并采用了改进的拉格朗日乘子交替方向最小化(ALM-ADM)算法。

1 Introduction

一般而言，子空间聚类方法认为数据点是从对应于不同簇的多个子空间中提取的。最近提出了一种基于自表示的子空间聚类方法，该方法可以用数据点本身的线性组合来表示每一个数据点，一般公式表示如下：$$\underset{\mathbf{Z}}{\min }L(\mathbf{X},\mathbf{X}\mathbf{Z})+\alpha \Omega (\mathbf{Z})\text{\hspace{1em}(1)}$$
$\alpha >0$ 平衡了 重构的误差和子空间表示 $Z$ 的正则化
$L(.)$ 和 $\Omega (.)$ 各自表示损失函数和正则化项，通常是根据不同的假设来定义的，比如SSC,LLR,SMR。

基于自我表示矩阵 $Z$ ，通常用 $S=abs(Z)+abs(Z^T)$来构建相似矩阵，最后，基于相似矩阵 $S$ ，通常使用谱聚类算法来得到最后聚类结果。

以往的子空间聚类方法仍然存在不足的地方，他们的performance通常受到原始特征之类的影响，特别是在观测量不足或严重损坏的情况下。因此多视角聚类被提出来了，其中每个数据点都用 来自多个来源的特征信息 来描述。这些多视图表示包含来自多个线索的丰富信息，有利于任务聚类。在适当的多视图约束条件下，这些子空间聚类方法显示出了它们的优越性。它们通常直接重构原始视图上的数据点，并生成每个视图的子空间表示。然而，单个视图通常不足以描述数据点，这使得仅使用一个视图进行重构本身存在风险。此外，数据采集可能存在噪声，进一步增加了聚类的难度。

为了解决这些问题，论文中介绍了 a latent representation to expolre the relationships among data points and handle the possible noise.

假设多重视角来源于一个共同的潜在表示，它可以从本质上描述数据，并且揭示一般的不同视角共享的潜在结构。基于此，论文提出了$LatentMulti-viewSubspaceClustering(LMSC)$。提出的方法基于多视角特征学习潜在表示，并且生成了一般的子空间表示。更多的，该方法将潜表示学习和多视角子空间聚类集成在一个统一的框架内，并利用增广拉格朗日乘子和交替方向最小化策略 来进行了优化。
论文使用综合的多视图潜在表示进行数据重构，而不是原始的每个单一视图。

与LS3C对原始单视图数据进行降维不同，论文方法恢复了潜在的多视图表示，并在这种潜在表示下同时学习了不同视图对应的投影。

2 Proposed Approach

论文考虑潜在表示（latent representation）子空间聚类。给出 N 个多视角的观测量 ${\left\{\left[{\mathrm{x}}_i^{(1)};\dots ;{\mathrm{x}}_i^{(V)}\right]\right\}}_{i=1}^N$，它包括了 $V$ 个不同视角，目标是推出每个数据点共享的latent representation $\mathbf{h}$ .
论文方法假设这些不同视角都是源于一个潜在的表示。如上图所示，不同视角的观测结果可以使用各自的模型$\left\{{\mathbf{P}}^{(1)},\dots ,{\mathbf{P}}^{(V)}\right\}$和共享潜在表示 H = { h i } i = 1 N \mathbf{H}=\left\{\mathbf{h}_{i}\right\}_{i=1}^{N} H={hi​}i=1N​来重构。相应的，作者有${\mathbf{x}}_i^{(v)}={\mathbf{P}}^{(v)}{\mathbf{h}}_i$,考虑噪音，可以得到：$${\mathbf{x}}_i^{(v)}={\mathbf{P}}^{(v)}{\mathbf{h}}_i+{\mathbf{e}}_i^{(v)}\text{\hspace{1em}(2)}$$其中 ${\mathbf{e}}_i^{(v)}$ 表示对应于$v^{th}$视角的重构误差
要推出的多视角潜表示的目标函数：$$\begin{array}{l}{\min }_{\mathbf{P},\mathbf{H}}{L}_h(\mathbf{X},\mathbf{P}\mathbf{H})\\ \text{ with }\mathbf{X}=\left[\begin{array}{c}{\mathbf{X}}^{(1)}\\ \cdots \\ {\mathbf{X}}^{(V)}\end{array}\right]\text{ and }\mathbf{P}=\left[\begin{array}{c}{\mathbf{P}}^{(1)}\\ \cdots \\ {\mathbf{P}}^{(V)}\end{array}\right]\end{array}\text{\hspace{1em}(3)}$$其中$\mathbf{X}和\mathbf{P}$分别四多视角的观测值和与之对齐的重构模型
$L_h(.)$表示 与潜在(隐藏)表示所关联 的损失函数

一般来说，在多视角的互补性作用下，隐性表征比单独对应于单个视角的表征更具有综合性

基于潜在(隐藏)表示 $\mathbf{H}$ ,基于自表示的子空间聚类的目标函数式(1)重新表示为$$\underset{\mathbf{Z}}{\min }{L}_r(\mathbf{H},\mathbf{H}\mathbf{Z})+\alpha \Omega (\mathbf{Z})\text{\hspace{1em}(4)}$$其中$L_r(\cdot )$为数据重构相关的损失函数，Z为重构系数矩阵

将Eq.(3)中的潜在表示学习和Eq.(4)中的子空间聚类整合为一个统一的目标函数，如下所示$$\underset{\mathbf{P},\mathbf{H},\mathbf{Z}}{\min }{L}_h(\mathbf{X},\mathbf{P}\mathbf{H})+{\lambda }_1{L}_r(\mathbf{H},\mathbf{H}\mathbf{Z})+{\lambda }_2\Omega (\mathbf{Z})\text{\hspace{1em}(5)}$$ ${\lambda }_1和{\lambda }_2$平衡此三项

合理的潜在表示和子空间重构的约束保证了子空间聚类。而多视图的互补性保证了隐表示，并通过子空间重构改进了隐表示。考虑到离群点的鲁棒性，最终的目标函数如下$$\begin{array}{c}{\min }_{\mathbf{P},\mathbf{H},\mathbf{Z},{\mathbf{E}}_h,{\mathbf{E}}_r}{\Vert {\mathbf{E}}_h\Vert }_{2,1}+{\lambda }_1{\Vert {\mathbf{E}}_r\Vert }_{2,1}+{\lambda }_2\Vert \mathbf{Z}{\Vert }_{\ast }\\ \text{s.t. }\mathbf{X}=\mathbf{P}\mathbf{H}+{\mathbf{E}}_h,\mathbf{H}=\mathbf{H}\mathbf{Z}+{\mathbf{E}}_r\text{ and }\mathbf{P}{\mathbf{P}}^T=\mathbf{I}\end{array}\text{\hspace{1em}(6)}$$$||.|{|}_{\ast }$ 矩阵核范数，保证子空间的表示是低秩的.
$||.|{|}_{2,1}$即${\ell }_{2,1}\text{ -norm }$ ,尽可能使（encourage）矩阵的列为零，其定义为
$\Vert \mathbf{A}{\Vert }_{2,1}={\sum }_{j=1}^D\sqrt{{\sum }_{i=1}^C{\mathrm{A}}_{ij}^2}\text{ with }\mathbf{A}\in {\mathbb{R}}^{C\times D}$
潜在假设数据坏块是具体的样本的

约束P，因为在没有约束的情况下，H只能通过重新矫正 H/s和P_s (s > 0)来任意地趋近于零，同时保持相同的损失。

第一项被用来保证学习的潜表示H和重建模型P^(v)与不同的视角相关联，有利于重构 观测值
第二项惩罚 潜(隐藏)多视角子空间 重构的误差
最后一项通过使子空间的表示低秩，来避免平凡解

鲁棒性受益于两方面
一方面，因为多视角间互补的信息，相比于单视角，潜在子空间的表示可以更综合地描述数据
第二方面， 2，1 第一和第二项的核范数是matrix block norm（矩阵块规范？），这比Frobenius准则（范数）对异常值更稳健

更进一步，垂直连结了潜在表示和子空间表示相对应的误差列。在积分的方式上，它将使Eh和Er的列具有共同一致的量值，于是，目标函数有以下形式：$$\begin{array}{c}{\min }_{\mathbf{P},\mathbf{H},\mathbf{Z},{\mathbf{E}}_h,{\mathbf{E}}_r}\Vert \mathbf{E}{\Vert }_{2,1}+\lambda \Vert \mathbf{Z}{\Vert }_{\ast }\\ \text{s.t. }\mathbf{X}=\mathbf{P}\mathbf{H}+{\mathbf{E}}_h,\mathbf{H}=\mathbf{H}\mathbf{Z}+{\mathbf{E}}_r,\\ \mathbf{E}=\left[{\mathbf{E}}_h;{\mathbf{E}}_r\right]\text{ and }\mathbf{P}{\mathbf{P}}^T=\mathbf{I}\end{array}\text{\hspace{1em}(7)}$$参数$\lambda >0$平衡了误差和正则化项

3 Optimization

目标函数在从多视角学习潜空间的同时，找到了有意义的有关潜空间的相似矩阵。
尽管目标函数对于所有变量 $\mathbf{P},\mathbf{H},\mathbf{Z},{\mathbf{E}}_{\mathbf{h}},{\mathbf{E}}_{\mathbf{r}}$ 并不是凸的,它们中的每一个都可以通过固定其他的来有效地解决。
增广拉格朗日乘子(ALM) 和 交替方向最小化（ADM) 是解决问题的有效高效方法。
采用ADM策略来解决优化问题，要是目标函数是可分离的。因此，引入一个辅助变量 $\mathbf{J}$ 去替换目标函数中的核心项 $\mathbf{Z}$ 。有以下等价问题
$$\begin{array}{c}{\min }_{\mathbf{P},\mathbf{H},\mathbf{Z},{\mathbf{E}}_h,{\mathbf{E}}_r,\mathbf{J}}\Vert \mathbf{E}{\Vert }_{2,1}+\lambda \Vert \mathbf{J}{\Vert }_{\ast }\\ \text{s.t. }\mathbf{X}=\mathbf{P}\mathbf{H}+{\mathbf{E}}_h,\mathbf{H}=\mathbf{H}\mathbf{Z}+{\mathbf{E}}_r,\\ \mathbf{E}=\left[{\mathbf{E}}_h;{\mathbf{E}}_r\right]\text{ and }\mathbf{P}{\mathbf{P}}^T=\mathbf{I}and\mathbf{J}=\mathbf{Z}\end{array}\text{\hspace{1em}(8)}$$

上述目标函数可以通过最小化下面的ALM问题来求解
$$\begin{array}{rl}\mathcal{L}& \mathbf{P},\mathbf{H},\mathbf{Z},{\mathbf{E}}_h,{\mathbf{E}}_r,\mathbf{J})\\ & =\Vert \mathbf{E}{\Vert }_{2,1}+\lambda \Vert \mathbf{J}{\Vert }_{\ast }\\ & +\Phi \left({\mathbf{Y}}_1,\mathbf{X}-\mathbf{P}\mathbf{H}-{\mathbf{E}}_h\right)\\ & +\Phi \left({\mathbf{Y}}_2,\mathbf{H}-\mathbf{H}\mathbf{Z}-{\mathbf{E}}_r\right)+\Phi \left({\mathbf{Y}}_3,\mathbf{J}-\mathbf{Z}\right)\\ \text{ s.t. }\mathbf{P}{\mathbf{P}}^T=\mathbf{I}& \end{array}$$

definition: $\Phi (\mathbf{C},\mathbf{D})=\frac{\mu }{2}\Vert \mathbf{D}{\Vert }_F^2+⟨\mathbf{C},\mathbf{D}⟩$,其中$⟨.,.⟩$定义了矩阵的内积,$\mu$是一个正惩罚标量
为了使用ALM-ADM优化问题，问题分为以下几个子问题

1. P-subproblem

固定其他变量不变，只有P变化$$\begin{array}{l}{\mathbf{P}}^{\ast }=\arg \min \Phi \left({\mathbf{Y}}_1,\mathbf{X}-\mathbf{P}\mathbf{H}-{\mathbf{E}}_h\right)\\ \text{ s.t. }\mathbf{P}{\mathbf{P}}^T=\mathbf{I}\end{array}\text{\hspace{1em}(10)}$$

此优化的解决方法是使用${\mathbf{P}}^T=\mathbf{U}\mathbf{V},其中，\mathbf{U},\mathbf{V}$分别是$\mathbf{H}{\left({\mathbf{Y}}_1+\mathbf{X}-{\mathbf{E}}_h\right)}^T$的SVD分解后的左右奇异值，就有$$\begin{array}{l}{\mathbf{P}}^{\ast }=\arg \min \Phi \left({\mathbf{Y}}_1,\mathbf{X}-\mathbf{P}\mathbf{H}-{\mathbf{E}}_h\right)\\ =\arg \min \frac{\mu }{2}{\Vert \mathbf{X}-\mathbf{P}\mathbf{H}-{\mathbf{E}}_h+{\mathbf{Y}}_1\Vert }_F^2\\ =\arg \min \frac{\mu }{2}{\Vert \left(\mathbf{X}+{\mathbf{Y}}_1/\mu -{\mathbf{E}}_h\right)-\mathbf{P}\mathbf{H}\Vert }_F^2\\ =\arg \min \frac{\mu }{2}{\Vert {\left(\mathbf{X}+{\mathbf{Y}}_1/\mu -{\mathbf{E}}_h\right)}^T-{\mathbf{H}}^T{\mathbf{P}}^T\Vert }_F^2\end{array}$$
约束P为正交矩阵（$P{P}^T=I,P\in {\mathbb{R}}^{k\times d},k<<d$）,性能和收敛都得到了保障

2. H-subproblem

$$\begin{array}{rl}{\mathbf{H}}^{\ast }=\arg \min \Phi ({\mathbf{Y}}_1,\mathbf{X}& -\mathbf{P}\mathbf{H}-{\mathbf{E}}_h)\\ +& \Phi \left({\mathbf{Y}}_2,\mathbf{H}-\mathbf{H}\mathbf{Z}-{\mathbf{E}}_r\right)\end{array}$$
求导令其=0，得到$$\begin{array}{l}\mathrm{A}\mathrm{H}+\mathrm{H}\mathrm{B}=\mathrm{C}\\ \text{ with }\mathrm{A}=\mu {\mathrm{P}}^T\mathrm{P},\mathrm{B}=\mu \left({\mathrm{Z}\mathrm{Z}}^T-\mathrm{Z}-{\mathrm{Z}}^T+\mathrm{I}\right)\\ \mathrm{C}=\left({\mathrm{P}}^T{\mathrm{Y}}_1+{\mathrm{Y}}_2\left({\mathrm{Z}}^T-\mathrm{I}\right)\right)\\ +\mu \left({\mathrm{P}}^T\mathrm{X}+{\mathrm{E}}_r^T-{\mathrm{P}}^T{\mathrm{E}}_h-{\mathrm{E}}_r{\mathrm{Z}}^T\right)\end{array}$$
由Sylvester equation $AH+HB=C$ , A和 -B无公共特征根时，方程H有确切的唯一解

3. Z-subproblem

$${\mathbf{Z}}^{\ast }=\arg \underset{\mathbf{Z}}{\min }\Phi \left({\mathbf{Y}}_3,\mathbf{J}-\mathbf{Z}\right)+\Phi \left({\mathbf{Y}}_2,\mathbf{H}-\mathbf{H}\mathbf{Z}-{\mathbf{E}}_r\right)$$
求导令其=0$$\begin{array}{r}{\mathrm{Z}}^{\ast }={\left({\mathrm{H}}^T\mathrm{H}+\mathrm{I}\right)}^{-1}[\left(\mathrm{J}+{\mathrm{H}}^T\mathrm{H}-{\mathrm{H}}^T{\mathrm{E}}_r\right)\\ +\left({\mathrm{Y}}_3+{\mathrm{H}}^T{\mathrm{Y}}_2\right)/\mu ]\end{array}$$

4. E-subproblem

$$\begin{array}{rl}{\mathbf{E}}^{\ast }=& \arg \underset{\mathbf{E}}{\min }\Vert \mathbf{E}{\Vert }_{2,1}+\Phi \left({\mathbf{Y}}_1,\mathbf{X}-\mathbf{P}\mathbf{H}-{\mathbf{E}}_h\right)\\ +& \Phi \left({\mathbf{Y}}_2,\mathbf{H}-\mathbf{H}\mathbf{Z}-{\mathbf{E}}_r\right)\\ =& \arg \underset{\mathbf{E}}{\min }\frac{1}{\mu }\Vert \mathbf{E}{\Vert }_{2,1}+\frac{1}{2}\Vert \mathbf{E}-\mathbf{G}{\Vert }_F^2\end{array}$$
$\begin{array}{rl}& \text{ where }\mathrm{G}\text{ is formed by vertically concatenating the matrices }\\ & \mathrm{X}-\mathrm{P}\mathrm{H}+{\mathrm{Y}}_1/\mu \text{ and }\mathrm{H}-\mathrm{H}\mathrm{Z}+{\mathrm{Y}}_2/\mu .\end{array}$

5. J-subproblem

$$\begin{array}{rl}{\mathbf{J}}^{\ast }& =\arg \underset{\mathbf{J}}{\min }\lambda \Vert \mathbf{J}{\Vert }_{\ast }+\Phi \left({\mathbf{Y}}_3,\mathbf{J}-\mathbf{Z}\right)\\ & =\frac{\lambda }{\mu }\Vert \mathbf{J}{\Vert }_{\ast }+\frac{1}{2}{\Vert \mathbf{J}-\left(\mathbf{Z}-{\mathbf{Y}}_3/\mu \right)\Vert }_F^2\end{array}$$
上述问题可以用奇异值阈值操作解决

6. Updating Multipliers

$$\{\begin{array}{l}{\mathbf{Y}}_1={\mathbf{Y}}_1+\mu \left(\mathbf{X}-\mathbf{P}\mathbf{H}-{\mathbf{E}}_h\right)\\ {\mathbf{Y}}_2={\mathbf{Y}}_2+\mu \left(\mathbf{H}-\mathbf{H}\mathbf{Z}-{\mathbf{E}}_r\right)\\ {\mathbf{Y}}_3={\mathbf{Y}}_3+\mu (\mathbf{J}-\mathbf{Z})\end{array}$$

优化中的H首先用随机化初始的块变量

5 个人整理：优化中用到的数学

(AB)^T=B^T A^T

Augmented Lagrange Multiplier(ALM)

增广拉格朗日乘子法
https://blog.csdn.net/deepinc/article/details/79344981

增广拉格朗日乘子法（Augmented Lagrange Method），是用于解决等式约束条件下的优化问题。相对于朴素拉格朗日，它增加对偶上升法的鲁棒性和放松函数f的强凸约束，使得转换后的问题能够更容易求解，不至于因条件数变大不好求

在朴素拉格朗日形式上加上一个惩罚项$\frac{\rho }{2}\Vert \phi (x){\Vert }_2^2$$$\begin{array}{l}\min f(x)\\ \text{ s.t. }\phi (x)=0\end{array}\}\Rightarrow L(x,\lambda )=f(x)+\lambda \phi (x)+\frac{\rho }{2}\Vert \phi (x){\Vert }_2^2,其中惩罚因子\rho >0$$
更新迭代：
$$\begin{gathered} 1.假设{\lambda }^k为当前k轮迭代的对偶问题最优解 \\ 2.求解x^{k+1}:x^{k+1}=argmi{n}_{x}L(x,{\lambda }^k),其中L(x,\lambda )定义如上式 \\ 3.梯度上升法更新\lambda :{\lambda }^{k+1}={\lambda }^k+\alpha \cdot {\frac{\partial L(x,\lambda )}{\partial \lambda }|}_{x=x^{k+1},\lambda ={\lambda }^k} \end{gathered}$$

Alternating Direction Minimizing（ADM)

交替方向最小化

ADMM(Alternating Direction Method of Multipliers)

https://blog.csdn.net/shanglianlm/article/details/46808793

ADMM是一个旨在将对偶上升法的可分解性和乘子法的上界收敛属性融合在一起的算法。

SVD分解（奇异值）&EVD分解（特征值）

https://www.cnblogs.com/endlesscoding/p/10033527.html
讲得 好清楚！！！

Sylvester equation

西尔维斯特方程，控制理论中的矩阵方程

定义

$$AX+XB=C$$

其中$A、B及C$ 是已知的矩阵，问题是要找出符合条件的$X$ 。其中所有矩阵的系数都是复数。为了要使方程成立，矩阵的行和列需要满足一定条件，$A和B$ 都要是方阵，大小分别是 $n和m$ ，而$X和C$要是 $n行m$ 列的矩阵，$n和m$ 也可以相等，四个矩阵都是大小相同的方阵。
西尔维斯特方程有唯一解 $X$ 的充分必要条件是 $A和-B$没有共同的特征值。
$AX+XB=C$ 也可以视为是（可能无穷维中）巴拿赫空间中有界算子的方程。此情形下，唯一解X的充份必要条件几乎相同：唯一解 $X$ 的充份必要条件是$A和-B$的谱互为不交集

解的存在及唯一

Roth消去规则

假设二个大小分别为$n和m$的方阵$A和B$，以及大小为$n乘m$的矩阵$C$，则可以确认以下二个大小为$n+m$的方阵$$\left[\begin{array}{ll}A& C\\ 0& B\end{array}\right]和\left[\begin{array}{ll}A& 0\\ 0& B\end{array}\right]$$是否彼此相似。这二个矩阵相似的条件是存在一矩阵$X使得AX-XB=C$，换句话说，$X$为西尔维斯特方程的解，这称为Roth消去法则（Roth’s removal rule）。
可以用以下方式检查，若AX-XB=C，则$$\left[\begin{array}{cc}{I}_n& X\\ 0& I_m\end{array}\right]\left[\begin{array}{cc}A& C\\ 0& B\end{array}\right]\left[\begin{array}{cc}{I}_n& -X\\ 0& I_m\end{array}\right]=\left[\begin{array}{cc}A& 0\\ 0& B\end{array}\right]$$
Roth消去法则无法延伸到巴拿赫空间中的无穷维有界算子中

矩阵的求导

范数求偏导：https://blog.csdn.net/txwh0820/article/details/46392293

矩阵求导：https://zhuanlan.zhihu.com/p/24709748

迹求导1：https://www.cnblogs.com/Lxk0825/archive/2004/01/13/13987066.html

迹求导2：https://zhuanlan.zhihu.com/p/59133643