• 论文 • 上一篇    下一篇

低秩稀疏矩阵恢复的快速非单调交替极小化方法

孙青青, 王川龙   

  1. 工程科学计算山西省高等学校重点实验室(太原师范学院), 晋中 030619
  • 收稿日期:2020-07-14 出版日期:2021-11-14 发布日期:2021-11-12
  • 通讯作者: 王川龙,clwang1964@163.com
  • 基金资助:
    国家自然科学基金(11371275)和山西省自然科学基金(201601D011004)资助.

孙青青, 王川龙. 低秩稀疏矩阵恢复的快速非单调交替极小化方法[J]. 计算数学, 2021, 43(4): 516-528.

Sun Qingqing, Wang Chuanlong. FAST ALTERNATING MINIMIZATION METHOD WITH NON-MONOTONE SEARCH FOR LOW-RANK AND SPARSE MATRIX RECOVERY[J]. Mathematica Numerica Sinica, 2021, 43(4): 516-528.

FAST ALTERNATING MINIMIZATION METHOD WITH NON-MONOTONE SEARCH FOR LOW-RANK AND SPARSE MATRIX RECOVERY

Sun Qingqing, Wang Chuanlong   

  1. Key Laboratory of Engineering and Computational Science (Taiyuan Normal University), Shanxi Province Department of Education, Jinzhong 030619, China
  • Received:2020-07-14 Online:2021-11-14 Published:2021-11-12
针对低秩稀疏矩阵恢复问题的一个非凸优化模型,本文提出了一种快速非单调交替极小化方法.主要思想是对低秩矩阵部分采用交替极小化方法,对稀疏矩阵部分采用非单调线搜索技术来分别进行迭代更新.非单调线搜索技术是将单步下降放宽为多步下降,从而提高了计算效率.文中还给出了新算法的收敛性分析.最后,通过数值实验的比较表明,矩阵恢复的非单调交替极小化方法比原单调类方法更有效.
In this paper, we propose a fast alternating minimization method with non-monotone line search technique for a non-convex optimization model of low-rank and sparse matrix recovery problem. The main idea is to use the alternating minimization method for the low-rank matrix part, and use the non-monotone line search technique for the sparse matrix part to iteratively update, respectively. The non-monotone line search technique relaxes the single-step descent into a multi-step descent, which greatly improves the computational efficiency. The paper also gives the convergence analysis of the new algorithm. Finally, the comparison of numerical experiments show that the alternate minimization method of the non-monotone technique of matrix recovery is more effective than the original monotone method.

MR(2010)主题分类: 

()
[1] Wright J, Ganesh A, Rao S, Ma Y. Robust Principal Component Analysis:Exact Recovery of Corrupted Low-Rank Matrices via Convex Optimization[C]. Advances in Neural Information Processing Systems 22:Conference on Neural Information Processing Systems A Meeting Held December. Curran Associates Inc. 2009.
[2] Amit Y, Fink M, Srebro N, Ullman S. Unconvering shared structures in malticalass classification[J]. In:Proceeding of the Twenty-Fourth International Conference on Machine Learning, ACM, 2007, 17-24.
[3] Argyriou A, Evgeniou T, Pontil M. Multi-task feature learning[J]. Adv. Neural Information Processing Systems, 2007, 19:41-48.
[4] Meng F, Yang X M, Zhou C H. The augmented Lagrange multipliers method for matrix completion from corrupted samplings with application to mixed Gaussian-impulse noise removal[J]. Plos One, 2014, 9(9):108-125.
[5] Zhou T, Tao D. GoDec:Randomized Lowrank and Sparse Matrix Decomposition in Noisy Case[C]. International Conference on Machine Learning. DBLP, 2011.
[6] Li X D. Compressed Sensing and Matrix Completion with Constant Proportion of Corruptions[J]. constructive approximation, 2013, 37(1):73-99.
[7] Water A E, Sankaranarayanan A C, Baraniuk R G. SpaRCS:Recovering low-rank and sparse matrices from compressive measurements[J]. International Conference on Neural Information Processing Systems. 2011.
[8] Wright J, Ganesh A, Min K. Compressive principal component pursuit[J]. Information and Inference A Journal of the Ima, 2013, 2:1276-1280.
[9] Wright J, Ganesh A, Rao S, Peng Y, Ma Y. Robust principal component analysis:exact recovery of corrupted low-rank matrices by convex optimization[J]. In:NIPS, 2009, 2080-2088.
[10] Zhou Z, Li X, Wright J, et al. Stable Principal Component Pursuit[J]. Information Theory Proceedings (ISIT), 2010 IEEE International Symposium on. IEEE, 2010.
[11] Xu H, Caramanis C, Sanghavi S. Robust PCA via outlier pursuit[J]. IEEE Transactions on Information Theory, 2012, 58:3047-3064.
[12] Lin Z, Ganesh A, Wright J, Wu L, Chen M, Ma Y. Fast convex optimization algorithms for exact recovery of a corrupted low rank matrix[J]. Journal of the Marine Biological Association of the Uk, 2009, 56:707-722.
[13] Lin Z, Chen M, Wu L, Ma Y. The augmented Lagrange multiplier method for exact recovery of corrupted low-rank matrices[M]. UIUC Technical Report UIUL-ENG-09-2214, 2010.
[14] Toh K C, Yun S. An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems[J]. Pacific Journal of Optimization, 2010, 6(3):615-640.
[15] Cai J F, Cand`es E J, Shen Z. A Singular Value Thresholding Algorithm for Matrix Completion[J]. Siam Journal on Optimization, 2008, 20(4):1956-1982.
[16] Li C, Wang C L, Wang J. Convergence analysis of the augmented Lagrange multiplier algorithm for a class of matrix compressive recovery[J]. Applied Mathematics Letters, 2016, 59:12-17.
[17] Jain P, Netrapalli P, Sanghavi S. Low-rank Matrix Completion using Alternating Minimization[J]. Statistics, 2012, 665-674.
[18] Tanner J, Wei K. Low rank matrix completion by alternating steepest descent methods[J]. Applied and Computational Harmonic Analysis, 2016, 40(2):417-429.
[19] Netrapalli P, Niranjan U N, Sanghavi S, et al. Non-convex Robust PCA[J]. Computer Science, 2014, 1107-1115.
[20] Wang Y X, Lee C M, Cheong L F, et al. Practical matrix completion and corruption recovery using proximal alternating robust subspace minimization[J]. International Journal of Computer Vision, 2015, 111(3):315-344.
[21] Yi X Y, Park D, Chen Y D, Caramanis C. Fast algorithms for robust PCA via gradient descent[J]. In Advances in Neural Information Processing Systems, 2016, 4152-4160.
[22] Zhang T, Yang Y. Robust PCA by manifold optimization[J]. Journal of Machine Learning Research, 2018, 19:1-39.
[23] Cai H Q, Cai J F, Wei K. Accelerated alternating projections for robust principal component analysis[J]. Journal of Machine Learning Research, 2019, 20:1-33.
[24] Koren Y, Bell R, Volinsky C. Matrix factorization techniques for recommender systems[J]. Computer, 2009, 42(8):30-37.
[25] Rendle S. Factorization machines with libfm[J]. ACM Transactions on Intelligent Systems and Technology, 2012, 3(3):1-22.
[26] Gu Q Q, Wang Z R, Liu H. Low-rank and sparse structure pursuit via alternating minimization[J]. In Arthur Gretton and Christian C. Robert, editors, AISTATS, volume 51 of JALR Workshop and Conference Proceedings, JMLR.org, 2016, 600-609.
[27] Li L, Huang W, Gu Y H, et al. Statistical Modeling of Complex Backgrounds for Foreground Object Detection[J]. IEEE Transactions on Image Processing, 2004, 13(11):1459-1472.
[1] 毕亚倩, 刘新为. 求解界约束优化的一种新的非单调谱投影梯度法[J]. 计算数学, 2013, 35(4): 419-430.
[2] 孙清滢, 段立宁, 陈颖梅, 王宣战, 宫恩龙, 徐胜来. 基于修正拟牛顿方程的两阶段步长非单调稀疏对角变尺度梯度投影算法[J]. 计算数学, 2013, 35(2): 113-124.
[3] 范斌, 马昌凤, 谢亚君. 求解非线性互补问题的一类光滑Broyden-like方法[J]. 计算数学, 2013, 35(2): 181-194.
[4] 万中, 冯冬冬. 一类非单调保守BFGS算法研究[J]. 计算数学, 2011, 33(4): 387-396.
[5] 庞善民, 陈兰平. 一类带非单调线搜索的信赖域算法[J]. 计算数学, 2011, 33(1): 48-56.
[6] 孙清滢, 崔彬, 王长钰. 新非单调线搜索规则的Lampariello修正对角稀疏拟牛顿算法[J]. 计算数学, 2008, 30(3): 255-268.
阅读次数
全文


摘要