矩阵低秩分解理论PPT.ppt

矩阵低秩分解理论及其应用分析矩阵低秩分解理论及其应用分析成科扬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)observationlow-ranksparse3预备知识4低秩矩阵恢复（鲁棒主成分分析RPCA）在许多实际应用中，给定的数据矩阵往往是低秩或近似低秩的，但存在随机幅值任意大但是分布稀疏的误差破坏了原有数据的低秩性，为了恢复矩阵的低秩结构，可将矩阵分解为两个矩阵之和，即，其中矩阵和未知，但是低秩的。当矩阵的元素服从独立同分布的高斯分布时，可用经典的PCA来获得最优的矩阵，即求解下列最优化问题：当为稀疏的大噪声矩阵时，问题转化为双目标优化问题：引入折中因子，将双目标优化问题转换为单目标优化问题：5RPCA的求解凸松弛NP难问题松弛后矩阵核范数6迭代阈值算法（iterative thresholding，IT）将最优化问题正则化，便得到优化问题：优化问题式的拉格朗日函数为使用迭代阈值算法交替更新矩阵,和。当=k，=k时，当k+1，k时，当k+1，k+1时，其中：步长k满足 k 1算法的迭代式形式简单且收敛，但它的收敛速度比较慢，且难以选取合适的步长7加速近端梯度算法（accelerated proximal gradient，APG）将优化问题式的等式约束松弛到目标函数中，得到如下的拉格朗日函数：记于是L(,)=(,)+(,)。函数(,)不可微，而(,)光滑且具有李普希兹连续梯度，即存在Lf0，使得 其中：表示函数(,)关于矩阵变量和的梯度。此处取Lf=。对于给定的与同型的两个矩阵A和E，作(,)的部分二次逼近：8加速近端梯度算法（accelerated proximal gradient，APG）为了得到更新A和E时的步长，需先确定参数k+1：于是A和E的迭代更新公式为:参数的迭代公式为其中：为事先给定的正数；0。尽管与算法类似，但它却大大降低了迭代次数。9由于核范数的对偶范数为谱范数，所以优化问题的对偶问题为：其中：表示矩阵元素绝对值最大的值。当优化问题对偶式取得最优值 时，必定满足 即此优化问题等价于：上述优化问题是非线性、非光滑的，可以使用最速上升法求解。当 时，定义正规锥 其中 表示函数(.)的次梯度。此时，优化问题的最速上升方向为k，其中k为在(k)上的投影。使用线性搜索方法确定步长大小：于是k的更新过程为DULL比APG算法具有更好的可扩展性，这是因为在每次迭代过程中对偶方法不需要矩阵的完全奇异值分解。对偶方法（DUL）10增广拉格朗日乘子法（augmented Lagrange multipliers,ALM）构造增广拉格朗日函数：当k，k，使用交替式方法求解块优化问题 min,(,k,k)。使用精确拉格朗日乘子法交替迭代矩阵和，直到满足终止条件为止。若 则11再更新矩阵:记 分别收敛于 ，则矩阵的更新公式为最后更新参数：其中：为常数；为比较小的正数。12交替方向方法（alternating direction methods，ADM，IALM）ADM对ALM做了改善，即不精确拉格朗日乘子法（inexactALM它不需要求 的精确解，即矩阵和的迭代更新公式为：13求解方法性能比较14低秩矩阵恢复应用图像恢复15低秩矩阵恢复应用图像去光照影响恢复16低秩矩阵恢复应用视频背景建模Cands,Li,Ma,and W.,JACM,May 2011.17低秩矩阵恢复应用图像类别标签净化18低秩矩阵恢复应用文本主题分析传统PCARPCA19低秩矩阵恢复应用音乐词曲分离20低秩矩阵恢复应用图像矫正与去噪21低秩矩阵恢复应用图像对齐22低秩矩阵补全当数据矩阵含丢失元素时，可根据矩阵的低秩结构来恢复矩阵的所有元素，称此恢复过程为矩阵补全（）。记为集合的子集，这里表示集合,。的原始模型可描述为如下的优化问题：其中：为一线性投影算子，即为便于优化，凸松弛后转化为：23低秩矩阵补全求解问题可应用算法求解，将原优化问题重新表示为：于是构造上述问题的部分增广拉格朗日函数为24低秩矩阵补全应用智能推荐系统25低秩矩阵补全应用电影去雨线处理26低秩矩阵表示（LRR）低秩矩阵表示（LRR）是将数据集矩阵表示成字典矩阵（也称为基矩阵）下的线性组合，即，并希望线性组合系数矩阵是低秩的。为此，需要求解下列优化问题：为便于优化，凸松弛后转化为：若选取数据集本身作为字典，则有 那么其解为 ，这里 是D的SVD分解。当D是从多个独立子空间的采样组合，那么 为对角块矩阵，每个块对应着一个子空间。此即为子空间聚类（Sparse Subspace Clustering）。27低秩矩阵表示（LRR）为了对噪声和野点更加鲁棒，一个更合理的模型为：一般意义上的LRR可以看做：28低秩矩阵表示求解构造上述优化问题的增广拉格朗日乘子函数为当 时,的更新公式为的更新公式为的更新公式为拉格朗日乘子的迭代公式为参数的更新式为29低秩矩阵表示的应用图像分割B.Cheng 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 LRRLiu and Yan.Latent Low-Rank Representation for Subspace Segmentation and Feature Extraction,ICCV 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稀疏表示和矩阵低秩分解类比37研究展望：理论方面：需要研究在稀疏性或(和)低秩性之外,如何更进一步地去发现和利用数据中潜在的本质结构。算法方面：需要充分利用问题的结构和现有的硬件条件,开发快速的、并行的算法变性。应用方面：需要根据应用问题本身的物理意义,设计合理的数学模型,使用现代凸优化方法进行高效的求解。38