矩阵低秩分解理论

矩阵低秩分解理论及其应用分析成科扬2013年9月4日从稀疏表示到低秩分解•稀疏表示压缩感知(Compressedsensing)从稀疏表示到低秩分解•矩阵低秩分解矩阵低秩稀疏分解(Sparseandlow-rankmatrixdecomposition)低秩矩阵恢复（Low-rankMatrixRecovery）鲁棒主成分分析(Robustprinciplecomponentanalysis,RPCA)低秩稀疏非相干分解(Rank-sparsityincoherence)observationlow-ranksparse预备知识低秩矩阵恢复（鲁棒主成分分析RPCA）•在许多实际应用中，给定的数据矩阵Ｄ往往是低秩或近似低秩的，但存在随机幅值任意大但是分布稀疏的误差破坏了原有数据的低秩性，为了恢复矩阵Ｄ的低秩结构，可将矩阵Ｄ分解为两个矩阵之和，即Ｄ＝Ａ＋Ｅ，其中矩阵Ａ和Ｅ未知，但Ａ是低秩的。当矩阵Ｅ的元素服从独立同分布的高斯分布时，可用经典的PCA来获得最优的矩阵Ａ，即求解下列最优化问题：当Ｅ为稀疏的大噪声矩阵时，问题转化为双目标优化问题：引入折中因子λ，将双目标优化问题转换为单目标优化问题：RPCA的求解•凸松弛NP难问题松弛后矩阵核范数迭代阈值算法（iterativethresholding，IT）将最优化问题正则化，便得到优化问题：优化问题式的拉格朗日函数为使用迭代阈值算法交替更新矩阵Ａ,Ｅ和Ｙ。当Ｅ=Ｅk，Ｙ=Ｙk时，当Ａ＝Ａk+1，Ｙ＝Ｙk时，当Ａ＝Ａk+1，Ｅ＝Ｅk+1时，其中：步长δk满足０＜δk＜1•ＩＴ算法的迭代式形式简单且收敛，但它的收敛速度比较慢，且难以选取合适的步长加速近端梯度算法（acceleratedproximalgradient，APG）•将优化问题式的等式约束松弛到目标函数中，得到如下的拉格朗日函数：记•于是L(Ａ,Ｅ,μ)=ｇ(Ａ,Ｅ,μ)+ｆ(Ａ,Ｅ)。函数ｇ(Ａ,Ｅ,μ)不可微，而ｆ(Ａ,Ｅ)光滑且具有李普希兹连续梯度，即存在Lf＞0，使得其中：表示函数ｆ(Ａ,Ｅ)关于矩阵变量Ａ和Ｅ的Ｆｒéｃｈｅｔ梯度。此处取Lf=２。对于给定的与Ｄ同型的两个矩阵ＹA和ＹE，作Ｌ(Ａ,Ｅ,μ)的部分二次逼近：加速近端梯度算法（acceleratedproximalgradient，APG）为了得到更新ＹA和ＹE时的步长，需先确定参数ｔk+1：于是ＹA和ＹE的迭代更新公式为:参数μ的迭代公式为其中：为事先给定的正数；0＜η＜１。尽管ＡＰＧ与ＩＴ算法类似，但它却大大降低了迭代次数。•由于核范数的对偶范数为谱范数，所以优化问题的对偶问题为：其中：表示矩阵元素绝对值最大的值。当优化问题对偶式取得最优值时，必定满足即此优化问题等价于：上述优化问题是非线性、非光滑的，可以使用最速上升法求解。当时，定义正规锥其中表示函数Ｊ(.)的次梯度。此时，优化问题的最速上升方向为Ｗｋ＝Ｄ－Ｄk，其中Ｄk为Ｄ在Ｎ(Ｙk)上的投影。使用线性搜索方法确定步长大小：•于是Ｙk的更新过程为•DULL比APG算法具有更好的可扩展性，这是因为在每次迭代过程中对偶方法不需要矩阵的完全奇异值分解。对偶方法（DUL）增广拉格朗日乘子法（augmentedLagrangemultipliers,ALM）•构造增广拉格朗日函数：•当Ｙ＝Ｙk，μ＝μk，使用交替式方法求解块优化问题minＡ,ＥＬ(Ａ,Ｅ,Ｙk,μk)。•使用精确拉格朗日乘子法交替迭代矩阵Ａ和Ｅ，直到满足终止条件为止。若则•再更新矩阵Ｅ:•记分别收敛于，则矩阵Ｙ的更新公式为•最后更新参数μ：其中：ρ＞１为常数；ε＞０为比较小的正数。交替方向方法（alternatingdirectionmethods，ADM，IALM）•ADM对ALM做了改善，即不精确拉格朗日乘子法（inexactALM它不需要求的精确解，即矩阵Ａ和Ｅ的迭代更新公式为：求解方法性能比较低秩矩阵恢复应用•图像恢复低秩矩阵恢复应用•图像去光照影响恢复低秩矩阵恢复应用•视频背景建模Candès,Li,Ma,andW.,JACM,May2011.低秩矩阵恢复应用•图像类别标签净化低秩矩阵恢复应用•文本主题分析传统PCARPCA低秩矩阵恢复应用•音乐词曲分离低秩矩阵恢复应用•图像矫正与去噪低秩矩阵恢复应用•图像对齐低秩矩阵补全•当数据矩阵Ｄ含丢失元素时，可根据矩阵的低秩结构来恢复矩阵的所有元素，称此恢复过程为矩阵补全（ＭＣ）。•记Ω为集合［ｍ］×［ｎ］的子集，这里［ｍ］表示集合｛１,２,…,ｍ｝。ＭＣ的原始模型可描述为如下的优化问题：其中：为一线性投影算子，即•为便于优化，凸松弛后转化为：低秩矩阵补全求解•ＭＣ问题可应用ＡＬＭ算法求解，将原优化问题重新表示为：于是构造上述问题的部分增广拉格朗日函数为低秩矩阵补全应用•智能推荐系统低秩矩阵补全应用•电影去雨线处理低秩矩阵表示（LRR）•低秩矩阵表示（LRR）是将数据集矩阵Ｄ表示成字典矩阵Ｂ（也称为基矩阵）下的线性组合，即Ｄ＝ＢＺ，并希望线性组合系数矩阵Ｚ是低秩的。为此，需要求解下列优化问题：为便于优化，凸松弛后转化为：若选取数据集Ｄ本身作为字典，则有那么其解为，这里是D的SVD分解。当D是从多个独立子空间的采样组合，那么为对角块矩阵，每个块对应着一个子空间。此即为子空间聚类（SparseSubspaceClustering）。低秩矩阵表示（LRR）为了对噪声和野点更加鲁棒，一个更合理的模型为：一般意义上的LRR可以看做：低秩矩阵表示求解•构造上述优化问题的增广拉格朗日乘子函数为•当时,Ｘ的更新公式为Ｚ的更新公式为Ｅ的更新公式为拉格朗日乘子的迭代公式为参数μ的更新式为低秩矩阵表示的应用•图像分割B.Chengetal.Multi-taskLow-rankAffinityPursuitforImageSegmentation,ICCV2011.低秩矩阵表示的应用•显著性检测Langetal.SaliencyDetectionbyMultitaskSparsityPursuit.IEEETIP2012.低秩矩阵表示新近的发展研究•LatentLRRLiuandYan.LatentLow-RankRepresentationforSubspaceSegmentationandFeatureExtraction,ICCV2011.低秩矩阵表示新近的发展研究•FixedRankRepresentation(FRR)Liu,Lin,Torre,andSu,Fixed-RankRepresentationforUnsupervisedVisualLearning,CVPR2012.低秩矩阵表示新近的发展研究•KernelLRRWangetal.,StructuralSimilarityandDistanceinLearning,AnnualAllertonConf.Communication,ControlandComputing2011.低秩矩阵表示新近的发展研究•基于低秩张量应用研究低秩矩阵表示新近的发展研究•基于低秩张量应用研究稀疏表示和矩阵低秩分解类比研究展望：•理论方面：需要研究在稀疏性或(和)低秩性之外,如何更进一步地去发现和利用数据中潜在的本质结构。•算法方面：需要充分利用问题的结构和现有的硬件条件,开发快速的、并行的算法变性。•应用方面：需要根据应用问题本身的物理意义,设计合理的数学模型,使用现代凸优化方法进行高效的求解。