矩陣低秩分解理論

1、矩陣低秩分解理論第1頁，共38頁，2022年，5月20日，1點8分，星期六從稀疏表示到低秩分解稀疏表示壓縮感知(Compressed sensing)第2頁，共38頁，2022年，5月20日，1點8分，星期六從稀疏表示到低秩分解矩陣低秩分解矩陣低秩稀疏分解(Sparse and low-rank matrix decomposition)低秩矩陣恢復(fù)（Low-rank Matrix Recovery）魯棒主成分分析(Robust principle component analysis, RPCA)低秩稀疏非相干分解(Rank-sparsity incoherence)observationl

2、ow-ranksparse第3頁，共38頁，2022年，5月20日，1點8分，星期六預(yù)備知識第4頁，共38頁，2022年，5月20日，1點8分，星期六低秩矩陣恢復(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)化問題：第5頁，

3、共38頁，2022年，5月20日，1點8分，星期六RPCA的求解凸松弛NP難問題松弛后矩陣核范數(shù)第6頁，共38頁，2022年，5月20日，1點8分，星期六迭代閾值算法（iterative thresholding，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算法的迭代式形式簡單且收斂，但它的收斂速度比較慢，且難以選取合適的步長第7頁，共38頁，2022年，5月20日，1點8分，星期六加速近端梯度算法（accelerated proximal gradient，

4、APG）將優(yōu)化問題式的等式約束松弛到目標函數(shù)中，得到如下的拉格朗日函數(shù)： 記于是L(,)=(,)+(,)。函數(shù)(,)不可微，而(,)光滑且具有李普希茲連續(xù)梯度，即存在Lf0，使得 其中： 表示函數(shù)(,)關(guān)于矩陣變量和的梯度。此處取Lf =。對于給定的與同型的兩個矩陣A和E，作(,)的部分二次逼近：第8頁，共38頁，2022年，5月20日，1點8分，星期六加速近端梯度算法（accelerated proximal gradient，APG）為了得到更新A和E時的步長，需先確定參數(shù)k+1：于是A和E的迭代更新公式為:參數(shù)的迭代公式為其中： 為事先給定的正數(shù)；0。盡管與算法類似，但它卻大大降低了迭代

5、次數(shù)。第9頁，共38頁，2022年，5月20日，1點8分，星期六由于核范數(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）第10頁，共38頁，2022年，5月20日，1

6、點8分，星期六增廣拉格朗日乘子法（augmented Lagrange multipliers,ALM）構(gòu)造增廣拉格朗日函數(shù)：當(dāng)k， k ，使用交替式方法求解塊優(yōu)化問題 min , (,k, k )。使用精確拉格朗日乘子法交替迭代矩陣和，直到滿足終止條件為止。若 則第11頁，共38頁，2022年，5月20日，1點8分，星期六第12頁，共38頁，2022年，5月20日，1點8分，星期六交替方向方法（alternating direction methods，ADM，IALM）ADM對ALM做了改善，即不精確拉格朗日乘子法（inexactALM它不需要求 的精確解，即矩陣和的迭代更新公式為：第13

7、頁，共38頁，2022年，5月20日，1點8分，星期六求解方法性能比較第14頁，共38頁，2022年，5月20日，1點8分，星期六低秩矩陣恢復(fù)應(yīng)用圖像恢復(fù)第15頁，共38頁，2022年，5月20日，1點8分，星期六低秩矩陣恢復(fù)應(yīng)用圖像去光照影響恢復(fù)第16頁，共38頁，2022年，5月20日，1點8分，星期六低秩矩陣恢復(fù)應(yīng)用視頻背景建模Cands, Li, Ma, and W., JACM, May 2011.第17頁，共38頁，2022年，5月20日，1點8分，星期六低秩矩陣恢復(fù)應(yīng)用圖像類別標簽凈化第18頁，共38頁，2022年，5月20日，1點8分，星期六低秩矩陣恢復(fù)應(yīng)用文本主題分析傳統(tǒng)PC

8、ARPCA第19頁，共38頁，2022年，5月20日，1點8分，星期六低秩矩陣恢復(fù)應(yīng)用音樂詞曲分離第20頁，共38頁，2022年，5月20日，1點8分，星期六低秩矩陣恢復(fù)應(yīng)用圖像矯正與去噪第21頁，共38頁，2022年，5月20日，1點8分，星期六低秩矩陣恢復(fù)應(yīng)用圖像對齊第22頁，共38頁，2022年，5月20日，1點8分，星期六低秩矩陣補全當(dāng)數(shù)據(jù)矩陣含丟失元素時，可根據(jù)矩陣的低秩結(jié)構(gòu)來恢復(fù)矩陣的所有元素，稱此恢復(fù)過程為矩陣補全（）。記為集合的子集，這里表示集合,。的原始模型可描述為如下的優(yōu)化問題： 其中： 為一線性投影算子，即為便于優(yōu)化，凸松弛后轉(zhuǎn)化為：第23頁，共38頁，2022年，5月2

9、0日，1點8分，星期六低秩矩陣補全求解問題可應(yīng)用算法求解，將原優(yōu)化問題重新表示為：于是構(gòu)造上述問題的部分增廣拉格朗日函數(shù)為第24頁，共38頁，2022年，5月20日，1點8分，星期六低秩矩陣補全應(yīng)用智能推薦系統(tǒng)第25頁，共38頁，2022年，5月20日，1點8分，星期六低秩矩陣補全應(yīng)用電影去雨線處理第26頁，共38頁，2022年，5月20日，1點8分，星期六低秩矩陣表示（LRR）低秩矩陣表示（LRR）是將數(shù)據(jù)集矩陣表示成字典矩陣（也稱為基矩陣）下的線性組合，即，并希望線性組合系數(shù)矩陣是低秩的。為此，需要求解下列優(yōu)化問題： 為便于優(yōu)化，凸松弛后轉(zhuǎn)化為： 若選取數(shù)據(jù)集本身作為字典，則有 那么其解為

10、 ，這里 是D的SVD分解。 當(dāng)D是從多個獨立子空間的采樣組合，那么 為對角塊矩陣，每個塊對應(yīng)著一個子空間。此即為子空間聚類（Sparse Subspace Clustering）。第27頁，共38頁，2022年，5月20日，1點8分，星期六低秩矩陣表示（LRR）為了對噪聲和野點更加魯棒，一個更合理的模型為：一般意義上的LRR可以看做：第28頁，共38頁，2022年，5月20日，1點8分，星期六低秩矩陣表示求解構(gòu)造上述優(yōu)化問題的增廣拉格朗日乘子函數(shù)為當(dāng) 時,的更新公式為的更新公式為的更新公式為拉格朗日乘子的迭代公式為參數(shù)的更新式為第29頁，共38頁，2022年，5月20日，1點8分，星期六低秩

11、矩陣表示的應(yīng)用圖像分割B. Cheng et al. Multi-task Low-rank Affinity Pursuit for Image Segmentation, ICCV 2011. 第30頁，共38頁，2022年，5月20日，1點8分，星期六低秩矩陣表示的應(yīng)用顯著性檢測Lang et al. Saliency Detection by Multitask Sparsity Pursuit. IEEE TIP 2012. 第31頁，共38頁，2022年，5月20日，1點8分，星期六低秩矩陣表示新近的發(fā)展研究Latent LRRLiu and Yan. Latent Low-Ran

12、k Representation for Subspace Segmentation and Feature Extraction, ICCV 2011. 第32頁，共38頁，2022年，5月20日，1點8分，星期六低秩矩陣表示新近的發(fā)展研究Fixed Rank Representation (FRR) Liu, Lin, Torre, and Su, Fixed-Rank Representation for Unsupervised Visual Learning, CVPR 2012. 第33頁，共38頁，2022年，5月20日，1點8分，星期六低秩矩陣表示新近的發(fā)展研究Kernel LRR Wang et al., Structural Similarity and Distance in Learning, Annual Allerton Conf. Communication, Control and Computing 2011. 第34頁，共38頁，2022年，5月20日，1點8分，星期六低秩矩陣表示新近的發(fā)展研究基于低秩張量應(yīng)用研究第35頁，共38頁，2022年，5月20日，1點8分，星期六低秩矩陣表示新近的發(fā)展研究基于低秩張量應(yīng)用研究第36頁，共38頁，2022年，5月20日，1點8分，星期六稀疏表示和矩陣低秩分解類比第37頁