矩阵低秩分解理论PPT学习课件.ppt

1、矩阵低秩分解理论及其应用分析,成科扬 2013年9月4日,1,从稀疏表示到低秩分解,稀疏表示 压缩感知(Compressed sensing),2,从稀疏表示到低秩分解,矩阵低秩分解 矩阵低秩稀疏分解(Sparse and low-rank matrix decomposition) 低秩矩阵恢复（Low-rank Matrix Recovery） 鲁棒主成分分析(Robust principle component analysis, RPCA) 低秩稀疏非相干分解(Rank-sparsity incoherence),observation,low-rank,sparse,3,预备知识,4

2、,低秩矩阵恢复（鲁棒主成分分析RPCA）,在许多实际应用中，给定的数据矩阵往往是低秩或近似低秩的，但存在随机幅值任意大但是分布稀疏的误差破坏了原有数据的低秩性，为了恢复矩阵的低秩结构，可将矩阵分解为两个矩阵之和，即，其中矩阵和未知，但是低秩的。当矩阵的元素服从独立同分布的高斯分布时，可用经典的PCA来获得最优的矩阵，即求解下列最优化问题： 当为稀疏的大噪声矩阵时，问题转化为双目标优化问题： 引入折中因子，将双目标优化问题转换为单目标优化问题：,5,RPCA的求解,凸松弛,NP难问题 松弛后,矩阵核范数,6,迭代阈值算法（iterative thresholding，IT）,将最优化问题正则化，

3、便得到优化问题： 优化问题式的拉格朗日函数为 使用迭代阈值算法交替更新矩阵,和。当=k，=k时， 当k+1，k时， 当k+1 ，k+1时， 其中：步长k满足 k 1 算法的迭代式形式简单且收敛，但它的收敛速度比较慢，且难以选取合适的步长,7,加速近端梯度算法（accelerated proximal gradient，APG）,将优化问题式的等式约束松弛到目标函数中，得到如下的拉格朗日函数： 记 于是L(,)=(,)+(,)。函数(,)不可微，而(,)光滑且具有李普希兹连续梯度，即存在Lf0，使得 其中： 表示函数(,)关于矩阵变量和的梯度。此处取Lf =。对于给定的与同型的两个矩阵A和E，作

4、(,)的部分二次逼近：,8,加速近端梯度算法（accelerated proximal gradient，APG）,为了得到更新A和E时的步长，需先确定参数k+1： 于是A和E的迭代更新公式为: 参数的迭代公式为 其中： 为事先给定的正数；0。 尽管与算法类似，但它却大大降低了迭代次数。,9,由于核范数的对偶范数为谱范数，所以优化问题的对偶问题为： 其中： 表示矩阵元素绝对值最大的值。当优化问题对偶式取得最优值 时，必定满足 即此优化问题等价于： 上述优化问题是非线性、非光滑的，可以使用最速上升法求解。当 时，定义正规锥 其中 表示函数(.)的次梯度。此时，优化问题的最速上升方向为k，其中k为

5、在(k)上的投影。使用线性搜索方法确定步长大小： 于是k的更新过程为 DULL比APG算法具有更好的可扩展性，这是因为在每次迭代过程中对偶方法不需要矩阵的完全奇异值分解。,对偶方法（DUL）,10,增广拉格朗日乘子法（augmented Lagrange multipliers,ALM）,构造增广拉格朗日函数： 当k， k ，使用交替式方法求解块优化问题 min , (,k, k )。 使用精确拉格朗日乘子法交替迭代矩阵和，直到满足终止条件为止。若 则,11,再更新矩阵: 记 分别收敛于 ，则矩阵的更新公式为 最后更新参数： 其中：为常数；为比较小的正数。,12,交替方向方法（alternat

6、ing direction methods，ADM，IALM）,ADM对ALM做了改善，即不精确拉格朗日乘子法（inexactALM它不需要求 的精确解，即矩阵和的迭代更新公式为：,13,求解方法性能比较,14,低秩矩阵恢复应用,图像恢复,15,低秩矩阵恢复应用,图像去光照影响恢复,16,低秩矩阵恢复应用,视频背景建模 Cands, Li, Ma, and W., JACM, May 2011.,17,低秩矩阵恢复应用,图像类别标签净化,18,低秩矩阵恢复应用,文本主题分析,传统PCA,RPCA,19,低秩矩阵恢复应用,音乐词曲分离,20,低秩矩阵恢复应用,图像矫正与去噪,21,低秩矩阵恢复应

7、用,图像对齐,22,低秩矩阵补全,当数据矩阵含丢失元素时，可根据矩阵的低秩结构来恢复矩阵的所有元素，称此恢复过程为矩阵补全（）。 记为集合的子集，这里表示集合,。的原始模型可描述为如下的优化问题： 其中： 为一线性投影算子，即 为便于优化，凸松弛后转化为：,23,低秩矩阵补全求解,问题可应用算法求解，将原优化问题重新表示为： 于是构造上述问题的部分增广拉格朗日函数为,24,低秩矩阵补全应用,智能推荐系统,25,低秩矩阵补全应用,电影去雨线处理,26,低秩矩阵表示（LRR）,低秩矩阵表示（LRR）是将数据集矩阵表示成字典矩阵（也称为基矩阵）下的线性组合，即，并希望线性组合系数矩阵是低秩的。为此，

8、需要求解下列优化问题： 为便于优化，凸松弛后转化为： 若选取数据集本身作为字典，则有 那么其解为 ，这里 是D的SVD分解。 当D是从多个独立子空间的采样组合，那么 为对角块矩阵，每个块对应着一个子空间。此即为子空间聚类（Sparse Subspace Clustering）。,27,低秩矩阵表示（LRR）,为了对噪声和野点更加鲁棒，一个更合理的模型为： 一般意义上的LRR可以看做：,28,低秩矩阵表示求解,构造上述优化问题的增广拉格朗日乘子函数为 当 时,的更新公式为 的更新公式为 的更新公式为 拉格朗日乘子的迭代公式为 参数的更新式为,29,低秩矩阵表示的应用,图像分割 B. Cheng

9、et al. Multi-task Low-rank Affinity Pursuit for Image Segmentation, ICCV 2011.,30,低秩矩阵表示的应用,显著性检测 Lang et al. Saliency Detection by Multitask Sparsity Pursuit. IEEE TIP 2012.,31,低秩矩阵表示新近的发展研究,Latent LRR Liu and Yan. Latent Low-Rank Representation for Subspace Segmentation and Feature Extraction, ICC

10、V 2011.,32,低秩矩阵表示新近的发展研究,Fixed Rank Representation (FRR),Liu, Lin, Torre, and Su, Fixed-Rank Representation for Unsupervised Visual Learning, CVPR 2012.,33,低秩矩阵表示新近的发展研究,Kernel LRR Wang et al., Structural Similarity and Distance in Learning, Annual Allerton Conf. Communication, Control and Computing 2011.,34,低秩矩阵表示新近的发展研究,基于低秩张量应用研究,35,低秩矩阵表示新近的发展研究,基于低秩张量应用研究,36,稀疏表示和矩阵低秩分