1. 1 为什么使用RPCA?
求解被高幅度尖锐噪声而不是高斯分布噪声污染的信号分离问题。
1.2 主要问题
给定C = A*+B*, 其中A*是稀疏的尖锐噪声矩阵，B* 是低秩矩阵, 目的是从C中恢复B*.
B*= UΣV’, 其中U∈Rn*k,Σ∈Rk*k,V∈Rn*k
3. 与PCA的区别
PCA和RPCA 的目的都是矩阵分解, 然而,
对于PCA, M = L0+N0,L0:低秩矩阵 ; N0: 小的idd Gaussian噪声矩阵, 通过最小化||M-L||2 且满足条件rank(L)<=k来搜索L0的最好秩k估计.通过SVD可以解决这个问题.
对于RPCA, M = L0+S0,L0:低秩矩阵 ; S0: 稀疏尖峰噪声矩阵,接下来将给出具体的求解过程.
2. 正确分解的条件
4. 病态问题:
假设稀疏矩阵A*和B*=eiejT是分解问题的解.
1) 假设B* 不仅低秩而且稀疏, 可找到另一个稀疏加低秩分解A1= A*+eiejT和B1= 0, 因此, w我们需要对低秩有一个合理的认识确保B* 不是太稀疏. 稍后附加条件需要由奇异向量U和V所张成的空间 (也就是B*的行列空间)与标准基“不连贯” 。
2) 相似地, 假设A* 是稀疏且低秩的 (例如A*的第一列非零, 其他列为0, 则 A* 秩为1且是稀疏的). 可找到另一个有效的分解 A2=0,B2= A*+B* (这里秩(B2) <= 秩(B*) + 1). 因此我们需要限制稀疏矩阵不应该是低秩的.即, 假设每一行/列不应该有太多的非零元素 (不存在稠密的行/列), 避免这种情况发生.
5. 正确恢复/分解的条件:
如果A* 和B* 来自于这些类时, 则可以高概率获得精确恢复[1].
1) 对于低秩矩阵L—随机正交模型[Candes andRecht 2008]:
以如下方式构建秩k矩阵B* 其SVD分解为B*=UΣV’ : 奇异向量U,V∈Rn*k来自于对Rn*k 中秩k偏等距算子的简单随机抽样. U和V的奇异向量不需要相互独立. 对奇异值无任何约束.
2) 对于稀疏矩阵S—随机稀疏模型:
矩阵A* 使得支撑(A*) 随机等可能地采样于尺度m的所有支撑集合中. There is no assumption made about the values of A* at locations specified by support(A*).
[Support(M)]: M中非零元素的位置
Latest[2]improved on the conditions and yields the ‘best’ condition.
3. 恢复算法
6.Formulization
对于分解D = A+E,其中A是低秩误差E是稀疏的.
1) 凭直觉提出
min rank(A)+γ||E||0, (1)
然而这时非凸的，因此难于处理 (两者是NP-hard需要近似处理).
2) 放松条件L0-范数至L1范数，，用核范数代替秩
min||A||*+ λ||E||1,
where||A||*=Σiσi(A) (2)
这是凸的, 也就是存在唯一的最小值解.
理由: 注意到||A||*+ λ||E||1 是rank(A)+γ||E||0在满足条件max(||A||2,2,||E||1, ∞)≤1上的集合(A,E)的凸包.
此外, there might be circumstances under which (2) perfectly recovers low-rank matrix A0.[3] shows it is indeed true under surprising broad conditions.
7.求解RPCA 的优化算法
采用两种不同的方法求解. 第一种方法, 直接使用一阶方法求解邻近问题.(E.g. 邻近梯度, 加速邻近梯度(APG)), 每一次迭代的计算瓶颈是一个SVD计算.第二种方法是将问题转换为对偶问题求解, 从对偶优化解中重新得到邻近解.RPCA的对偶问题为:
maxYtrace(DTY) , subject to J(Y) ≤ 1
其中J(Y) = max(||Y||2,λ-1||Y||∞). ||A||x指A的x范数.(无穷范数表示矩阵中绝对值最大的一个)。这个对偶问题可通过约束最速上升法求解.
现在讨论增广拉格朗日乘子法 (ALM)和交替方向法(ADM)[2,4].
7.1. ALM的一般方法
对于优化问题
min f(X), subj. h(X)=0(3)
定义拉格朗日函数:
L(X,Y,μ) = f(X)+<Y, h(x)>+μ/2||h(X)||F2 (4)
其中Y是拉格朗日乘子，μ 是正标量.
ALM的一般方法:
广义拉格朗日乘子算法通过重复令(Xk) = arg min L(Xk,Yk,μ)求解主成分追踪(principle component pursuit) ，则拉格朗日乘子矩阵Yk+1=Yk+μ(hk(X))
7.2 求解RPCA的ALM算法
在RPCA, 定义(5)式为
X = (A,E), f(x) = ||A||*+ λ||E||1, h(X) = D-A-E
则拉格朗日函数(6)
L(A,E,Y, μ) = ||A||*+ λ||E||1+ <Y, D-A-E>+μ/2·|| D-A-E ||F2
每一个成功者都有一个开始。勇于开始，才能找到成功的路。
