矩陣低秩分解理論

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

2、rse第三張，PPT共三十八頁，創(chuàng)作于2022年6月預備知識第四張，PPT共三十八頁，創(chuàng)作于2022年6月低秩矩陣恢復（魯棒主成分分析RPCA）在許多實際應用中，給定的數(shù)據(jù)矩陣往往是低秩或近似低秩的，但存在隨機幅值任意大但是分布稀疏的誤差破壞了原有數(shù)據(jù)的低秩性，為了恢復矩陣的低秩結構，可將矩陣分解為兩個矩陣之和，即，其中矩陣和未知，但是低秩的。當矩陣的元素服從獨立同分布的高斯分布時，可用經典的PCA來獲得最優(yōu)的矩陣，即求解下列最優(yōu)化問題： 當為稀疏的大噪聲矩陣時，問題轉化為雙目標優(yōu)化問題： 引入折中因子，將雙目標優(yōu)化問題轉換為單目標優(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ù)為使用迭代閾值算法交替更新矩陣,和。當=k，=k時，當k+1，k時，當k+1 ，k+1時，其中：步長k滿足 k 1算法的迭代式形式簡單且收斂，但它的收斂速度比較慢，且難以選取合適的步長第七張，PPT共三十八頁，創(chuàng)作于2022年6月加速近端梯度算法（accelerated proximal gradient，APG）將優(yōu)化問題式的等式約束松弛到目標函數(shù)中，得到如下的拉格朗日函數(shù)： 記于是

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

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

6、日函數(shù)：當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對ALM做了改善，即不精確拉格朗日乘子法（inexactALM它不需要求 的精確解，即矩陣和的迭代更新公式為：第十三張，PPT共三十八頁，創(chuàng)作于2022年6月求解方法

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

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

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

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

11、22年6月低秩矩陣表示的應用顯著性檢測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. 第