A customized inertial proximal alternating minimization for SVD-free robust principal component analysis. (English) Zbl 07914184
Summary: Robust principal component analysis (RPCA) is devoted to tackling grossly corrupted datasets with noise. However, the performance of RPCA is usually circumscribed by the lack of efficiency of singular value decomposition (SVD), which rules out its potential applications to many large-scale real-world problems. In this paper, we develop a nonconvex optimization algorithm customized to SVD-free RPCA models. The proposed algorithm, which is built upon proximal alternating linearized minimization Bolte et al. [Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Math Program. 2014;146(1-2):459-494], can reduce computational efforts by partially linearizing data fidelity and increase efficiency by leveraging inertial techniques. Under the Kurdyka-Łojasiewicz assumption on the objective function and some mild premises on stepsizes, the sequence produced by the proposed algorithm converges globally to a critical point of SVD-free RPCA models. Numerical simulations on synthetic and real datasets demonstrate the compelling performance of the proposed algorithm.
MSC:
| 65K10 | Numerical optimization and variational techniques |
| 90C26 | Nonconvex programming, global optimization |
| 68U10 | Computing methodologies for image processing |
Keywords:
robust principal component analysis; matrix factorization; nonconvex; proximal alternating minimization; mixed noise removalSoftware:
PROPACKReferences:
| [1] | Candès, EJ, Li, X, Ma, Y, et al. Robust principal component analysis?J ACM. 2011;58(3):1-37. doi: · Zbl 1327.62369 |
| [2] | Goli, A, Ala, A, Hajiaghaei-Keshteli, M.Efficient multi-objective meta-heuristic algorithms for energy-aware non-permutation flow-shop scheduling problem. Exp Syst Appl. 2023;213:Article ID 119077. doi: |
| [3] | Goli, A, Ala, A, Mirjalili, S.A robust possibilistic programming framework for designing an organ transplant supply chain under uncertainty. Ann Oper Res. 2022;1-38. doi: |
| [4] | Goli, A, Golmohammadi, A, Verdegay, J.Two-echelon electric vehicle routing problem with a developed moth-flame meta-heuristic algorithm. Oper Manag Res. 2022;15(3-4):891-912. doi: |
| [5] | Goli, A, Khademi Zare, H, Tavakkoli-Moghaddam, R, et al. Hybrid artificial intelligence and robust optimization for a multi-objective product portfolio problem case study: the dairy products industry. Comp Indus Enginee. 2019;137:Article ID 106090. doi: |
| [6] | Goli, A, Mohammadi, H.Developing a sustainable operational management system using hybrid shapley value and multimoora method: case study petrochemical supply chain. Environ Dev Sustain. 2022;24(9):10540-10569. doi: |
| [7] | Bouwmans, T, Aybat, NS, hadi Zahzah, E.Handbook of robust low-rank and sparse matrix decomposition: applications in image and video processing. Boca Raton, FL: Chapman Hall, CRC; 2016. · Zbl 1339.68002 |
| [8] | Vaswani, N, Bouwmans, T, Javed, S, et al. Robust subspace learning: robust PCA, robust subspace tracking, and robust subspace recovery. IEEE Signal Process Mag. 2018;35(4):32-55. doi: |
| [9] | Vaswani, N, Chi, Y, Bouwmans, T.Rethinking PCA for modern data sets: theory, algorithms, and applications. Proc IEEE. 2018;106(8):1274-1276. doi: |
| [10] | Chandrasekaran, V, Sanghavi, S, Parrilo, PA, et al. Rank-sparsity incoherence for matrix decomposition. SIAM J Optim. 2009;21(2):572-596. doi: · Zbl 1226.90067 |
| [11] | Wright, J, Ganesh, A, Rao, SR, et al. Robust principal component analysis: exact recovery of corrupted low-rank matrices via convex optimization. In: Advances in neural information processing systems. Vol. 58; 2009. p. 289-298. |
| [12] | Tao, M, Yuan, X.Recovering low-rank and sparse components of matrices from incomplete and noisy observations. SIAM J Optim. 2011;21(1):57-81. doi: · Zbl 1218.90115 |
| [13] | Bolte, J, Sabach, S, Teboulle, M.Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Math Program. 2014;146(1-2):459-494. doi: · Zbl 1297.90125 |
| [14] | Pock, T, Sabach, S.Inertial proximal alternating linearized minimization (iPALM) for nonconvex and nonsmooth problems. SIAM J Imaging Sci. 2016;9(4):1756-1787. doi: · Zbl 1358.90109 |
| [15] | Shen, Y, Xu, H, Liu, X.An alternating minimization method for robust principal component analysis. Optim Methods Softw. 2019;34(6):1251-1276. doi: · Zbl 1436.65071 |
| [16] | Zhao, Q, Meng, D, Xu, Z, et al. A block coordinate descent approach for sparse principal component analysis. Neurocomputing. 2015;153:180-190. doi: |
| [17] | Shen, Y, Wen, Z, Zhang, Y.Augmented lagrangian alternating direction method for matrix separation based on low-rank factorization. Optim Methods Softw. 2014;29(2):239-263. doi: · Zbl 1285.90068 |
| [18] | Han, D.A survey on some recent developments of alternating direction method of multipliers. J Oper Res Soc China. 2022;10(1):1-52. doi: · Zbl 1499.90158 |
| [19] | Lin, Z, Liu, R, Su, Z.Linearized alternating direction method with adaptive penalty for low-rank representation. Adv Neural Inf Process Syst. 2011;24:612-620. |
| [20] | Yuan, X, Yang, J.Sparse and low-rank matrix decomposition via alternating direction methods. Pac J Optim. 2013;9(1):167-180. · Zbl 1269.90061 |
| [21] | Park, YW, Klabjan, D.Three iteratively reweighted least squares algorithms for \(l_1 \) -norm principal component analysis. Knowl Inf Syst. 2018;54(3):541-565. doi: |
| [22] | Cai, H, Cai, J, Wei, K.Accelerated alternating projections for robust principal component analysis. J Mach Learn Res. 2019;20:1-33. · Zbl 1483.62098 |
| [23] | Onuki, M, Ono, S, Shirai, K, et al. Fast singular value shrinkage with Chebyshev polynomial approximation based on signal sparsity. IEEE Trans Signal Process. 2017;65(22):6083-6096. doi: · Zbl 1414.94451 |
| [24] | Lu, C, Tang, J, Yan, S, et al. Nonconvex nonsmooth low rank minimization via iteratively reweighted nuclear norm. IEEE Trans Image Process. 2016;25(2):829-839. doi: · Zbl 1408.94866 |
| [25] | Yao, Q, Kwok, JT, Wang, T, et al. Large-scale low-rank matrix learning with nonconvex regularizers. IEEE Trans Pattern Anal Mach Intell. 2019;41(11):2628-2643. doi: |
| [26] | Ito, K, Kunisch, K.\( L^p(\Omega )\) optimization with \(p\in [0,1) \). SIAM J Control Optim. 2014;52(2):1251-1275. doi: · Zbl 1306.49010 |
| [27] | Ito, K, Kunisch, K.A variational approach to sparsity optimization based on Lagrange multiplier theory. Inverse Probl. 2014;30(1):Article ID 015001. doi: · Zbl 1292.65070 |
| [28] | Anderson, E, Bai, Z, Bischof, CH, et al. LAPACK users’ guide. Philadelphia, PA: SIAM; 1999. · Zbl 0934.65030 |
| [29] | Larsen, RM. PROPACK-software for large and sparse SVD calculations; 2005. Available from: https://sun.stanford.edu/srmunk/PROPACK/ |
| [30] | Srebro, N, Rennie, JDM, Jaakkola, TS. Maximum-margin matrix factorization. In: Advances in neural information processing systems; 2004. p. 1329-1336. |
| [31] | Sprechmann, P, Bronstein, AM, Sapiro, G.Learning efficient sparse and low rank models. IEEE Trans Pattern Anal Mach Intell. 2015;37(9):1821-1833. doi: |
| [32] | Feng, J, Xu, H, Yan, S. Online robust PCA via stochastic optimization. In: Advances in neural information processing systems; 2013. p. 404-412. |
| [33] | Fan, J, Ding, L, Chen, Y, et al. Factor group-sparse regularization for efficient low-rank matrix recovery. In: Advances in neural information processing systems; 2019. p. 5104-5114. |
| [34] | Cai, H, Hamm, K, Huang, L, et al. Rapid robust principal component analysis: CUR accelerated inexact low rank estimation. IEEE Signal Process Lett. 2020;28:116-120. doi: |
| [35] | Dutta, A, Liang, J, Li, X. A fast and adaptive svd-free algorithm for general weighted low-rank recovery; 2021. arXiv preprint arXiv:2101.00749. |
| [36] | Ebadi, SE, Guerra-Ones, V, Izquierdo, E. Efficient background subtraction with low-rank and sparse matrix decomposition. In: IEEE International conference on image processing; 2015. p. 4863-4867. |
| [37] | Tong, T, Ma, C, Chi, Y.Accelerating ill-conditioned low-rank matrix estimation via scaled gradient descent. J Mach Learn Res. 2021;22(150):1-63. · Zbl 07415093 |
| [38] | Yi, X, Park, D, Chen, Y, et al. Fast algorithms for robust PCA via gradient descent. In: Advances in neural information processing systems. Vol. 29; 2016. |
| [39] | Fan, J, Li, R.Variable selection via nonconcave penalized likelihood and its oracle properties. J Amer Statist Assoc. 2001;96(456):1348-1360. doi: · Zbl 1073.62547 |
| [40] | Zhang, C.Nearly unbiased variable selection under minimax concave penalty. Ann Stat. 2010;38(2):894-942. doi: · Zbl 1183.62120 |
| [41] | Zhang, T.Analysis of multi-stage convex relaxation for sparse regularization. J Mach Learn Res. 2010;11:1081-1107. · Zbl 1242.68262 |
| [42] | Candès, EJ, Wakin, MB, Boyd, SP.Enhancing sparsity by reweighted l1 minimization. J Fourier Anal Appl. 2007;14(5):877-905. doi: · Zbl 1176.94014 |
| [43] | Friedman, J.Fast sparse regression and classification. Intern J Forecasting. 2012;28(3):722-738. doi: |
| [44] | Rennie, JDM, Srebro, N. Fast maximum margin matrix factorization for collaborative prediction. In: International conference machine learning. Vol. 119; 2005. p. 713-719. |
| [45] | Rockafellar, RT, Wets, RJB.Variational analysis. Berlin: Springer; 1998. · Zbl 0888.49001 |
| [46] | Cai, X, Guo, K, Jiang, F, et al. The developments of proximal point algorithms. J Oper Res Soc China. 2022;10(2):197-239. doi: · Zbl 1502.47081 |
| [47] | Güler, O.On the convergence of the proximal point algorithm for convex minimization. SIAM J Control Optim. 1991;29(2):403-419. doi: · Zbl 0737.90047 |
| [48] | Rockafellar, RT.Monotone operators and the proximal point algorithm. SIAM J Control Optim. 1976;14(5):877-898. doi: · Zbl 0358.90053 |
| [49] | Nesterov, Y.Introductory lectures on convex optimization: a basic course. Dordrecht, The Netherlands: Kluwer Academic Publishers; 2004. · Zbl 1086.90045 |
| [50] | Boyd, S, Parikh, N, Chu, E, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers. Found Trends Mach Learn. 2010;3(1):1-122. doi: · Zbl 1229.90122 |
| [51] | Wang, Z, Bovik, AC, Sheikh, HR, et al. Image quality assessment: from error visibility to structural similarity. IEEE Trans Image Process. 2004;13(4):600-612. doi: |
| [52] | Markovsky, I.Low-rank approximation: algorithms, implementation, applications. London, UK: Springer; 2018. |
| [53] | Schaeffer, H, Osher, S.A low patch-rank interpretation of texture. SIAM J Imaging Sci. 2013;6(1):226-262. doi: · Zbl 1335.68287 |
| [54] | Vacavant, A, Chateau, T, Wilhelm, A, et al. A benchmark dataset for outdoor foreground/background extraction. In: Computer vision-ACCV international workshops, Korea; 2012. p. 291-300. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
