矩阵低秩分解理论

矩阵低秩分解理论及其应用分析

成科扬 2013年9月4日

从稀疏表示到低秩分解 稀疏表示

压缩感知(Compressed sensing)

从稀疏表示到低秩分解 矩阵低秩分解

observation

low-rank

sparse

矩阵低秩稀疏分解(Sparse and low-rank matrix decomposition) 低秩矩阵恢复(Low-rank Matrix Recovery) 鲁棒主成分分析(Robust principle component analysis, RPCA) 低秩稀疏非相干分解(Rank-sparsity incoherence)

预备知识

低秩矩阵恢复(鲁棒主成分分析RPCA) 在许多实际应用中，给定的数据矩阵D往往是低秩或近似低 秩的，但存在随机幅值任意大但是分布稀疏的误差破坏了原 有数据的低秩性，为了恢复矩阵D的低秩结构，可将矩阵D 分解为两个矩阵之和，即D=A+E,其中矩阵A和E未知， 但A是低秩的。当矩阵E的元素服从独立同分布的高斯分布 时，可用经典的PCA来获得最优的矩阵A,即求解下列最优 化问题： 当E为稀疏的大噪声矩阵时，问题转化为双目标优化问题： 引入折中因子λ,将双目标优化问题转换为单目标优化问题：

RPCA的求解 凸松弛NP难问题 松弛后

矩阵核范数

迭代阈值算法(iterative thresholding,IT)将最优化问题正则化，便得到优化问题： 优化问题式的拉格朗日函数为

使用迭代阈值算法交替更新矩阵A,E和Y。当E=Ek,Y=Yk时，

当A=Ak+1,Y=Yk时，

当A=Ak+1 ,E=Ek+1时， 其中：步长δk满足0< δk <1 IT算法的迭代式形式简单且收敛，但它的收敛速度比较慢，且难以选取合适的步长

加速近端梯度算法(acceleratedAPG)

proximal gradient,

将优化问题式的等式约束松弛到目标函数中，得到如下的拉格朗日函 数： 记 于是L(A,E,μ)=g(A,E,μ)+f(A,E)。函数g(A,E,μ)不可微，而f (A,E)光滑且具有李普希兹连续梯度，即存在Lf>0,使得其中： 表示函数f(A,E)关于矩阵变量A和E的Fréche t梯度。此处取Lf =2。对于给定的与D同型的两个矩阵YA和YE,作 L(A,E,μ)的部分二次逼近：

加速近端梯度算法(acceleratedgradient,APG)

proximal

为了得到更新YA和YE时的步长，需先确定参数tk+1: 于是YA和YE的迭代更新公式为:

参数μ的迭代公式为 其中： 为事先给定的正数；0<η<1。 尽管APG与IT算法类似，但它却大大降低了迭代次数。

对偶方法(DUL) 由于核范数的对偶范数为谱范数，所以优化问题的对偶问题 为： 其中： 表示矩阵元素绝对值最大 的值。当优化问题对偶式取得最优值 时，必定满足 即此优化问题等价于： 上述优化问题是非线性、非光滑的，可以使用最速上升法求 解

。当 时，定义正规锥 其中 表示函数J(.)的次梯度。此时，优化问题的最速 上升方向为Wk=D-Dk,其中Dk为D在N(Yk)上的投影。 使用线性搜索方法确定步长大小： 于是Yk的更新过程为 DULL比APG算法具有更好的可扩展性，这是因为在每次迭 代过程中对偶方法不需要矩阵的完全奇异值分解。

增广拉格朗日乘子法(augmentedmultipliers,ALM) 构造增广拉格朗日函数：

Lagrange

当Y=Yk,μ=μ k ,使用交替式方法求解块优化问题 min A,E L(A,E,Yk,μ k )。 使用精确拉格朗日乘子法交替迭代矩阵A和E,直到满足终止条件为 止。若 则

再更新矩阵E:

记

分别收敛于

,则矩阵Y的更新公式为

最后更新参数μ:

其中：ρ>1为常数；ε>0为比较小的正数。

交替方向方法(alternatingmethods,ADM,IALM)

direction

ADM对ALM做了改善，即不精确拉格朗日乘子法(inexactALM 它不需要求 的精确解，即矩阵A和E的迭代更 新公式为：

求解方法性能比较

低秩矩阵恢复应用 图像恢复

低秩矩阵恢复应用 图像去光照影响恢复