Robust-Rcovery-of-Subspace-Structure-by-Low-Rank-Representation精读笔记
Robust-Rcovery-of-Subspace-Structure-by-Low-Rank-Representation精读笔记
背景
论文链接：Robust-Rcovery-of-Subspace-Structure-by-Low-Rank-Representation
RPCA（鲁棒主成分分析）把一个观测到的数据分解成一个干净的数据矩阵和一个稀疏的噪声矩阵的和的形式。 \[ X = D + E \] 其中\(X\)是观测数据，\(D\)是要恢复的矩阵，\(E\)是稀疏的噪声矩阵。
因为一个好的图像往往是低秩的，因为高质量的图像往往是平滑的，行与行之间往往是线性相关的，这样就会出现低秩。所以\(D\)是一个低秩的矩阵。
可以通过秩最小化，来恢复出低秩矩阵\(D\)。 \[ \min_{D,\ E}\ rank(D) + \lambda||E||_l, \qquad s.t.X = D + E \] 取得令上述取最小值的\(D^*,\ E^*\) 就得到了低秩矩阵和离散的噪声矩阵。
上述的方法就是RPCA的主要思想。
这个方法有一个问题，现实中潜在的数据结构往往来自于多个子空间，但是上述的方法是基于数据的结构只是来自于一个子空间。这就会导致恢复出来的数据不精准。
解决措施
为了解决这个问题，作者引入了字典\(A\)，用\(AZ\)来表示低秩矩阵，这样就能把这个低秩矩阵看作是多个子空间的线性组合。 \[ \min_{Z,\ E}\ rank(Z) + \lambda||E||_l, \qquad s.t.X=AZ+E \] 取令上述公式取得最小值时的\(Z^*, \ E^*\)，由矩阵乘法的性质得出，\(rank(AZ^*) < rank(Z^*)\) ，所以恢复出来的矩阵，仍是低秩矩阵。
另外通过取字典\(A = I\)（\(I\)表示单位阵）则就是RPCA的方法。所以这里可以看作是RPCA的一个推广。
详细算法
低秩表示
因为秩函数不是唯一解，但是在一定条件下，核范数是秩函数的最佳凸松弛。而且作者想要处理的图像主要包含特定值缺失这种类型的错误。所以选择了\(l_{2,1}\) 。 \[ \min_{Z,\ E}\ rank(Z) + \lambda||E||_{2,1}, \qquad s.t. X = AZ + E \] 作者使用不精确拉格朗日乘子法（Inexact ALM）也叫交替方向乘子法（ADMM）来求最小值点。
交替方向乘子法（Alternating Direction Method of Multipliers）通常用于解决存在两个优化变量的只含等式约束的优化类问题
首先引入松弛变量\(J\)，便于用Singular Value Thresholding（SVT 奇异阈值法）求解\(Z\)，使得下面单独优化\(Z\)时，关于\(Z\)的损失函数足够简单。
这里可以参考了一篇博客凸优化实战1来理解\(J\)的作用。
然后写出增广拉格朗日函数： \[ L = ||J||_* + \lambda||E||_{2,1} + tr(Y_1^T(X - AZ - E)) + tr(Y_2^T(Z-J)) + \frac{\mu}{2}(||X-AZ-E||_F^2 + ||Z-J||_F^2) \] 然后按照下列步骤逐渐迭代得出\(Z^*, E^*\) 。
Step 1可由SVT（奇异值阈值）求解。
Step 3用以下引理求解。
子空间分割
通过上述步骤获得了\(Z^*,\ E^*\) 。通过下列步骤获取亲和矩阵\(W\)，之后把亲和矩阵放入谱聚类算法分割成k类。
估计子空间数目
获取了亲和矩阵\(W\)之后，根据下列步骤得出对称归一化拉普拉斯矩阵。
拉普拉斯矩阵是半正定矩阵，有m个非负特征值。利用它的性质——特征值为0的重数等于图连通分量的个数，来估计子空间数目。
但是低秩矩阵多少存在些噪声。所以提出了如下的软阈值算法来估计特征值近似0的重数，来估计子空间数目。
这里的\(n\)表示样本个数。这里的样本数目指的是行向量的个数，因为这里的子空间指的是行空间。
离群值检测
离群值检测有两个方法
通过获取的\(E^*\)的非零列来检测：
当\(||E||_{:,i} > \tau\)时，X的第i个分量被视为离群值。
通过亲和值来检测：
亲和度为0或者接近0的分量，被视为离群值。
实验
本人是一个刚入门的初学者，有很多地方表述不到位，另外有些结论的得出是根据直觉。如有不严谨的地方，请批评指正。
低秩恢复
这里我找了一些有一些强烈噪声的图像作为观测矩阵。分别使用RPCA和LRR算法处理。
通过实验四，我观察到RPCA在去除噪声的同时也会将图像上的一些信息也会去掉。LRR只是会去掉一些横竖向的噪点，不能恢复较为明显的损坏。
首先RPCA会出现上述结果的原因，是RPCA基于潜在的数据的结构只来自一个低秩子空间。所以恢复的低秩矩阵只会保留较大的子空间，也就是大面积的结构相似的部分，因为只有这样行向量之间线性相关程度更高，所以秩也就越低。因此就会去除很多图像原本包含的信息。
反观LRR，LRR在设计的时候针对上述问题做了改进，引入了字典A，让低秩矩阵表示为多个子空间的线性组合，这样就使得恢复出来的低秩矩阵可以包含较多子空间的信息，使得观测矩阵的大部分结构都得以保留。但是如果噪声较强，则仍可能保留噪声。
验证对图像结构的影响
我用Set 5数据集，随机对一些行和列产生缺失，来制作噪声图像。然后分别用RPCA和LRR处理。
通过实验五，发现RPCA处理过的图像的SSIM和PSNR都有明显的下降，说明RPCA在去除噪声的同时对图像原本的结构也有破坏，而LRR处理之后的图像SSIM与观测图像几乎相同，PSNR在有些情况下还有小幅提升。
验证\(\lambda\)的取值对结果的影响
输入仍是被处理过的Set 5数据集。\(\lambda = [0.01, 0.50,1.10,4.10]\)
经过对不同的\(\lambda\) 产生的结果对比，发现LRR算法对参数不敏感，\(\lambda\)对恢复出的图像质量影响不大。噪声图像差别较大的原因，是在获取了噪声图像之后，进行了归一化操作。我认为对\(\lambda\)不敏感的原因在于字典的选择，因为字典\(A\)是来自\(X\)。
| 耗时（S） | LRR | RPCA |
|---|---|---|
| Baby | 140.211 | 9.995 |
| Bird | 50.88 | 2.019 |
| Head | 49.015 | 1.985 |
| Woman | 36.01 | 1.786 |
| Butterfly | 46.08 | 1.883 |
LRR处理一幅较大的彩色图像的时间远大于RPCA处理的时间。
自带噪声的图像恢复
这里的数据是来自几个常见的人脸数据集。
通过实验七发现，LRR在恢复图像清晰度方面，比RPCA效果好很多。LRR和RPCA在调整图像过曝或过暗方面都有一定的效果，但是通过观察对镜片反光这一现象处理的效果，发现LRR算法作用不大，RPCA能够去除反光的大部分影响。说明在处理严重缺失时，LRR算法还有进步的空间。
结论
通过实验发现，LRR的优缺点如下：
优点：
- LRR算法恢复的低秩图像，能有效地保留图像的结构，能去除一部分噪声。
- 对\(\lambda\)的选择不敏感，在\(\lambda\)不同时，恢复出来的低秩图像质量差别不大。
缺点：
- 在噪声或者异常值严重的时候，无法正确去除。
- 处理图片时耗时较长。