矩陣低秩分解理論

1、關(guān)于矩陣低秩分解理論第一張，PPT共三十八頁，創(chuàng)作于2022年6月從稀疏表示到低秩分解稀疏表示壓縮感知(Compressed sensing)第二張，PPT共三十八頁，創(chuàng)作于2022年6月從稀疏表示到低秩分解矩陣低秩分解矩陣低秩稀疏分解(Sparse and low-rank matrix decomposition)低秩矩陣恢復(fù)（Low-rank Matrix Recovery）魯棒主成分分析(Robust principle component analysis, RPCA)低秩稀疏非相干分解(Rank-sparsity incoherence)observationlow-rankspa

2、rse第三張，PPT共三十八頁，創(chuàng)作于2022年6月預(yù)備知識(shí)第四張，PPT共三十八頁，創(chuàng)作于2022年6月低秩矩陣恢復(fù)（魯棒主成分分析RPCA）在許多實(shí)際應(yīng)用中，給定的數(shù)據(jù)矩陣往往是低秩或近似低秩的，但存在隨機(jī)幅值任意大但是分布稀疏的誤差破壞了原有數(shù)據(jù)的低秩性，為了恢復(fù)矩陣的低秩結(jié)構(gòu)，可將矩陣分解為兩個(gè)矩陣之和，即，其中矩陣和未知，但是低秩的。當(dāng)矩陣的元素服從獨(dú)立同分布的高斯分布時(shí)，可用經(jīng)典的PCA來獲得最優(yōu)的矩陣，即求解下列最優(yōu)化問題： 當(dāng)為稀疏的大噪聲矩陣時(shí)，問題轉(zhuǎn)化為雙目標(biāo)優(yōu)化問題： 引入折中因子，將雙目標(biāo)優(yōu)化問題轉(zhuǎn)換為單目標(biāo)優(yōu)化問題：第五張，PPT共三十八頁，創(chuàng)作于2022年6月RPC

3、A的求解凸松弛NP難問題松弛后矩陣核范數(shù)第六張，PPT共三十八頁，創(chuàng)作于2022年6月迭代閾值算法（iterative thresholding，IT）將最優(yōu)化問題正則化，便得到優(yōu)化問題：優(yōu)化問題式的拉格朗日函數(shù)為使用迭代閾值算法交替更新矩陣,和。當(dāng)=k，=k時(shí)，當(dāng)k+1，k時(shí)，當(dāng)k+1 ，k+1時(shí)，其中：步長k滿足 k 1算法的迭代式形式簡(jiǎn)單且收斂，但它的收斂速度比較慢，且難以選取合適的步長第七張，PPT共三十八頁，創(chuàng)作于2022年6月加速近端梯度算法（accelerated proximal gradient，APG）將優(yōu)化問題式的等式約束松弛到目標(biāo)函數(shù)中，得到如下的拉格朗日函數(shù)： 記于是

4、L(,)=(,)+(,)。函數(shù)(,)不可微，而(,)光滑且具有李普希茲連續(xù)梯度，即存在Lf0，使得 其中： 表示函數(shù)(,)關(guān)于矩陣變量和的梯度。此處取Lf =。對(duì)于給定的與同型的兩個(gè)矩陣A和E，作(,)的部分二次逼近：第八張，PPT共三十八頁，創(chuàng)作于2022年6月加速近端梯度算法（accelerated proximal gradient，APG）為了得到更新A和E時(shí)的步長，需先確定參數(shù)k+1：于是A和E的迭代更新公式為:參數(shù)的迭代公式為其中： 為事先給定的正數(shù)；0。盡管與算法類似，但它卻大大降低了迭代次數(shù)。第九張，PPT共三十八頁，創(chuàng)作于2022年6月由于核范數(shù)的對(duì)偶范數(shù)為譜范數(shù)，所以優(yōu)化問

5、題的對(duì)偶問題為： 其中： 表示矩陣元素絕對(duì)值最大的值。當(dāng)優(yōu)化問題對(duì)偶式取得最優(yōu)值 時(shí)，必定滿足 即此優(yōu)化問題等價(jià)于： 上述優(yōu)化問題是非線性、非光滑的，可以使用最速上升法求解。當(dāng) 時(shí)，定義正規(guī)錐 其中 表示函數(shù)(.)的次梯度。此時(shí)，優(yōu)化問題的最速上升方向?yàn)閗，其中k為在(k)上的投影。使用線性搜索方法確定步長大?。河谑莐的更新過程為DULL比APG算法具有更好的可擴(kuò)展性，這是因?yàn)樵诿看蔚^程中對(duì)偶方法不需要矩陣的完全奇異值分解。對(duì)偶方法（DUL）第十張，PPT共三十八頁，創(chuàng)作于2022年6月增廣拉格朗日乘子法（augmented Lagrange multipliers,ALM）構(gòu)造增廣拉格朗

6、日函數(shù)：當(dāng)k， k ，使用交替式方法求解塊優(yōu)化問題 min , (,k, k )。使用精確拉格朗日乘子法交替迭代矩陣和，直到滿足終止條件為止。若 則第十一張，PPT共三十八頁，創(chuàng)作于2022年6月再更新矩陣:記 分別收斂于 ，則矩陣的更新公式為最后更新參數(shù)：其中：為常數(shù)；為比較小的正數(shù)。第十二張，PPT共三十八頁，創(chuàng)作于2022年6月交替方向方法（alternating direction methods，ADM，IALM）ADM對(duì)ALM做了改善，即不精確拉格朗日乘子法（inexactALM它不需要求 的精確解，即矩陣和的迭代更新公式為：第十三張，PPT共三十八頁，創(chuàng)作于2022年6月求解方法

7、性能比較第十四張，PPT共三十八頁，創(chuàng)作于2022年6月低秩矩陣恢復(fù)應(yīng)用圖像恢復(fù)第十五張，PPT共三十八頁，創(chuàng)作于2022年6月低秩矩陣恢復(fù)應(yīng)用圖像去光照影響恢復(fù)第十六張，PPT共三十八頁，創(chuàng)作于2022年6月低秩矩陣恢復(fù)應(yīng)用視頻背景建模Cands, Li, Ma, and W., JACM, May 2011.第十七張，PPT共三十八頁，創(chuàng)作于2022年6月低秩矩陣恢復(fù)應(yīng)用圖像類別標(biāo)簽凈化第十八張，PPT共三十八頁，創(chuàng)作于2022年6月低秩矩陣恢復(fù)應(yīng)用文本主題分析傳統(tǒng)PCARPCA第十九張，PPT共三十八頁，創(chuàng)作于2022年6月低秩矩陣恢復(fù)應(yīng)用音樂詞曲分離第二十張，PPT共三十八頁，創(chuàng)作于2

8、022年6月低秩矩陣恢復(fù)應(yīng)用圖像矯正與去噪第二十一張，PPT共三十八頁，創(chuàng)作于2022年6月低秩矩陣恢復(fù)應(yīng)用圖像對(duì)齊第二十二張，PPT共三十八頁，創(chuàng)作于2022年6月低秩矩陣補(bǔ)全當(dāng)數(shù)據(jù)矩陣含丟失元素時(shí)，可根據(jù)矩陣的低秩結(jié)構(gòu)來恢復(fù)矩陣的所有元素，稱此恢復(fù)過程為矩陣補(bǔ)全（）。記為集合的子集，這里表示集合,。的原始模型可描述為如下的優(yōu)化問題： 其中： 為一線性投影算子，即為便于優(yōu)化，凸松弛后轉(zhuǎn)化為：第二十三張，PPT共三十八頁，創(chuàng)作于2022年6月低秩矩陣補(bǔ)全求解問題可應(yīng)用算法求解，將原優(yōu)化問題重新表示為：于是構(gòu)造上述問題的部分增廣拉格朗日函數(shù)為第二十四張，PPT共三十八頁，創(chuàng)作于2022年6月低秩

9、矩陣補(bǔ)全應(yīng)用智能推薦系統(tǒng)第二十五張，PPT共三十八頁，創(chuàng)作于2022年6月低秩矩陣補(bǔ)全應(yīng)用電影去雨線處理第二十六張，PPT共三十八頁，創(chuàng)作于2022年6月低秩矩陣表示（LRR）低秩矩陣表示（LRR）是將數(shù)據(jù)集矩陣表示成字典矩陣（也稱為基矩陣）下的線性組合，即，并希望線性組合系數(shù)矩陣是低秩的。為此，需要求解下列優(yōu)化問題： 為便于優(yōu)化，凸松弛后轉(zhuǎn)化為： 若選取數(shù)據(jù)集本身作為字典，則有 那么其解為 ，這里 是D的SVD分解。 當(dāng)D是從多個(gè)獨(dú)立子空間的采樣組合，那么 為對(duì)角塊矩陣，每個(gè)塊對(duì)應(yīng)著一個(gè)子空間。此即為子空間聚類（Sparse Subspace Clustering）。第二十七張，PPT共三十

10、八頁，創(chuàng)作于2022年6月低秩矩陣表示（LRR）為了對(duì)噪聲和野點(diǎn)更加魯棒，一個(gè)更合理的模型為：一般意義上的LRR可以看做：第二十八張，PPT共三十八頁，創(chuàng)作于2022年6月低秩矩陣表示求解構(gòu)造上述優(yōu)化問題的增廣拉格朗日乘子函數(shù)為當(dāng) 時(shí),的更新公式為的更新公式為的更新公式為拉格朗日乘子的迭代公式為參數(shù)的更新式為第二十九張，PPT共三十八頁，創(chuàng)作于2022年6月低秩矩陣表示的應(yīng)用圖像分割B. Cheng et al. Multi-task Low-rank Affinity Pursuit for Image Segmentation, ICCV 2011. 第三十張，PPT共三十八頁，創(chuàng)作于20

11、22年6月低秩矩陣表示的應(yīng)用顯著性檢測(cè)Lang et al. Saliency Detection by Multitask Sparsity Pursuit. IEEE TIP 2012. 第三十一張，PPT共三十八頁，創(chuàng)作于2022年6月低秩矩陣表示新近的發(fā)展研究Latent LRRLiu and Yan. Latent Low-Rank Representation for Subspace Segmentation and Feature Extraction, ICCV 2011. 第三十二張，PPT共三十八頁，創(chuàng)作于2022年6月低秩矩陣表示新近的發(fā)展研究Fixed Rank Representation (FRR) Liu, Lin, Torre, and Su, Fixed-Rank Representation for Unsupervised Visual Learning, CVPR 2012. 第三十三張，PPT共三十八頁，創(chuàng)作于2022年6月低秩矩陣表示新近的發(fā)展研究Kernel LRR Wang et al., Structural Similarity and Distance in Learning, Annual Allerton Conf. Communication, Control and Computing 2011. 第