矩阵低秩与分解理论 .ppt

矩阵低秩分解理论及其应用分析 成科扬 2013年9月4日 从稀疏表示到低秩分解 稀疏表示 压缩感知(Compressed sensing) 从稀疏表示到低秩分解 矩阵低秩分解 矩阵低秩稀疏分解(Sparse and low-rank matrix decomposition) 低秩矩阵恢复（Low-rank Matrix Recovery） 鲁棒主成分分析(Robust principle component analysis, RPCA) 低秩稀疏非相干分解(Rank-sparsity incoherence) 预备知识 低秩矩阵恢复（鲁棒主成分分析RPCA） 在许多实际应用中，给定的数据矩阵Ｄ往往是低秩或近似低秩的，但存在随机幅值任意大但是分布稀疏的误差破坏了原有数据的低秩性，为了恢复矩阵Ｄ的低秩结构，可将矩阵Ｄ分解为两个矩阵之和，即Ｄ＝Ａ＋Ｅ，其中矩阵Ａ和Ｅ未知，但Ａ是低秩的。当矩阵Ｅ的元素服从独立同分布的高斯分布时，可用经典的PCA来获得最优的矩阵Ａ，即求解下列最优化问题： 当Ｅ为稀疏的大噪声矩阵时，问题转化为双目标优化问题： 引入折中因子λ，将双目标优化问题转换为单目标优化问题： RPCA的求解 凸松弛 迭代阈值算法（iterative thresholding，IT） 将最优化问题正则化，便得到优化问题： 优化问题式的拉格朗日函数为 使用迭代阈值算法交替更新矩阵Ａ,Ｅ和Ｙ。当Ｅ=Ｅk，Ｙ=Ｙk时， 当Ａ＝Ａk+1，Ｙ＝Ｙk时， 当Ａ＝Ａk+1 ，Ｅ＝Ｅk+1时， 其中：步长δk满足０＜ δk ＜1 ＩＴ算法的迭代式形式简单且收敛，但它的收敛速度比较慢，且难以选取合适的步长 加速近端梯度算法（accelerated proximal gradient，APG） 将优化问题式的等式约束松弛到目标函数中，得到如下的拉格朗日函数： 记 于是L(Ａ,Ｅ,μ)=ｇ(Ａ,Ｅ,μ)+ｆ(Ａ,Ｅ)。函数ｇ(Ａ,Ｅ,μ)不可微，而ｆ(Ａ,Ｅ)光滑且具有李普希兹连续梯度，即存在Lf＞0，使得 其中： 表示函数ｆ(Ａ,Ｅ)关于矩阵变量Ａ和Ｅ的Ｆｒéｃｈｅｔ梯度。此处取Lf =２。对于给定的与Ｄ同型的两个矩阵ＹA和ＹE，作Ｌ(Ａ,Ｅ,μ)的部分二次逼近： 加速近端梯度算法（accelerated proximal gradient，APG） 对偶方法（DUL） 由于核范数的对偶范数为谱范数，所以优化问题的对偶问题为： 其中： 表示矩阵元素绝对值最大的值。当优化问题对偶式取得最优值 时，必定满足 即此优化问题等价于： 上述优化问题是非线性、非光滑的，可以使用最速上升法求解。当 时，定义正规锥 其中 表示函数Ｊ(.)的次梯度。此时，优化问题的最速上升方向为Ｗｋ＝Ｄ－Ｄk，其中Ｄk为Ｄ在Ｎ(Ｙk)上的投影。使用线性搜索方法确定步长大小： 于是Ｙk的更新过程为 DULL比APG算法具有更好的可扩展性，这是因为在每次迭代过程中对偶方法不需要矩阵的完全奇异值分解。 增广拉格朗日乘子法（augmented Lagrange multipliers,ALM） 构造增广拉格朗日函数： 当Ｙ＝Ｙk，μ＝μ k ，使用交替式方法求解块优化问题 min Ａ,Ｅ Ｌ(Ａ,Ｅ,Ｙk,μ k )。 使用精确拉格朗日乘子法交替迭代矩阵Ａ和Ｅ，直到满足终止条件为止。若 则 再更新矩阵Ｅ: 记 分别收敛于 ，则矩阵Ｙ的更新公式为 最后更新参数μ： 其中：ρ＞１为常数；ε＞０为比较小的正数。 交替方向方法（alternating direction methods，ADM，IALM） ADM对ALM做了改善，即不精确拉格朗日乘子法（inexactALM它不需要求 的精确解，即矩阵Ａ和Ｅ的迭代更新公式为： 求解方法性能比较 低秩矩阵恢复应用 图像恢复 低秩矩阵恢复应用 图像去光照影响恢复 低秩矩阵恢复应用 视频背景建模 Candès, Li, Ma, and W., JACM, May 2011. 低秩矩阵恢复应用 图像类别标签净化 低秩矩阵恢复应用 文本主题分析 低秩矩阵恢复应用 音乐词曲分离 低