本文共 2226 字，大约阅读时间需要 7 分钟。

 

 

1:矩阵的填充问题。 

矩阵填充问题,考虑的是采样得到的一个矩阵，这个矩阵并不是完整的，只能得到一部分的元素。如何利用已有的元素，去把未知的元素给填充完整。不是说任意不完全的矩阵都可以直接填充的，现有的算法必须要求这个矩阵是有信息冗余的，换句话说必须要求这个矩阵是低秩的。  那么就是解决如下优化问题： min:Rank(X) min:Rank(X) s.t:Xij=Mij s.t:Xij=Mij

其中MijMij 是已经采样的矩阵。 

对于这种问题 Rank(X)Rank(X) 的最小。由于其是NP问题。所以想着用其他范数去替代。首先想到的是0范数，非0的元素的个数。最小化0范数，希望XX 的大部分元素都是0。这很好啊，可是遗憾的是这也是NP问题。于是又有1范数来近似替代0范数。1范数是0范数的近似替代，而且1范数是凸的，对于问题的解决比较容易，而且得到的结果也比较好。  那么问题变为解决如下优化问题： min:||X||1 min:||X||1 s.t:Xij=Mij s.t:Xij=Mij

此问题的算法有几种。 

1) 奇异值阈值：可以理解为拉格朗日乘子法。考虑问题的近似解 min:a||X||1+1/2||X||2F min:a||X||1+1/2||X||F2 s.t:P(X)=P(M) s.t:P(X)=P(M) ,其中相当于在目标函数加了一个规则项。当aa比较大的时候，那么很显然可以近似原问题的解。f范数一般能保证所求的解过度拟合。然后利用拉格朗日函数 L(X,λ)=a||X||1+1/2||X||F+<λ,P(X)−P(M)> L(X,λ)=a||X||1+1/2||X||F+<λ,P(X)−P(M)> 那么利用交替迭代的思想来计算 X,λX,λ。即是： X=argminL(X,λk) X=argminL(X,λk) λk+1=λk+t(k)(P(X)−P(M)) λk+1=λk+t(k)(P(X)−P(M)) 其中t(k)t(k) 为步长。  接下来就是来计算X=argminL(X,λk)X=argminL(X,λk) 值得一提的是计算过程中，需要迭代的进行奇异值分解，算法中，设计一个阈值，当奇异值小于这个阈值的时候，让它为0。这也就是奇异值阈值算法。  2) Proximal Gradient:此算法求解的是无约束问题形如 min:F(X)=f(x)+g(x) min:F(X)=f(x)+g(x) 其中f(x)f(x)是凸的光滑即要求连续可微，g(x)g(x)是凸的。然后我们用f(x)=f(Y)+<∇f(Y),X−Y>+L/2||X−Y||2Ff(x)=f(Y)+<∇f(Y),X−Y>+L/2||X−Y||F2 其中LL为f(x)f(x) 满足的利普希茨常数。所以问题转换为求 Q(X,Y)=f(Y)+<∇f(Y),X−Y>+L/2||X−Y||2F+g(x) Q(X,Y)=f(Y)+<∇f(Y),X−Y>+L/2||X−Y||F2+g(x) 的最小值问题。也是利用交替迭代的思想去求解。当然此算法得到很大改进，出现Accelerated Proximal Gradient。比较常用的是在每次迭代的过程中，也按照一定方式来更新L。  那么对于填充问题可以近似来求解以下问题 minF(X)=1/2||P(M−X)||2F+a||X||1 minF(X)=1/2||P(M−X)||F2+a||X||1 当aa 比较大时可以看为近似解。那么可以按照上面介绍的方法进行求解。  2：矩阵的重建问题。又称为Robust PCA。即是有一个高维的数据，可以投影到低维空间上去。传统的PCA，主成分分析法，直接进行SVD分解，舍掉小奇异值，既可以达到这种目的。但是实际上发现，当这个矩阵很大，并且受到污染很严重的时候，运用传统的PCA方法，效果往往不理想。这个时候提出了RPCA。  RPCA的问题是 min:||A||∗+λ||E||1 min:||A||∗+λ||E||1 s.t.:D=A+E s.t.:D=A+E

解决此问题，可以按照上面介绍的两中方法进行求解。我们介绍一下比较流行的IALM(inexact augment Lagrange multiplier)。 

首先写出增广拉格朗日函数 L(A,E,Y,μ)=||A||∗+λ||E||1+<Y,D−A−E>+μ/2||D−A−E||2F L(A,E,Y,μ)=||A||∗+λ||E||1+<Y,D−A−E>+μ/2||D−A−E||F2 其中Y是线性约束乘子。μμ 是惩罚项。  经典的ALM是按照如下方法迭代更新求解的： (Ak+1,Ek+1)=argminL(A,E,Yk,μ) (Ak+1,Ek+1)=argminL(A,E,Yk,μ) Yk+1=Yk+μ(D−Ak+1−Ek+1) Yk+1=Yk+μ(D−Ak+1−Ek+1) 同时更新A,EA,E 使问题收敛的较慢。  所以有人提出了交替方向法(ADM)，来分别迭代子问题的解。最后得到问题的解。即为： Ak+1=argminL(A,Ek,Yk,μ) Ak+1=argminL(A,Ek,Yk,μ) Ek+1=argminL(Ak+1,E,Yk,μ) Ek+1=argminL(Ak+1,E,Yk,μ) Yk+1=Yk+μ(D−Ak+1−Ek+1) Yk+1=Yk+μ(D−Ak+1−Ek+1)

 

转载地址：http://rgxgi.baihongyu.com/