矩阵低秩分解理论

1、矩阵低秩分解理论第1页，共38页，2022年，5月20日，1点8分，星期六从稀疏表示到低秩分解稀疏表示压缩感知(Compressed sensing)第2页，共38页，2022年，5月20日，1点8分，星期六从稀疏表示到低秩分解矩阵低秩分解矩阵低秩稀疏分解(Sparse and low-rank matrix decomposition)低秩矩阵恢复（Low-rank Matrix Recovery）鲁棒主成分分析(Robust principle component analysis, RPCA)低秩稀疏非相干分解(Rank-sparsity incoherence)observationl

2、ow-ranksparse第3页，共38页，2022年，5月20日，1点8分，星期六预备知识第4页，共38页，2022年，5月20日，1点8分，星期六低秩矩阵恢复（鲁棒主成分分析RPCA）在许多实际应用中，给定的数据矩阵往往是低秩或近似低秩的，但存在随机幅值任意大但是分布稀疏的误差破坏了原有数据的低秩性，为了恢复矩阵的低秩结构，可将矩阵分解为两个矩阵之和，即，其中矩阵和未知，但是低秩的。当矩阵的元素服从独立同分布的高斯分布时，可用经典的PCA来获得最优的矩阵，即求解下列最优化问题： 当为稀疏的大噪声矩阵时，问题转化为双目标优化问题： 引入折中因子，将双目标优化问题转换为单目标优化问题：第5页，

3、共38页，2022年，5月20日，1点8分，星期六RPCA的求解凸松弛NP难问题松弛后矩阵核范数第6页，共38页，2022年，5月20日，1点8分，星期六迭代阈值算法（iterative thresholding，IT）将最优化问题正则化，便得到优化问题：优化问题式的拉格朗日函数为使用迭代阈值算法交替更新矩阵,和。当=k，=k时，当k+1，k时，当k+1 ，k+1时，其中：步长k满足 k 1算法的迭代式形式简单且收敛，但它的收敛速度比较慢，且难以选取合适的步长第7页，共38页，2022年，5月20日，1点8分，星期六加速近端梯度算法（accelerated proximal gradient，

4、APG）将优化问题式的等式约束松弛到目标函数中，得到如下的拉格朗日函数： 记于是L(,)=(,)+(,)。函数(,)不可微，而(,)光滑且具有李普希兹连续梯度，即存在Lf0，使得 其中： 表示函数(,)关于矩阵变量和的梯度。此处取Lf =。对于给定的与同型的两个矩阵A和E，作(,)的部分二次逼近：第8页，共38页，2022年，5月20日，1点8分，星期六加速近端梯度算法（accelerated proximal gradient，APG）为了得到更新A和E时的步长，需先确定参数k+1：于是A和E的迭代更新公式为:参数的迭代公式为其中： 为事先给定的正数；0。尽管与算法类似，但它却大大降低了迭代

5、次数。第9页，共38页，2022年，5月20日，1点8分，星期六由于核范数的对偶范数为谱范数，所以优化问题的对偶问题为： 其中： 表示矩阵元素绝对值最大的值。当优化问题对偶式取得最优值 时，必定满足 即此优化问题等价于： 上述优化问题是非线性、非光滑的，可以使用最速上升法求解。当 时，定义正规锥 其中 表示函数(.)的次梯度。此时，优化问题的最速上升方向为k，其中k为在(k)上的投影。使用线性搜索方法确定步长大小：于是k的更新过程为DULL比APG算法具有更好的可扩展性，这是因为在每次迭代过程中对偶方法不需要矩阵的完全奇异值分解。对偶方法（DUL）第10页，共38页，2022年，5月20日，1

6、点8分，星期六增广拉格朗日乘子法（augmented Lagrange multipliers,ALM）构造增广拉格朗日函数：当k， k ，使用交替式方法求解块优化问题 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分，星期六低秩矩阵恢复应用图像恢复第15页，共38页，2022年，5月20日，1点8分，星期六低秩矩阵恢复应用图像去光照影响恢复第16页，共38页，2022年，5月20日，1点8分，星期六低秩矩阵恢复应用视频背景建模Cands, Li, Ma, and W., JACM, May 2011.第17页，共38页，2022年，5月20日，1点8分，星期六低秩矩阵恢复应用图像类别标签净化第18页，共38页，2022年，5月20日，1点8分，星期六低秩矩阵恢复应用文本主题分析传统PC

8、ARPCA第19页，共38页，2022年，5月20日，1点8分，星期六低秩矩阵恢复应用音乐词曲分离第20页，共38页，2022年，5月20日，1点8分，星期六低秩矩阵恢复应用图像矫正与去噪第21页，共38页，2022年，5月20日，1点8分，星期六低秩矩阵恢复应用图像对齐第22页，共38页，2022年，5月20日，1点8分，星期六低秩矩阵补全当数据矩阵含丢失元素时，可根据矩阵的低秩结构来恢复矩阵的所有元素，称此恢复过程为矩阵补全（）。记为集合的子集，这里表示集合,。的原始模型可描述为如下的优化问题： 其中： 为一线性投影算子，即为便于优化，凸松弛后转化为：第23页，共38页，2022年，5月2

9、0日，1点8分，星期六低秩矩阵补全求解问题可应用算法求解，将原优化问题重新表示为：于是构造上述问题的部分增广拉格朗日函数为第24页，共38页，2022年，5月20日，1点8分，星期六低秩矩阵补全应用智能推荐系统第25页，共38页，2022年，5月20日，1点8分，星期六低秩矩阵补全应用电影去雨线处理第26页，共38页，2022年，5月20日，1点8分，星期六低秩矩阵表示（LRR）低秩矩阵表示（LRR）是将数据集矩阵表示成字典矩阵（也称为基矩阵）下的线性组合，即，并希望线性组合系数矩阵是低秩的。为此，需要求解下列优化问题： 为便于优化，凸松弛后转化为： 若选取数据集本身作为字典，则有 那么其解为

10、 ，这里 是D的SVD分解。 当D是从多个独立子空间的采样组合，那么 为对角块矩阵，每个块对应着一个子空间。此即为子空间聚类（Sparse Subspace Clustering）。第27页，共38页，2022年，5月20日，1点8分，星期六低秩矩阵表示（LRR）为了对噪声和野点更加鲁棒，一个更合理的模型为：一般意义上的LRR可以看做：第28页，共38页，2022年，5月20日，1点8分，星期六低秩矩阵表示求解构造上述优化问题的增广拉格朗日乘子函数为当 时,的更新公式为的更新公式为的更新公式为拉格朗日乘子的迭代公式为参数的更新式为第29页，共38页，2022年，5月20日，1点8分，星期六低秩

11、矩阵表示的应用图像分割B. Cheng et al. Multi-task Low-rank Affinity Pursuit for Image Segmentation, ICCV 2011. 第30页，共38页，2022年，5月20日，1点8分，星期六低秩矩阵表示的应用显著性检测Lang et al. Saliency Detection by Multitask Sparsity Pursuit. IEEE TIP 2012. 第31页，共38页，2022年，5月20日，1点8分，星期六低秩矩阵表示新近的发展研究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分，星期六低秩矩阵表示新近的发展研究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分，星期六低秩矩阵表示新近的发展研究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分，星期六低秩矩阵表示新近的发展研究基于低秩张量应用研究第35页，共38页，2022年，5月20日，1点8分，星期六低秩矩阵表示新近的发展研究基于低秩张量应用研究第36页，共38页，2022年，5月20日，1点8分，星期六稀疏表示和矩阵低秩分解类比第37页