矩陣低秩分解理論

1、矩陣低秩分解理論及其應(yīng)用分析矩陣低秩分解理論及其應(yīng)用分析成科揚(yáng)2013年9月4日從稀疏表示到低秩分解 稀疏表示壓縮感知(Compressed sensing)從稀疏表示到低秩分解 矩陣低秩分解 矩陣低秩稀疏分解(Sparse and low-rank matrix decomposition) 低秩矩陣恢復(fù)（Low-rank Matrix Recovery） 魯棒主成分分析(Robust principle component analysis, RPCA) 低秩稀疏非相干分解(Rank-sparsity incoherence)observationlow-ranksparse預(yù)備知識(shí)低秩矩

2、陣恢復(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)題：RPCA的求解 凸松弛NP難問(wèn)題松弛后矩陣核范數(shù)迭代閾值算法（iterative thresholding，IT）將最優(yōu)化問(wèn)題正則化，便得到優(yōu)化問(wèn)題：優(yōu)化問(wèn)題式的

3、拉格朗日函數(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)加速近端梯度算法（accelerated proximal gradient，APG）將優(yōu)化問(wèn)題式的等式約束松弛到目標(biāo)函數(shù)中，得到如下的拉格朗日函數(shù)： 記于是L(,)=(,)+(,)。函數(shù)(,)不可微，而(,)光滑且具有李普希茲連續(xù)梯度，即存在Lf0，使得 其中： 表示函數(shù)(,)關(guān)于矩陣變量和的梯度。此處取Lf =。對(duì)于給定的與同型的兩個(gè)矩陣A和E，作(,)的部分二次逼近：加速近端梯度算法（accel

4、erated proximal gradient，APG）為了得到更新A和E時(shí)的步長(zhǎng)，需先確定參數(shù)k+1：于是A和E的迭代更新公式為:參數(shù)的迭代公式為其中： 為事先給定的正數(shù)；0。盡管與算法類(lèi)似，但它卻大大降低了迭代次數(shù)。 由于核范數(shù)的對(duì)偶范數(shù)為譜范數(shù)，所以?xún)?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í)，定義正規(guī)錐 其中 表示函數(shù)(.)的次梯度。此時(shí)，優(yōu)化問(wèn)題的最速上升方向?yàn)閗，其中k為在(k)上的投影。使用線性搜索方法確定步長(zhǎng)大?。?于是k的更新過(guò)程為

5、DULL比APG算法具有更好的可擴(kuò)展性，這是因?yàn)樵诿看蔚^(guò)程中對(duì)偶方法不需要矩陣的完全奇異值分解。對(duì)偶方法（DUL）增廣拉格朗日乘子法（augmented Lagrange multipliers,ALM）構(gòu)造增廣拉格朗日函數(shù)：當(dāng)k， k ，使用交替式方法求解塊優(yōu)化問(wèn)題 min , (,k, k )。使用精確拉格朗日乘子法交替迭代矩陣和，直到滿足終止條件為止。若 則交替方向方法（alternating direction methods，ADM，IALM） ADM對(duì)ALM做了改善，即不精確拉格朗日乘子法（inexactALM它不需要求 的精確解，即矩陣和的迭代更新公式為：求解方法性能比較低秩

6、矩陣恢復(fù)應(yīng)用 圖像恢復(fù)低秩矩陣恢復(fù)應(yīng)用 圖像去光照影響恢復(fù)低秩矩陣恢復(fù)應(yīng)用 視頻背景建模Cands, Li, Ma, and W., JACM, May 2011.低秩矩陣恢復(fù)應(yīng)用 圖像類(lèi)別標(biāo)簽凈化低秩矩陣恢復(fù)應(yīng)用 文本主題分析傳統(tǒng)PCARPCA低秩矩陣恢復(fù)應(yīng)用 音樂(lè)詞曲分離低秩矩陣恢復(fù)應(yīng)用 圖像矯正與去噪低秩矩陣恢復(fù)應(yīng)用 圖像對(duì)齊低秩矩陣補(bǔ)全 當(dāng)數(shù)據(jù)矩陣含丟失元素時(shí)，可根據(jù)矩陣的低秩結(jié)構(gòu)來(lái)恢復(fù)矩陣的所有元素，稱(chēng)此恢復(fù)過(guò)程為矩陣補(bǔ)全（）。 記為集合的子集，這里表示集合,。的原始模型可描述為如下的優(yōu)化問(wèn)題： 其中： 為一線性投影算子，即 為便于優(yōu)化，凸松弛后轉(zhuǎn)化為：低秩矩陣補(bǔ)全求解 問(wèn)題可應(yīng)用算

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

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

9、的發(fā)展研究 Latent LRRLiu and Yan. Latent Low-Rank Representation for Subspace Segmentation and Feature Extraction, ICCV 2011. 低秩矩陣表示新近的發(fā)展研究 Fixed Rank Representation (FRR) Liu, Lin, Torre, and Su, Fixed-Rank Representation for Unsupervised Visual Learning, CVPR 2012. 低秩矩陣表示新近的發(fā)展研究 Kernel LRR Wang et al., Structural Similarity and Distance in Learning, Annual Allerton Conf. Communication, Control and Computing 2011. 低秩矩陣表示新近的發(fā)展研究 基于低秩張量應(yīng)用研究低秩矩陣表示新近的發(fā)展研究 基于低秩張量應(yīng)用研究稀疏表示和矩陣低秩分解類(lèi)