Journal of Computer Applications ›› 2020, Vol. 40 ›› Issue (11): 3133-3138.DOI: 10.11772/j.issn.1001-9081.2020030375

• Artificial intelligence • Previous Articles     Next Articles

Newton-soft threshold iteration algorithm for robust principal component analysis

WANG Haipeng, JIANG Ailian, LI Pengxiang   

  1. 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).

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

王海鹏, 降爱莲, 李鹏翔   

  1. 太原理工大学 信息与计算机学院, 山西 晋中 030600
  • 通讯作者: 降爱莲(1969-),女,山西太原人,副教授,博士,CCF会员,主要研究方向:人工智能、大数据、特征选择、计算机视觉;ailianjiang@126.com
  • 作者简介:王海鹏(1996-),男,山东潍坊人,硕士研究生,主要研究方向:机器学习、特征提取;李鹏翔(1992-),男,山西吕梁人,硕士研究生,主要研究方向:机器学习、异常检测
  • 基金资助:
    山西省回国留学人员科研资助项目(2017-051)。

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 l1-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

摘要: 针对鲁棒主成分分析(RPCA)问题,为了降低RPCA算法的时间复杂度,提出了牛顿-软阈值迭代(NSTI)算法。首先,使用低秩矩阵的Frobenius范数与稀疏矩阵的l1-范数的和来构造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算法的时间效率。

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

CLC Number: