矩陣低秩分解理論

1、整理課件,1,矩陣低秩分解理論及其應(yīng)用分析,整理課件,2,從稀疏表示到低秩分解,稀疏表示 壓縮感知(Compressed sensing),整理課件,3,從稀疏表示到低秩分解,矩陣低秩分解 矩陣低秩稀疏分解(Sparse and low-rank matrix decomposition) 低秩矩陣恢復(fù)（Low-rank Matrix Recovery） 魯棒主成分分析(Robust principle component analysis, RPCA) 低秩稀疏非相干分解(Rank-sparsity incoherence),observation,low-rank,sparse,整理課件,

2、4,預(yù)備知識(shí),整理課件,5,低秩矩陣恢復(fù)（魯棒主成分分析RPCA）,在許多實(shí)際應(yīng)用中，給定的數(shù)據(jù)矩陣往往是低秩或近似低秩的，但存在隨機(jī)幅值任意大但是分布稀疏的誤差破壞了原有數(shù)據(jù)的低秩性，為了恢復(fù)矩陣的低秩結(jié)構(gòu)，可將矩陣分解為兩個(gè)矩陣之和，即，其中矩陣和未知，但是低秩的。當(dāng)矩陣的元素服從獨(dú)立同分布的高斯分布時(shí)，可用經(jīng)典的PCA來(lái)獲得最優(yōu)的矩陣，即求解下列最優(yōu)化問(wèn)題： 當(dāng)為稀疏的大噪聲矩陣時(shí)，問(wèn)題轉(zhuǎn)化為雙目標(biāo)優(yōu)化問(wèn)題： 引入折中因子，將雙目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)換為單目標(biāo)優(yōu)化問(wèn)題：,整理課件,6,RPCA的求解,凸松弛,NP難問(wèn)題 松弛后,矩陣核范數(shù),整理課件,7,迭代閾值算法（iterative thre

3、sholding，IT）,將最優(yōu)化問(wèn)題正則化，便得到優(yōu)化問(wèn)題： 優(yōu)化問(wèn)題式的拉格朗日函數(shù)為 使用迭代閾值算法交替更新矩陣,和。當(dāng)=k，=k時(shí)， 當(dāng)k+1，k時(shí)， 當(dāng)k+1 ，k+1時(shí)， 其中：步長(zhǎng)k滿足 k 1 算法的迭代式形式簡(jiǎn)單且收斂，但它的收斂速度比較慢，且難以選取合適的步長(zhǎng),整理課件,8,加速近端梯度算法（accelerated proximal gradient，APG）,將優(yōu)化問(wèn)題式的等式約束松弛到目標(biāo)函數(shù)中，得到如下的拉格朗日函數(shù)： 記 于是L(,)=(,)+(,)。函數(shù)(,)不可微，而(,)光滑且具有李普希茲連續(xù)梯度，即存在Lf0，使得 其中： 表示函數(shù)(,)關(guān)于矩陣變量和的梯

4、度。此處取Lf =。對(duì)于給定的與同型的兩個(gè)矩陣A和E，作(,)的部分二次逼近：,整理課件,9,加速近端梯度算法（accelerated proximal gradient，APG）,為了得到更新A和E時(shí)的步長(zhǎng)，需先確定參數(shù)k+1： 于是A和E的迭代更新公式為: 參數(shù)的迭代公式為 其中： 為事先給定的正數(shù)；0。 盡管與算法類似，但它卻大大降低了迭代次數(shù)。,整理課件,10,由于核范數(shù)的對(duì)偶范數(shù)為譜范數(shù)，所以優(yōu)化問(wèn)題的對(duì)偶問(wèn)題為： 其中： 表示矩陣元素絕對(duì)值最大的值。當(dāng)優(yōu)化問(wèn)題對(duì)偶式取得最優(yōu)值 時(shí)，必定滿足 即此優(yōu)化問(wèn)題等價(jià)于： 上述優(yōu)化問(wèn)題是非線性、非光滑的，可以使用最速上升法求解。當(dāng) 時(shí)，定義正

5、規(guī)錐 其中 表示函數(shù)(.)的次梯度。此時(shí)，優(yōu)化問(wèn)題的最速上升方向?yàn)閗，其中k為在(k)上的投影。使用線性搜索方法確定步長(zhǎng)大?。?于是k的更新過(guò)程為 DULL比APG算法具有更好的可擴(kuò)展性，這是因?yàn)樵诿看蔚^(guò)程中對(duì)偶方法不需要矩陣的完全奇異值分解。,對(duì)偶方法（DUL）,整理課件,11,增廣拉格朗日乘子法（augmented Lagrange multipliers,ALM）,構(gòu)造增廣拉格朗日函數(shù)： 當(dāng)k， k ，使用交替式方法求解塊優(yōu)化問(wèn)題 min , (,k, k )。 使用精確拉格朗日乘子法交替迭代矩陣和，直到滿足終止條件為止。若 則,整理課件,12,再更新矩陣: 記 分別收斂于 ，則矩陣

6、的更新公式為 最后更新參數(shù)： 其中：為常數(shù)；為比較小的正數(shù)。,整理課件,13,交替方向方法（alternating direction methods，ADM，IALM）,ADM對(duì)ALM做了改善，即不精確拉格朗日乘子法（inexactALM它不需要求 的精確解，即矩陣和的迭代更新公式為：,整理課件,14,求解方法性能比較,整理課件,15,低秩矩陣恢復(fù)應(yīng)用,圖像恢復(fù),整理課件,16,低秩矩陣恢復(fù)應(yīng)用,圖像去光照影響恢復(fù),整理課件,17,低秩矩陣恢復(fù)應(yīng)用,視頻背景建模 Cands, Li, Ma, and W., JACM, May 2011.,整理課件,18,低秩矩陣恢復(fù)應(yīng)用,圖像類別標(biāo)簽凈化,

7、整理課件,19,低秩矩陣恢復(fù)應(yīng)用,文本主題分析,傳統(tǒng)PCA,RPCA,整理課件,20,低秩矩陣恢復(fù)應(yīng)用,音樂(lè)詞曲分離,整理課件,21,低秩矩陣恢復(fù)應(yīng)用,圖像矯正與去噪,整理課件,22,低秩矩陣恢復(fù)應(yīng)用,圖像對(duì)齊,整理課件,23,低秩矩陣補(bǔ)全,當(dāng)數(shù)據(jù)矩陣含丟失元素時(shí)，可根據(jù)矩陣的低秩結(jié)構(gòu)來(lái)恢復(fù)矩陣的所有元素，稱此恢復(fù)過(guò)程為矩陣補(bǔ)全（）。 記為集合的子集，這里表示集合,。的原始模型可描述為如下的優(yōu)化問(wèn)題： 其中： 為一線性投影算子，即 為便于優(yōu)化，凸松弛后轉(zhuǎn)化為：,整理課件,24,低秩矩陣補(bǔ)全求解,問(wèn)題可應(yīng)用算法求解，將原優(yōu)化問(wèn)題重新表示為： 于是構(gòu)造上述問(wèn)題的部分增廣拉格朗日函數(shù)為,整理課件,2

8、5,低秩矩陣補(bǔ)全應(yīng)用,智能推薦系統(tǒng),整理課件,26,低秩矩陣補(bǔ)全應(yīng)用,電影去雨線處理,整理課件,27,低秩矩陣表示（LRR）,低秩矩陣表示（LRR）是將數(shù)據(jù)集矩陣表示成字典矩陣（也稱為基矩陣）下的線性組合，即，并希望線性組合系數(shù)矩陣是低秩的。為此，需要求解下列優(yōu)化問(wèn)題： 為便于優(yōu)化，凸松弛后轉(zhuǎn)化為： 若選取數(shù)據(jù)集本身作為字典，則有 那么其解為 ，這里 是D的SVD分解。 當(dāng)D是從多個(gè)獨(dú)立子空間的采樣組合，那么 為對(duì)角塊矩陣，每個(gè)塊對(duì)應(yīng)著一個(gè)子空間。此即為子空間聚類（Sparse Subspace Clustering）。,整理課件,28,低秩矩陣表示（LRR）,為了對(duì)噪聲和野點(diǎn)更加魯棒，一個(gè)更

9、合理的模型為： 一般意義上的LRR可以看做：,整理課件,29,低秩矩陣表示求解,構(gòu)造上述優(yōu)化問(wèn)題的增廣拉格朗日乘子函數(shù)為 當(dāng) 時(shí),的更新公式為 的更新公式為 的更新公式為 拉格朗日乘子的迭代公式為 參數(shù)的更新式為,整理課件,30,低秩矩陣表示的應(yīng)用,圖像分割 B. Cheng et al. Multi-task Low-rank Affinity Pursuit for Image Segmentation, ICCV 2011.,整理課件,31,低秩矩陣表示的應(yīng)用,顯著性檢測(cè) Lang et al. Saliency Detection by Multitask Sparsity Pursu

10、it. IEEE TIP 2012.,整理課件,32,低秩矩陣表示新近的發(fā)展研究,Latent LRR Liu and Yan. Latent Low-Rank Representation for Subspace Segmentation and Feature Extraction, ICCV 2011.,整理課件,33,低秩矩陣表示新近的發(fā)展研究,Fixed Rank Representation (FRR),Liu, Lin, Torre, and Su, Fixed-Rank Representation for Unsupervised Visual Learning, CVPR 2012.,整理課件,34,低秩矩陣表示新近的發(fā)展研究,Kernel LRR Wang et al., Structural Similarity and Distance in Learning, Annual Allerton Conf. Communication, Control and Computing 2011.,整理課件,35,低秩矩陣表示新近的發(fā)展研究,基于低秩張量應(yīng)用研究,整理課件,36,低秩矩陣表示新近的發(fā)展研究,基于低秩張量應(yīng)用研究,整理課件,37,稀疏表