矩陣低秩分解理論課件

矩陣低秩分解理論及其應(yīng)用分析成科揚2013年9月4日矩陣低秩分解理論及其應(yīng)用分析成科揚1從稀疏表示到低秩分解稀疏表示壓縮感知(Compressedsensing)從稀疏表示到低秩分解稀疏表示2從稀疏表示到低秩分解矩陣低秩分解矩陣低秩稀疏分解(Sparseandlow-rankmatrixdecomposition)低秩矩陣恢復(fù)（Low-rankMatrixRecovery）魯棒主成分分析(Robustprinciplecomponentanalysis,RPCA)低秩稀疏非相干分解(Rank-sparsityincoherence)observationlow-ranksparse從稀疏表示到低秩分解矩陣低秩分解observationlow3預(yù)備知識預(yù)備知識4低秩矩陣恢復(fù)（魯棒主成分分析RPCA）在許多實際應(yīng)用中，給定的數(shù)據(jù)矩陣Ｄ往往是低秩或近似低秩的，但存在隨機幅值任意大但是分布稀疏的誤差破壞了原有數(shù)據(jù)的低秩性，為了恢復(fù)矩陣Ｄ的低秩結(jié)構(gòu)，可將矩陣Ｄ分解為兩個矩陣之和，即Ｄ＝Ａ＋Ｅ，其中矩陣Ａ和Ｅ未知，但Ａ是低秩的。當(dāng)矩陣Ｅ的元素服從獨立同分布的高斯分布時，可用經(jīng)典的PCA來獲得最優(yōu)的矩陣Ａ，即求解下列最優(yōu)化問題：

當(dāng)Ｅ為稀疏的大噪聲矩陣時，問題轉(zhuǎn)化為雙目標優(yōu)化問題：

引入折中因子λ，將雙目標優(yōu)化問題轉(zhuǎn)換為單目標優(yōu)化問題：低秩矩陣恢復(fù)（魯棒主成分分析RPCA）在許多實際應(yīng)用中，給定5RPCA的求解凸松弛NP難問題松弛后矩陣核范數(shù)RPCA的求解凸松弛NP難問題矩陣核范數(shù)6迭代閾值算法（iterativethresholding，IT）將最優(yōu)化問題正則化，便得到優(yōu)化問題：優(yōu)化問題式的拉格朗日函數(shù)為使用迭代閾值算法交替更新矩陣Ａ,Ｅ和Ｙ。當(dāng)Ｅ=Ｅk，Ｙ=Ｙk時，當(dāng)Ａ＝Ａk+1，Ｙ＝Ｙk時，當(dāng)Ａ＝Ａk+1，Ｅ＝Ｅk+1時，其中：步長δk滿足０＜δk＜1ＩＴ算法的迭代式形式簡單且收斂，但它的收斂速度比較慢，且難以選取合適的步長迭代閾值算法（iterativethresholding，7加速近端梯度算法（acceleratedproximalgradient，APG）將優(yōu)化問題式的等式約束松弛到目標函數(shù)中，得到如下的拉格朗日函數(shù)：記于是L(Ａ,Ｅ,μ)=ｇ(Ａ,Ｅ,μ)+ｆ(Ａ,Ｅ)。函數(shù)ｇ(Ａ,Ｅ,μ)不可微，而ｆ(Ａ,Ｅ)光滑且具有李普希茲連續(xù)梯度，即存在Lf＞0，使得其中：表示函數(shù)ｆ(Ａ,Ｅ)關(guān)于矩陣變量Ａ和Ｅ的Ｆｒéｃｈｅｔ梯度。此處取Lf=２。對于給定的與Ｄ同型的兩個矩陣ＹA和ＹE，作Ｌ(Ａ,Ｅ,μ)的部分二次逼近：加速近端梯度算法（acceleratedproximal8加速近端梯度算法（acceleratedproximalgradient，APG）為了得到更新ＹA和ＹE時的步長，需先確定參數(shù)ｔk+1：于是ＹA和ＹE的迭代更新公式為:參數(shù)μ的迭代公式為其中：為事先給定的正數(shù)；0＜η＜１。盡管ＡＰＧ與ＩＴ算法類似，但它卻大大降低了迭代次數(shù)。加速近端梯度算法（acceleratedproximal9由于核范數(shù)的對偶范數(shù)為譜范數(shù)，所以優(yōu)化問題的對偶問題為：其中：表示矩陣元素絕對值最大的值。當(dāng)優(yōu)化問題對偶式取得最優(yōu)值時，必定滿足即此優(yōu)化問題等價于：上述優(yōu)化問題是非線性、非光滑的，可以使用最速上升法求解。當(dāng)時，定義正規(guī)錐其中表示函數(shù)Ｊ(.)的次梯度。此時，優(yōu)化問題的最速上升方向為Ｗｋ＝Ｄ－Ｄk，其中Ｄk為Ｄ在Ｎ(Ｙk)上的投影。使用線性搜索方法確定步長大?。河谑牵賙的更新過程為DULL比APG算法具有更好的可擴展性，這是因為在每次迭代過程中對偶方法不需要矩陣的完全奇異值分解。對偶方法（DUL）由于核范數(shù)的對偶范數(shù)為譜范數(shù)，所以優(yōu)化問題的對偶問題為：對偶10增廣拉格朗日乘子法（augmentedLagrangemultipliers,ALM）構(gòu)造增廣拉格朗日函數(shù)：當(dāng)Ｙ＝Ｙk，μ＝μk，使用交替式方法求解塊優(yōu)化問題minＡ,ＥＬ(Ａ,Ｅ,Ｙk,μk)。使用精確拉格朗日乘子法交替迭代矩陣Ａ和Ｅ，直到滿足終止條件為止。若則增廣拉格朗日乘子法（augmentedLagrangem11再更新矩陣Ｅ:記分別收斂于，則矩陣Ｙ的更新公式為最后更新參數(shù)μ：其中：ρ＞１為常數(shù)；ε＞０為比較小的正數(shù)。再更新矩陣Ｅ:12交替方向方法（alternatingdirectionmethods，ADM，IALM）ADM對ALM做了改善，即不精確拉格朗日乘子法（inexactALM它不需要求的精確解，即矩陣Ａ和Ｅ的迭代更新公式為：交替方向方法（alternatingdirectionm13求解方法性能比較求解方法性能比較14低秩矩陣恢復(fù)應(yīng)用圖像恢復(fù)低秩矩陣恢復(fù)應(yīng)用圖像恢復(fù)15低秩矩陣恢復(fù)應(yīng)用圖像去光照影響恢復(fù)低秩矩陣恢復(fù)應(yīng)用圖像去光照影響恢復(fù)16低秩矩陣恢復(fù)應(yīng)用視頻背景建模Candès,Li,Ma,andW.,JACM,May2011.低秩矩陣恢復(fù)應(yīng)用視頻背景建模17低秩矩陣恢復(fù)應(yīng)用圖像類別標簽凈化低秩矩陣恢復(fù)應(yīng)用圖像類別標簽凈化18低秩矩陣恢復(fù)應(yīng)用文本主題分析傳統(tǒng)PCARPCA低秩矩陣恢復(fù)應(yīng)用文本主題分析傳統(tǒng)PCARPCA19低秩矩陣恢復(fù)應(yīng)用音樂詞曲分離低秩矩陣恢復(fù)應(yīng)用音樂詞曲分離20低秩矩陣恢復(fù)應(yīng)用圖像矯正與去噪低秩矩陣恢復(fù)應(yīng)用圖像矯正與去噪21低秩矩陣恢復(fù)應(yīng)用圖像對齊低秩矩陣恢復(fù)應(yīng)用圖像對齊22低秩矩陣補全當(dāng)數(shù)據(jù)矩陣Ｄ含丟失元素時，可根據(jù)矩陣的低秩結(jié)構(gòu)來恢復(fù)矩陣的所有元素，稱此恢復(fù)過程為矩陣補全（ＭＣ）。記Ω為集合［ｍ］×［ｎ］的子集，這里［ｍ］表示集合｛１,２,…,ｍ｝。ＭＣ的原始模型可描述為如下的優(yōu)化問題：其中：為一線性投影算子，即為便于優(yōu)化，凸松弛后轉(zhuǎn)化為：低秩矩陣補全當(dāng)數(shù)據(jù)矩陣Ｄ含丟失元素時，可根據(jù)矩陣的低秩結(jié)構(gòu)來23低秩矩陣補全求解ＭＣ問題可應(yīng)用ＡＬＭ算法求解，將原優(yōu)化問題重新表示為：于是構(gòu)造上述問題的部分增廣拉格朗日函數(shù)為低秩矩陣補全求解ＭＣ問題可應(yīng)用ＡＬＭ算法求解，將原優(yōu)化問題重24低秩矩陣補全應(yīng)用智能推薦系統(tǒng)低秩矩陣補全應(yīng)用智能推薦系統(tǒng)25低秩矩陣補全應(yīng)用電影去雨線處理低秩矩陣補全應(yīng)用電影去雨線處理26低秩矩陣表示（LRR）低秩矩陣表示（LRR）是將數(shù)據(jù)集矩陣Ｄ表示成字典矩陣Ｂ（也稱為基矩陣）下的線性組合，即Ｄ＝ＢＺ，并希望線性組合系數(shù)矩陣Ｚ是低秩的。為此，需要求解下列優(yōu)化問題：為便于優(yōu)化，凸松弛后轉(zhuǎn)化為：若選取數(shù)據(jù)集Ｄ本身作為字典，則有那么其解為，這里是D的SVD分解。當(dāng)D是從多個獨立子空間的采樣組合，那么為對角塊矩陣，每個塊對應(yīng)著一個子空間。此即為子空間聚類（SparseSubspaceClustering）。低秩矩陣表示（LRR）低秩矩陣表示（LRR）是將數(shù)據(jù)集矩陣Ｄ27低秩矩陣表示（LRR）為了對噪聲和野點更加魯棒，一個更合理的模型為：一般意義上的LRR可以看做：低秩矩陣表示（LRR）為了對噪聲和野點更加魯棒，一個更合理的28低秩矩陣表示求解構(gòu)造上述優(yōu)化問題的增廣拉格朗日乘子函數(shù)為當(dāng)時,Ｘ的更新公式為Ｚ的更新公式為Ｅ的更新公式為拉格朗日乘子的迭代公式為參數(shù)μ的更新式為低秩矩陣表示求解構(gòu)造上述優(yōu)化問題的增廣拉格朗日乘子函數(shù)為29低秩矩陣表示的應(yīng)用圖像分割B.Chengetal.Multi-taskLow-rankAffinityPursuitforImageSegmentation,ICCV2011.低秩矩陣表示的應(yīng)用圖像分割30低秩矩陣表示的應(yīng)用顯著性檢測Langetal.SaliencyDetectionbyMultitaskSparsityPursuit.IEEETIP2012.

低秩矩陣表示的應(yīng)用顯著性檢測31低秩矩陣表示新近的發(fā)展研究LatentLRRLiuandYan.LatentLow-RankRepresentationforSubspaceSegmentationandFeatureExtraction,ICCV2011.

低秩矩陣表示新近的發(fā)展研究LatentLRR32低秩矩陣表示新近的發(fā)展研究FixedRankRepresentation(FRR)Liu,Lin,Torre,andSu,Fixed-RankRepresentationforUnsupervisedVisualLearning,CVPR2012.

低秩矩陣表示新近的發(fā)展研究FixedRankRepres33低秩矩陣表示新近的發(fā)展研究KernelLRRWangetal.,StructuralSimilarityandDistanceinLearning,AnnualAllertonConf.Communication,ControlandComputing2011.低秩矩陣表示新近的發(fā)展研究KernelLRR34低秩矩陣表示新近的發(fā)展研究基于低秩張量應(yīng)用研究低秩矩陣表示新近的發(fā)展研究基于低秩張量應(yīng)用研究35低秩矩陣表示新近的發(fā)展研究基于低秩張量應(yīng)用研究低秩矩陣表示新近的發(fā)展研