(3条消息) Learning Robust Low
Learning Robust Low-Rank Representation (2012)
注释：
本篇主要学习LRR和online LRR理论。本文由RPCA的提出讲起；再叙述论文提出的online RPCA数学解析以及insight；最终阐述如何与神经网络结合，构成可训练的online RPCA regressor。
论文梗要：
主要采用稀疏表示的非凸方法，来得到数据鲁棒的低秩表示，并提出了高速的在线训练方法。涉及的主要内容包括：字典学习、鲁棒PCA、设计可训练的编码器获得近似估计。
提炼主要的几个优化问题：
正文
一、 关于PCA
（1） 原始数据矩阵
，由于观测噪声的存在，可以简化为以下两个部分组成：
其中：L是一个低秩矩阵，N是一个扰动矩阵（perturbation matrix）
（2） 理想状态下PCA能提取数据的前K次分量，得到低秩表达
（3）然而，PCA对不符合它模型设想的数据，十分敏感，无法克服异常样本点的存在所造成的影响。
（4）PCA的噪声敏感性导致了鲁棒PCA研究的出现。
二、 关于鲁棒PCA
（1） 鲁棒PCA的基本观点是：将原始数据矩阵，分解成稳定部分和扰动部分的前提下，增加一个误差项O，如下：
其中 O是误差矩阵，O中存在稀疏的任意大小的非零系数（所以假设为outlier的存在形式同样是稀疏的？）。
（2）改进的PCA模型就变成:
a.
表示矩阵核范数（矩阵奇异值的总和的总和）
b.
作为非零标量，控制着outlier的稀疏水平
c.
控制误差估计上界
（3）而在无噪声设定的情况中（noiseless setting），数据矩阵限制条件则退化为
（4）在解决有无噪声设定的RPCA优化问题（目标函数2）方面，取得的不错的进展，但是依然存在过高的算法复杂度问题，实时性能不足。进展包括：
a. 当数据集规模合适时，first-order优化方法（一阶线性多项式，见Wikipedia）以及拓展的拉格朗日方法。
b. 利用投影方法获得有效的降维。
c. 将原矩阵分解成维度较小的非凸结构问题。
d. 深度学习方面，在训练得到稀疏编码上有长足进展。但是深度学习在RPCA的应用上未有工作。
（5）由于RPCA的迭代涉及到SVD，因此在实时性应用上，RPCA和标准的稀疏编码不同，作者对此进行了RPCA编码器的设计。
（6）作者通过incorporating learning实现在实际信号与RPCA之间的跨越（即改变设计的RPCA编码器的训练损失函数）。
三、 RPCA via non-convex factorization方法
（1） 优化目标函数改写
改写成：
因为，对于不同的非负数
，我们都可以找到
，使得两种目标函数得到相同的解。因此，从这个意义上而言，目标函数1和目标函数2是等效的。
（2） 优化过程引入核范数的作用
核范数在矩阵低秩表达方面有重要的作用。与本文相关的定理，有以下几个内容：
a. 首先是一个SVD相关的：给定原m*n矩阵为L，L可分解为：
其中：
b. 且若存在，使得：
c. 那么，对于这个最优化问题：
d. 该矩阵分解目标函数，最小化的解，可以由SVD过程获得。解为：
e. 相应的，RPCA模型可以写作
（3） 其中，关于L的分解方式
，从字典学习进行考虑，以便对该模型的稀疏编码得到更透彻的理解：
a. U可以看成一个待完成的字典，U含有n个原子元素（每列代表一个元素）
b. S在每个列中，包含了X中各个数据向量（每列）之间的相关系数。
c. 因此，以上的矩阵分解过程，可以看成字典学习的过程。
d. 基于此，本算法可以往字典学习的稀疏建模领域靠拢。Online dictionary learning for sparse coding
e. 将求解过程的变量从2*n*m减少为q*（n+m）
f. 但优化问题变成了非严格凸问题；好在优化模型（4）中，任何满足
的驻点
都是每次迭代的最优解。（证明？二阶导是半正定？见Unveiling anomalies in large-scale networks via sparsity and low rank）
g. 有了定理f，优化过程就可以通过交替迭代优化或者Block Coordinate方法（wiki介绍见下图）（就是EM吧？）
四、 RPCA的新样本点投影方法
现在考虑一个新问题，凭借已有的数据来获得模型，这样获得的样本整体模型是不够的，因为数据流一直在输入输出，数据永远在改变，我们也需要考虑：如何衡量新采样点该如何投影，以去除噪声影响？
a. 首先， 关于样本整体，我们已有估计模型
b. 但是，怎么进行RPCA的更新（新采样到的数据点，对已有模型参数进行合理的更新）？
（1）符号定义：
基于一个经验假设：新采样点x与X相互aligned，也就是x可能来自和X同样的分布。换句话说，x可能是有先验的（a priori）。
注意：这个采样假设是online RPCA的重要基础；实际上，实际应用中有的情况是不符合这个假设的，但是这里我们认为，面对的数据，都是有先验可循的。
其中，n是来自采样的微小扰动，o是稀疏outlier。
（2） 模型的采样更新：
关于单个新采样点，我们在原先字典元素矩阵U取定的情况下，不再规一化处理U的每个列（unit norm column）。
相较而言，我们更关注字典关系向量s，因为s在估计中衡量着在数据所在低秩空间里，字典元素之间的相关性。
基于此，可以拓展模型为
相比优化问题4，优化问题5对待U是有所区别的。
本文的重点贡献，后文编码器也是依此而设计
（3） 模型5是一个凸优化问题，有很多解决方法。为了使得改编码器可训练，文中采用EM迭代方法：
，
其中
是关于
的阈值函数，它赋阈值给每一个输入向量的每一个成分。
（4）在online模型获得关于某一次新采样点的投影表征{st,ot}更新后，我们再对字典矩阵Ut进行该时刻的更新
解决优化问题8的方法主要有两种：
a. 一种是根据之前若干次时序，以bias或variance最小化为目标，进行当次状态更新的recursive method（系统辨识有讲）；或者使用前面说的BCD方法分参数求解;
b. 另一种就是直接解方程9
c. recursive method一般来说，计算复杂度比较低，但是对于大规模问题，需要内存较大。所以，要根据应用要求，再确定是否采用recursive方法。（疑问：这里的大规模指的是数据维度过高，还是指数据流太长，导致更新时间长度太长？如果是后者，那么，对于大规模的数据量，把更新时间窗口长度限定在指定范围内不也是系统辨识的一种有效办法吗？）
五、关于模型5的附加内容
再进一步假设
a. 对数据的秩上界估计q是正确的
b. 矩阵
也已经是优化问题4的驻点
c. 满足
，
，
d. 为了符号的不失一般性，假设矩阵L的秩严格等于q
我们以此，对优化问题5进行改动，更一般化地方便我们理解该投影模型5。
a.
是L的奇异值矩阵
b. 把U的估计改形式为：
c. 相应的，s改写形式为：
d. 整体改写为：
e. 此时，我们的优化目标从{s，o}转移为{w，o}
根据以上变化，模型可以修改成：
其中第二项
显示：投影向量w的系数是根据L的主方向进行更新的。
六、如何设计online RPCA的 {s,o} encoder和 {U} encorder
（1）{s,o} RPCA encoder：
a. 定义：在基于字典矩阵U已经给定的情况下，对数据的投影{s，o}进行参数回归过程。
b. 编码器的更新：
效仿LeCun的快速稀疏编码方法，建立前馈机制，并基于我们得到的online RPCA模型EM优化过程，使用SGD对{s,o}进行更新，如图所示。
c. 总结一下编码器：
每层编码器都包含一个非线性操作
的和线性操作
，优化过程类似EM，多了一个可选的软阈值参数
，以促进对编码器的提升。（留有疑问：去除
性能会下降多少？
是否是一个必要因素？）
（2）{U} encoder
作者把online RPCA regressor中U的迭代过程，称为 the online adaptation of the dictionary。其损失正如前面的模型8所示。
因此，训练过程中，我们可自主选择进行优化字典调整{U}或是投影过程{s, o}。
同时，模型8也再次贴合了假设：数据是有先验的。
七、不同样本情况下，如何设计损失函数
（1） 记得前面强调了本文的一个重要假设：数据是有先验的。符合这个假设的数据，我们可以直接训练。
此时，用经验主义方法，对编码器的输出
定义损失计算即可。
如：
MSE，
等。
（2）但是，对于不符合这个假设的数据，我们需要对损失函数进行改动，对训练过程做些预处理。
作者提了两种提升方法。
第一种是为参数增加监督：
作者把前人完成的 “歌声和伴奏的音频分离” 实验作为例子：
a. 歌手歌声在音频中占据的成分较高，而主导了音频的成分。
b. 背景伴奏可以被认为低秩的outlier。
c. 前人简单地使用RPCA可以进行音频分割，不过得到的结果谈不上理想。
分析中，音频中歌声和伴奏分别主导了s和o。训练过程，加入真实的纯歌手声音投影s*、和真实的纯背景音乐o*，对编码器参数进行监督，实际上效果会更好。
第二种是进行预处理，使得数据从不对齐变成对齐：
比较典型的就是人脸建模。CVPR的一篇文章Robust alignment by sparse and low-rank decomposition for linearly correlated images中指出了：只有当数据集的面部图像都是像素对齐的情况下，人脸图像才存在低纬模型。即使是再小的未对准，都会导致US的低维的秩数增加、outlier矩阵O也失去稀疏性，所以，人脸的表征会迅速被破坏。
下图为简单的人脸训练实验最终结果。
其中，训练过程分别使用的损失函数为：关于s和o的监督L2 loss、U的L2+L1 loss、损失函数11的f(x,z)。
第一列是原图像Us+o，第二列是低秩估计的图像Us，第三列是噪声o。
下方一列数字表示为f(x,z)损失的大小。
实验结果表明：图像训练样本优化对齐后，所得到的人脸低秩估计是最好的。
基于此，Regressor的损失函数更一般化地改进为：
定义了映射过程
，增加了序列
，对输入样本
进行预先的对齐映射。
以上，文旁主要的insight和contribution已整理完毕。