低秩和稀疏分离的模型推导

综述

低秩和稀疏分离的模型又有一个说法叫鲁棒的主成分分析(Robust Principal Component Analysis)，简称RPCA。
RPCA
在上图中低秩矩阵就是对应矩阵中的主成分，而sparse error matrix就是稀疏成分。RPCA在信号处理中有着很多实际的应用。
rpca_application
上图中两个典型的应用分别是视频中的背景建模和人脸图像去阴影。在监控视频中，背景往往是固定不动的，是对应视频中的主成分，而运动部分在每一帧图像中所处的位置不同，并且所占比例很小，可以看作是稀疏成分。人脸图像去阴影，是对多张同一人脸进行去阴影，而每一张人脸图像中的阴影比例较小，并且分布的位置不同，所以阴影部分就是稀疏成分，而无阴影图像对应主成分。因此，这两个应用都可以通过RPCA来进行建模处理。注意上述的稀疏成分更多是经验性的描述，并没有给出明确的数学定义，具体的定义在文献中也没有给出，具体问题应该具体分析吧。

RPCA数学建模及求解

这篇博客中介绍的是典型的RPCA数学建模方法，也是在这篇论文中“Robust Principal Analysis ?”提出的RPCA凸优化模型。这里应该注意RPCA分析的具体操作流程是首先把每一帧图像或者每一张图片进行了列向量化，然后把列向量按列排在一起，这样便构成了RPCA中的矩阵。对应的数学模型是：
$$M=L_0 + S_0$$
其中$M$对应的是列向量化的矩阵，$L_0$则对应的是矩阵中的低秩成分，$S_0$是稀疏成分。上述问题可以建模为：
$$ \text{min} \quad rank(L) + ||S||_0 \quad \text{s. t.} \quad M = L + S $$
模型的直观解释是主成分是低秩的，稀疏成分的非零元更少，所以对两者之和进行最小化求解就可以得到低秩和稀疏成分。但是，上述模型是非凸的，为了转化为凸优化模型求解的问题，需要进行凸松弛（凸放缩），把$rank(L)$转化为核范数$||L||_\ast$即奇异值之和，零范数转化为1范数。那么凸放缩后的数学模型是：
$$\text{min} \quad ||L||_\ast + || S ||_1 \quad \text{s. t.} \quad M = L + S $$
求解该模型的常用方法是Alternating Direction Method of Multipliers(ADMM)算法。首先写出模型的增广拉格朗日式子：
$$l(L,S,Y) = ||L||_\ast + \lambda ||S||_1 + \langle Y,M-L-S \rangle +\frac{\mu}{2}||M-L-S||_F^2$$，
ADMM 算法的更新公式为：
$$L_{k+1} = \text{arg min}_L ||L||_\ast + \frac{\mu}{2} ||M-L-S_k+\frac{Y}{\mu}||_F^2 \\
S_{k+1} = \text{arg min}_S \lambda ||S||_1 + \frac{\mu}{2} ||M-L_k-S+\frac{Y}{\mu}||_F^2 \\
Y_{k+1} = Y_k + \mu (M-L_k-S_k)
$$
关于ADMM算法会在下一篇博客中进行介绍。
其中$L$的更新式子可以简化为求解如下问题
$$\text{arg min}_X \frac{1}{2}||X-Y||_F^2 + \tau ||X||_\ast$$
由于该问题是凸问题因此最小值的解唯一，我们假设其解为$\hat{X} = \mathcal{D}_{\tau}(Y)$，其中$\mathcal{D}_{\tau}(Y)=U\mathcal{S}_{\tau}(\Sigma)V^T$，截断操作$\mathcal{S}_{\tau}[x] = \text{sgn}(x)\text{max}(|x|-\tau,0)$。下面我们需要证明$\hat{X}$为该凸问题的解。这里只需要证明下式成立：
$$Y- \hat{X} \in \tau \partial ||\hat{X}||_\ast$$
假设矩阵$Y$可以分解成$Y=U_0\Sigma_0 V_0^T + U_1\Sigma_1 V_1^T$，其中$\Sigma_0$奇异值大于$\tau$，$\Sigma_1$奇异值小于$\tau$。因此我们可以得到
$\hat{X} = U_0 (\Sigma_0 -\tau I)V_0^T$，$Y-\hat{X} = \tau (U_0 V_0^T + W), W=\frac{1}{\tau} U_1 \Sigma_1 V_1^T$核范数导数的定义是一个集合，即

$$\partial ||E||_\ast = \lbrace A B^T + D : A^TD=\mathbf{0}, DB= \mathbf{0}, ||D||_2 \leq 1 \rbrace$$

令$A=U_0, B=V_0, D=W$，由Y的SVD分解定义可知：$U_0^T U_1=\mathbf{0}$，因此，$A^TD=\mathbf{0}, DB= \mathbf{0}$。又因为$\Sigma_1$奇异值小于$\tau$，所以$||D||_2 \leq 1$。结论$Y-\hat{X} \in \tau \partial ||\hat{X}||_\ast$得证。
更新$S$的式子只需要进行求导就可以得到解，在此不再赘述，需要注意的是$||X||_1$是各元素的绝对值之和，因此求导时需要注意。
最后的更新算法即:

RPCA_algorithm