牛顿-软阈值迭代鲁棒主成分分析算法

doi:10.11772/j.issn.1001-9081.2020030375

计算机应用 ›› 2020, Vol. 40 ›› Issue (11): 3133-3138.DOI: 10.11772/j.issn.1001-9081.2020030375

牛顿-软阈值迭代鲁棒主成分分析算法

王海鹏, 降爱莲, 李鹏翔

太原理工大学信息与计算机学院, 山西晋中 030600

收稿日期:2020-03-30 修回日期:2020-06-15 出版日期:2020-11-10 发布日期:2020-06-23
通讯作者: 降爱莲(1969-),女,山西太原人,副教授,博士,CCF会员,主要研究方向:人工智能、大数据、特征选择、计算机视觉;ailianjiang@126.com
作者简介:王海鹏(1996-),男,山东潍坊人,硕士研究生,主要研究方向:机器学习、特征提取;李鹏翔(1992-),男,山西吕梁人,硕士研究生,主要研究方向:机器学习、异常检测
基金资助:
山西省回国留学人员科研资助项目（2017-051）。

Newton-soft threshold iteration algorithm for robust principal component analysis

WANG Haipeng, JIANG Ailian, LI Pengxiang

College of Information and Computer, Taiyuan University of Technology, Jinzhong Shanxi 030600, China

Received:2020-03-30 Revised:2020-06-15 Online:2020-11-10 Published:2020-06-23
Supported by:
This work is partially supported by the Research Project Supported by Shanxi Scholarship Council of China (2017-051).

摘要/Abstract

摘要： 针对鲁棒主成分分析（RPCA）问题，为了降低RPCA算法的时间复杂度，提出了牛顿-软阈值迭代（NSTI）算法。首先，使用低秩矩阵的Frobenius范数与稀疏矩阵的l₁-范数的和来构造NSTI算法的模型；其次，同时使用两种不同的优化方式求解模型的不同部分，即用牛顿法快速计算出低秩矩阵，用软阈值迭代算法快速计算出稀疏矩阵，交替使用这两种方法计算出原数据的低秩矩阵和稀疏矩阵的分解；最后，得到原始数据的低秩特征。在数据规模为5 000×5 000，低秩矩阵的秩为20的情况下，NSTI算法和梯度下降（GD）算法、低秩矩阵拟合（LMaFit）算法相比，时间效率分别提高了24.6%、45.5%。对180帧的视频前景背景进行分离，NSTI耗时3.63 s，时间效率比GD算法、LMaFit算法分别高78.7%、82.1%。图像降噪实验中，NSTI算法耗时0.244 s，所得到的降噪后的图像与原始图像的残差为0.381 3，与GD算法、LMaFit算法相比，时间效率和精确度分别提高了64.3%和45.3%。实验结果证明，NSTI算法能够有效解决RPCA问题并提升RPCA算法的时间效率。

关键词: 鲁棒主成分分析, 特征提取, 图像降噪, 软阈值迭代, 牛顿法

Abstract: Aiming at Robust Principal Component Analysis (RPCA) problem, a Newton-Soft Threshold Iteration (NSTI) algorithm was proposed for reducing time complexity of RPCA algorithm. Firstly, the NSTI algorithm model was constructed by using the sum of the Frobenius norm of the low-rank matrix and the l₁-norm of the sparse matrix. Secondly, two different optimization methods were used to calculate different parts of the model at the same time. Newton method was used to quickly calculate the low-rank matrix. Soft threshold iteration algorithm was used to quickly calculate the sparse matrix. The decomposition of low-rank matrix and sparse matrix of original data was calculated by alternately using the two optimization methods. Finally, the low-rank features of the original data were obtained. Under the condition that the data scale is 5 000×5 000 and rank of the low-rank matrix is 20, NSTI algorithm can improve the time efficiency by 24.6% and 45.5% compared with Gradient Descent (GD) algorithm and Low-Rank Matrix Fitting (LMaFit) algorithm. For foreground and background separation of 180-frame video, NSTI takes 3.63 s and has the time efficiency 78.7% and 82.1% higher than GD algorithm and LMaFit algorithm. In the experiment of image denoising, NSTI algorithm takes 0.244 s, and the residual error of the image processed by NSTI and the original image is 0.381 3, showing that the time efficiency and the accuracy of the proposed algorithm are 64.3% more efficient and 45.3% more accurate than those of GD algorithm and LMaFit algorithm. Experimental results prove that NSTI algorithm can effectively solve the RPCA problem and improve the time efficiency of the RPCA algorithm.

Key words: Robust Principal Component Analysis (RPCA), feature extraction, image denoising, soft threshold iteration, Newton method

中图分类号:

王海鹏, 降爱莲, 李鹏翔. 牛顿-软阈值迭代鲁棒主成分分析算法[J]. 计算机应用, 2020, 40(11): 3133-3138.

WANG Haipeng, JIANG Ailian, LI Pengxiang. Newton-soft threshold iteration algorithm for robust principal component analysis[J]. Journal of Computer Applications, 2020, 40(11): 3133-3138.

参考文献

[1] WAN G,MAUNG C,SCHWEITZER H. Improving the accuracy of principalcomponent analysis by the maximum entropy method[EB/OL].[2019-12-19]. https://arxiv.org/pdf/1907.11094.pdf.
[2] BOUWMANS T, ZAHZAH E. Robust PCA via principalcomponent pursuit:a review for acomparative evaluation in video surveillance[J]. Computer Vision and Image Understanding, 2014,122:22-34.
[3] 陈利霞, 刘俊丽, 王学文. 结合加权Schatten-p范数与3D全变分的前景检测[J]. 计算机应用,2019,39(4):1170-1175. (CHEN L X, LIU J L, WANG X W. Foreground detectioncombining weighted Schatten-p norm with 3D total variation[J]. Journal of Computer Applications,2019,39(4):1170-1175.)
[4] 宣晓, 余勤. 基于截断核范数的视频前景与背景分离[J]. 计算机工程与设计,2018,39(5):1415-1421.(XUAN X,YU Q. Video foreground-background separation based on truncated nuclear norm[J]. Computer Engineering and Design,2018,39(5):1415-1421.)
[5] WRIGHT J, YANG A Y, GANESH A, et al. Robust face recognition via sparse representation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31(2):210-227.
[6] JAVED S,MAHMOOD A,Al-MAADEED S,et al. Moving object detection incomplex scene using spatiotemporal structured-sparse RPCA[J]. IEEE Transactions on Image Processing,2019,28(2):1007-1022.
[7] CANDÈS E J,LI X,MA Y,et al. Robust principalcomponent analysis[J]. Journal of the ACM,2011,58(3):No. 11.
[8] GILLIS N,VAVASIS S A. On thecomplexity of robust PCA and l₁-norm low-rank matrix approximation[J]. Mathematics of Operations Research,2018,43(4):1072-1084.
[9] LIN Z,CHEN M,MA Y. The augmented Lagrange multiplier method for exact recovery of corrupted low-rank matrices[EB/OL].[2019-12-19]. https://arxiv.org/pdf/1009.5055.pdf.
[10] SHEN Y,WEN Z,ZHANG Y. Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization[J]. Optimization Methods and Software,2014,29(2):239-263.
[11] YI X,PARK D,CHEN Y,et al. Fast algorithms for robust PCA via gradient descent[C]//Proceedings of the 30th International Conference on Neural Information Processing Systems. Red Hook, NY:Curran Associates Inc.,2016:4159-4167.
[12] LU C, FENG J, CHEN Y, et al. Tensor robust principalcomponent analysis with a new tensor nuclear norm[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2020, 42(4):925-938.
[13] CHEREAU J P,DEES B S,MANDIC D P. Robust principalcomponent analysis based on maximum correntropy power iterations[EB/OL].[2019-12-19]. https://arxiv.org/pdf/1910.11374.pdf.
[14] WOLD S, ESBENSEN K, GELADI P. Principalcomponent analysis[J]. Chemometrics and Intelligent Laboratory Systems, 1987,2(1/2/3):37-52.
[15] BIOUCAS-DIAS J M,FIGUEIREDO M A T. A new TwIST:twostep iterative shrinkage/thresholding algorithms for image restoration[J]. IEEE Transactions on Image Processing,2007,16(12):2992-3004.
[16] MA S,AYBAT N S. Efficient optimization algorithms for robust principalcomponent analysis and its variants[J]. Proceedings of the IEEE,2018,106(8):1411-1426.
[17] VASWANI N, BOUWMANS T, JAVED S, et al. Robust subspace learning:robust PCA,robust subspace tracking,and robust subspace recovery[J]. IEEE Signal Processing Magazine, 2018,35(4):32-55.

牛顿-软阈值迭代鲁棒主成分分析算法

Newton-soft threshold iteration algorithm for robust principal component analysis

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	郑志强, 胡鑫, 翁智, 王雨禾, 程曦. 基于改进DenseNet的牛眼图像特征提取方法[J]. 计算机应用, 2021, 41(9): 2780-2784.
[2]	王心, 朱浩华, 刘光灿. 卷积鲁棒主成分分析[J]. 计算机应用, 2021, 41(5): 1314-1318.
[3]	佘玉龙, 张晓龙, 程若勤, 邓春华. 基于边缘关注模型的语义分割方法[J]. 计算机应用, 2021, 41(2): 343-349.
[4]	朱新成, 何坤金, 倪娜, 郝博. 基于改进迭代最近点算法的接骨板贴合性快捷计算方法[J]. 计算机应用, 2021, 41(10): 3033-3039.
[5]	尹春勇, 何苗. 基于改进胶囊网络的文本分类[J]. 计算机应用, 2020, 40(9): 2525-2530.
[6]	陈利霞, 班颖, 王学文. 基于张量核范数与3D全变分的背景减除[J]. 计算机应用, 2020, 40(9): 2737-2742.
[7]	周云, 陈淑荣. 基于双流非局部残差网络的行为识别方法[J]. 计算机应用, 2020, 40(8): 2236-2240.
[8]	张家岗, 李达平, 杨晓东, 邹茂扬, 吴锡, 胡金蓉. 基于深度卷积特征光流的形变医学图像配准算法[J]. 计算机应用, 2020, 40(6): 1799-1805.
[9]	徐代, 岳璋, 杨文霞, 任潇. 基于改进的三向流Faster R-CNN的篡改图像识别[J]. 计算机应用, 2020, 40(5): 1315-1321.
[10]	张俊升, 徐晶晶, 余伟. 面部美化图像质量无参考评价方法[J]. 计算机应用, 2020, 40(4): 1184-1190.
[11]	郭志强, 胡永武, 刘鹏, 杨杰. 基于特征融合的室外天气图像分类[J]. 计算机应用, 2020, 40(4): 1023-1029.
[12]	沈亮, 王鑫, 陈曙晖. 面向移动应用识别的结构化特征提取方法[J]. 计算机应用, 2020, 40(4): 1109-1114.
[13]	刘尚旺, 刘承伟, 张爱丽. 基于深度可分卷积神经网络的实时人脸表情和性别分类[J]. 计算机应用, 2020, 40(4): 990-995.
[14]	朱喆, 许少华. 降噪自编码器深度卷积过程神经网络及在时变信号分类中的应用[J]. 计算机应用, 2020, 40(3): 698-703.
[15]	陈梅婕, 谢振平, 陈晓琪, 许鹏. 专利新词发现的双向聚合度特征提取新方法[J]. 计算机应用, 2020, 40(3): 631-637.