矩阵低秩分解理论

关于矩阵低秩分解理论从稀疏表示到低秩分解稀疏表示压缩感知(Compressedsensing)第2页,共38页，2024年2月25日，星期天从稀疏表示到低秩分解矩阵低秩分解矩阵低秩稀疏分解(Sparseandlow-rankmatrixdecomposition)低秩矩阵恢复（Low-rankMatrixRecovery）鲁棒主成分分析(Robustprinciplecomponentanalysis,RPCA)低秩稀疏非相干分解(Rank-sparsityincoherence)observationlow-ranksparse第3页,共38页，2024年2月25日，星期天预备知识第4页,共38页，2024年2月25日，星期天低秩矩阵恢复（鲁棒主成分分析RPCA）在许多实际应用中，给定的数据矩阵Ｄ往往是低秩或近似低秩的，但存在随机幅值任意大但是分布稀疏的误差破坏了原有数据的低秩性，为了恢复矩阵Ｄ的低秩结构，可将矩阵Ｄ分解为两个矩阵之和，即Ｄ＝Ａ＋Ｅ，其中矩阵Ａ和Ｅ未知，但Ａ是低秩的。当矩阵Ｅ的元素服从独立同分布的高斯分布时，可用经典的PCA来获得最优的矩阵Ａ，即求解下列最优化问题：

当Ｅ为稀疏的大噪声矩阵时，问题转化为双目标优化问题：

引入折中因子λ，将双目标优化问题转换为单目标优化问题：第5页,共38页，2024年2月25日，星期天RPCA的求解凸松弛NP难问题松弛后矩阵核范数第6页,共38页，2024年2月25日，星期天迭代阈值算法（iterativethresholding，IT）将最优化问题正则化，便得到优化问题：优化问题式的拉格朗日函数为使用迭代阈值算法交替更新矩阵Ａ,Ｅ和Ｙ。当Ｅ=Ｅk，Ｙ=Ｙk时，当Ａ＝Ａk+1，Ｙ＝Ｙk时，当Ａ＝Ａk+1

，Ｅ＝Ｅk+1时，其中：步长δk满足０＜δk

＜1ＩＴ算法的迭代式形式简单且收敛，但它的收敛速度比较慢，且难以选取合适的步长第7页,共38页，2024年2月25日，星期天加速近端梯度算法（acceleratedproximalgradient，APG）将优化问题式的等式约束松弛到目标函数中，得到如下的拉格朗日函数：记于是L(Ａ,Ｅ,μ)=ｇ(Ａ,Ｅ,μ)+ｆ(Ａ,Ｅ)。函数ｇ(Ａ,Ｅ,μ)不可微，而ｆ(Ａ,Ｅ)光滑且具有李普希兹连续梯度，即存在Lf＞0，使得其中：表示函数ｆ(Ａ,Ｅ)关于矩阵变量Ａ和Ｅ的Ｆｒéｃｈｅｔ梯度。此处取Lf=２。对于给定的与Ｄ同型的两个矩阵ＹA和ＹE，作Ｌ(Ａ,Ｅ,μ)的部分二次逼近：第8页,共38页，2024年2月25日，星期天加速近端梯度算法（acceleratedproximalgradient，APG）为了得到更新ＹA和ＹE时的步长，需先确定参数ｔk+1：于是ＹA和ＹE的迭代更新公式为:参数μ的迭代公式为其中：为事先给定的正数；0＜η＜１。尽管ＡＰＧ与ＩＴ算法类似，但它却大大降低了迭代次数。第9页,共38页，2024年2月25日，星期天由于核范数的对偶范数为谱范数，所以优化问题的对偶问题为：其中：表示矩阵元素绝对值最大的值。当优化问题对偶式取得最优值时，必定满足即此优化问题等价于：上述优化问题是非线性、非光滑的，可以使用最速上升法求解。当时，定义正规锥其中表示函数Ｊ(.)的次梯度。此时，优化问题的最速上升方向为Ｗｋ＝Ｄ－Ｄk，其中Ｄk为Ｄ在Ｎ(Ｙk)上的投影。使用线性搜索方法确定步长大小：于是Ｙk的更新过程为DULL比APG算法具有更好的可扩展性，这是因为在每次迭代过程中对偶方法不需要矩阵的完全奇异值分解。对偶方法（DUL）第10页,共38页，2024年2月25日，星期天增广拉格朗日乘子法（augmentedLagrangemultipliers,ALM）构造增广拉格朗日函数：当Ｙ＝Ｙk，μ＝μk

，使用交替式方法求解块优化问题

minＡ,ＥＬ(Ａ,Ｅ,Ｙk,μk)。使用精确拉格朗日乘子法交替迭代矩阵Ａ和Ｅ，直到满足终止条件为止。若则第11页,共38页，2024年2月25日，星期天再更新矩阵Ｅ:记分别收敛于，则矩阵Ｙ的更新公式为最后更新参数μ：其中：ρ＞１为常数；ε＞０为比较小的正数。第12页,共38页，2024年2月25日，星期天交替方向方法（alternatingdirectionmethods，ADM，IALM）ADM对ALM做了改善，即不精确拉格朗日乘子法（inexactALM它不需要求的精确解，即矩阵Ａ和Ｅ的迭代更新公式为：第13页,共38页，2024年2月25日，星期天求解方法性能比较第14页,共38页，2024年2月25日，星期天低秩矩阵恢复应用图像恢复第15页,共38页，2024年2月25日，星期天低秩矩阵恢复应用图像去光照影响恢复第16页,共38页，2024年2月25日，星期天低秩矩阵恢复应用视频背景建模Candès,Li,Ma,andW.,JACM,May2011.第17页,共38页，2024年2月25日，星期天低秩矩阵恢复应用图像类别标签净化第18页,共38页，2024年2月25日，星期天低秩矩阵恢复应用文本主题分析传统PCARPCA第19页,共38页，2024年2月25日，星期天低秩矩阵恢复应用音乐词曲分离第20页,共38页，2024年2月25日，星期天低秩矩阵恢复应用图像矫正与去噪第21页,共38页，2024年2月25日，星期天低秩矩阵恢复应用图像对齐第22页,共38页，2024年2月25日，星期天低秩矩阵补全当数据矩阵Ｄ含丢失元素时，可根据矩阵的低秩结构来恢复矩阵的所有元素，称此恢复过程为矩阵补全（ＭＣ）。记Ω为集合［ｍ］×［ｎ］的子集，这里［ｍ］表示集合｛１,２,…,ｍ｝。ＭＣ的原始模型可描述为如下的优化问题：其中：为一线性投影算子，即为便于优化，凸松弛后转化为：第23页,共38页，2024年2月25日，星期天低秩矩阵补全求解ＭＣ问题可应用ＡＬＭ算法求解，将原优化问题重新表示为：于是构造上述问题的部分增广拉格朗日函数为第24页,共38页，2024年2月25日，星期天低秩矩阵补全应用智能推荐系统第25页,共38页，2024年2月25日，星期天低秩矩阵补全应用电影去雨线处理第26页,共38页，2024年2月25日，星期天低秩矩阵表示（LRR）低秩矩阵表示（LRR）是将数据集矩阵Ｄ表示成字典矩阵Ｂ（也称为基矩阵）下的线性组合，即Ｄ＝ＢＺ，并希望线性组合系数矩阵Ｚ是低秩的。为此，需要求解下列优化问题：为便于优化，凸松弛后转化为：若选取数据集Ｄ本身作为字典，则有那么其解为，这里是D的SVD分解。当D是从多个独立子空间的采样组合，那么为对角块矩阵，每个块对应着一个子空间。此即为子空间聚类（SparseSubspaceClustering）。第27页,共38页，2024年2月25日，星期天低秩矩阵表示（LRR）为了对噪声和野点更加鲁棒，一个更合理的模型为：一般意义上的LRR可以看做：第28页,共38页，2024年2月25日，星期天低秩矩阵表示求解构造上述优化问题的增广拉格朗日乘子函数为当时,Ｘ的更新公式为Ｚ的更新公式为Ｅ的更新公式为拉格朗日乘子的迭代公式为参数μ的更新式为第29页,共38页，2024年2月25日，星期天低秩矩阵表示的应用图像分割B.Chengetal.Multi-taskLow-rankAffinityPursuitforImageSegmentation,ICCV2011.第30页,共38页，2024年2月25日，星期天低秩矩阵表示的应用显著性检测Langetal.SaliencyDetectionbyMultitaskSparsityPursuit.IEEETIP2012.

第31页,共38页，2024年2月25日，星期天低秩矩阵表示新近的发展研究LatentLRRLiuandYan.LatentLow-RankRepresentationforSubspaceSegmentationandFeatureExtraction,ICCV2011.

第32页,共38页，2024年2月25日，星期天低秩矩阵表示新近的发展研究FixedRankRepresentation(FRR)Liu,Lin,Torre,andSu,Fixed-RankRepresentationforUnsupervisedVisualLearning,CVPR2012.

第33页,共38页，2024年2月25日，星期天低秩矩阵表示新近的发展研究KernelLRRWangetal.,StructuralSimilarityandDistanceinLearning,AnnualAllertonConf.Communication,ControlandComputing2011.第