矩陣低秩分解理論

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

2、陣恢復（魯棒主成分分析RPCA） 在許多實際應用中，給定的數據矩陣往往是低秩或近似低秩的，但存在隨機幅值任意大但是分布稀疏的誤差破壞了原有數據的低秩性，為了恢復矩陣的低秩結構，可將矩陣分解為兩個矩陣之和，即，其中矩陣和未知，但是低秩的。當矩陣的元素服從獨立同分布的高斯分布時，可用經典的PCA來獲得最優(yōu)的矩陣，即求解下列最優(yōu)化問題： 當為稀疏的大噪聲矩陣時，問題轉化為雙目標優(yōu)化問題： 引入折中因子，將雙目標優(yōu)化問題轉換為單目標優(yōu)化問題：RPCA的求解 凸松弛NP難問題松弛后矩陣核范數迭代閾值算法（iterative thresholding，IT）將最優(yōu)化問題正則化，便得到優(yōu)化問題：優(yōu)化問題式的

3、拉格朗日函數為使用迭代閾值算法交替更新矩陣,和。當=k，=k時，當k+1，k時，當k+1 ，k+1時，其中：步長k滿足 k 1算法的迭代式形式簡單且收斂，但它的收斂速度比較慢，且難以選取合適的步長加速近端梯度算法（accelerated proximal gradient，APG）將優(yōu)化問題式的等式約束松弛到目標函數中，得到如下的拉格朗日函數： 記于是L(,)=(,)+(,)。函數(,)不可微，而(,)光滑且具有李普希茲連續(xù)梯度，即存在Lf0，使得 其中： 表示函數(,)關于矩陣變量和的梯度。此處取Lf =。對于給定的與同型的兩個矩陣A和E，作(,)的部分二次逼近：加速近端梯度算法（accel

4、erated proximal gradient，APG）為了得到更新A和E時的步長，需先確定參數k+1：于是A和E的迭代更新公式為:參數的迭代公式為其中： 為事先給定的正數；0。盡管與算法類似，但它卻大大降低了迭代次數。 由于核范數的對偶范數為譜范數，所以優(yōu)化問題的對偶問題為： 其中： 表示矩陣元素絕對值最大的值。當優(yōu)化問題對偶式取得最優(yōu)值 時，必定滿足 即此優(yōu)化問題等價于： 上述優(yōu)化問題是非線性、非光滑的，可以使用最速上升法求解。當 時，定義正規(guī)錐 其中 表示函數(.)的次梯度。此時，優(yōu)化問題的最速上升方向為k，其中k為在(k)上的投影。使用線性搜索方法確定步長大?。?于是k的更新過程為

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

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

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

8、魯棒，一個更合理的模型為：一般意義上的LRR可以看做：低秩矩陣表示求解 構造上述優(yōu)化問題的增廣拉格朗日乘子函數為 當 時,的更新公式為的更新公式為的更新公式為拉格朗日乘子的迭代公式為參數的更新式為低秩矩陣表示的應用 圖像分割B. Cheng et al. Multi-task Low-rank Affinity Pursuit for Image Segmentation, ICCV 2011. 低秩矩陣表示的應用 顯著性檢測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ā)展研究 基于低秩張量應用研究低秩矩陣表示新近的發(fā)展研究 基于低秩張量應用研究稀疏表示和矩陣低秩分解類