Low-rank and mix-sparse matrix decomposition has wide applications in computer vision, compressed sensing, and machine learning. In this paper, we study a nonconvex low-rank and mix sparse optimization problem, where the low-rank part is induced by the $ \ell_p (0 < p < 1) $ quasi-norm and the mix-sparse part is induced by a penalty composed of a combination of $ \ell_0 $ norm and $ \ell_{2, 0} $ norm. To solve this nonconvex optimization problem, we propose an alternating proximal gradient algorithm with partial singular value decomposition (APGP). The significant advantage of the APGP is that the partial-SVD strategy reduces the computational cost of low-rank updates, while the mix-sparse update admits a closed-form solution with low storage requirements. Furthermore, we establish the global convergence of the whole iterative sequence generated by the proposed APGP algorithm. Numerical experiments on synthetic data and background subtraction demonstrate that APGP performs competitively with representative algorithms.
Citation: Xian Zhang, Xin Wang, Lihua Wang. An alternating proximal gradient algorithm with partial SVD for low-rank and mix-sparse matrix decomposition[J]. Journal of Industrial and Management Optimization, 2026, 22(12): 6374-6398. doi: 10.3934/jimo.2026214
Low-rank and mix-sparse matrix decomposition has wide applications in computer vision, compressed sensing, and machine learning. In this paper, we study a nonconvex low-rank and mix sparse optimization problem, where the low-rank part is induced by the $ \ell_p (0 < p < 1) $ quasi-norm and the mix-sparse part is induced by a penalty composed of a combination of $ \ell_0 $ norm and $ \ell_{2, 0} $ norm. To solve this nonconvex optimization problem, we propose an alternating proximal gradient algorithm with partial singular value decomposition (APGP). The significant advantage of the APGP is that the partial-SVD strategy reduces the computational cost of low-rank updates, while the mix-sparse update admits a closed-form solution with low storage requirements. Furthermore, we establish the global convergence of the whole iterative sequence generated by the proposed APGP algorithm. Numerical experiments on synthetic data and background subtraction demonstrate that APGP performs competitively with representative algorithms.
| [1] |
J. Bolte, S. Sabach, M. Teboulle, Proximal alternating linearized minimization for nonconvex and nonsmooth problems, Math. Program., 146 (2014), 459–494. https://doi.org/10.1007/s10107-013-0701-9 doi: 10.1007/s10107-013-0701-9
|
| [2] |
D. Peng, N. Xiu, J. Yu, Global optimality conditions and fixed point continuation algorithm for non-Lipschitz $\ell_{p}$ regularized matrix minimization, Sci. China Math., 61 (2018), 1139–1152. https://doi.org/10.1007/s11425-016-9107-y doi: 10.1007/s11425-016-9107-y
|
| [3] |
Y. Hu, J. Lu, X. Yang, K. Zhang, Iterative mix thresholding algorithm with continuation technique for mix sparse optimization and application, J. Glob. Optim., 91 (2025), 511–534. https://doi.org/10.1007/s10898-024-01441-w doi: 10.1007/s10898-024-01441-w
|
| [4] |
Y. Jiao, B. Jin, X. Lv, Group sparse recovery via the $\ell_0(\ell_2)$ penalty: Theory and algorithm, IEEE Trans. Signal Process., 65 (2017), 998–1012. https://doi.org/10.1109/TSP.2016.2630028 doi: 10.1109/TSP.2016.2630028
|
| [5] |
R. Fan, M. Jing, J. Shi, TVRPCA+: Low-rank and sparse decomposition based on spectral norm and structural sparsity-inducing norm. Signal Process., 217 (2024), 109319. https://doi.org/10.1016/j.sigpro.2023.109319 |
| [6] |
D. Bertsimas, R. Cory-Wright, N. Johnson, Sparse plus low rank matrix decomposition: a discrete optimization approach, J. Mach. Learn. Res., 24 (2023), 1–51. Available from: http://jmlr.org/papers/v24/21-1130.html. |
| [7] |
E. Cand${\rm\grave{e}}$s, Y. Plan, Matrix completion with noise, Proc. IEEE, 98 (2010), 925–936. https://doi.org/10.1109/JPROC.2009.2035722 |
| [8] |
S. Liao, S. Fu, Y. Li, H. Han, Image inpainting using non-convex low rank decomposition and multidirectional search, Appl. Math. Comput., 452 (2023), 128048. https://doi.org/10.1016/j.amc.2023.128048 doi: 10.1016/j.amc.2023.128048
|
| [9] |
H. Yang, J. Lu, H. Zhang, Field of experts regularized nonlocal low rank matrix approximation for image denoising, J. Comput. Appl. Math., 412 (2022), 114244. https://doi.org/10.1016/j.cam.2022.114244 doi: 10.1016/j.cam.2022.114244
|
| [10] |
L. Zhuang, J. Bioucas-Dias, Fast hyperspectral image denoising and inpainting based on low-rank and sparse representations, IEEE J. Sel. Top. Appl. Earth Obs. Remote. Sens., 11 (2018), 730–742. https://doi.org/10.1109/JSTARS.2018.2796570 doi: 10.1109/JSTARS.2018.2796570
|
| [11] |
S. Ji, K. Sze, Z. Zhou, A. So, Y. Ye, Beyond convex relaxation: A polynomial-time non-convex optimization approach to network localization, IEEE International Conference on Computer Communications (INFOCOM), 2013, 2499–2507. https://doi.org/10.1109/INFCOM.2013.6567056 |
| [12] |
Y. Li, X. Sun, Sensor network localization via riemannian conjugate gradient and rank reduction, IEEE Trans. Signal Process., 72 (2024), 1910–1927. https://doi.org/10.1109/TSP.2024.3378378 doi: 10.1109/TSP.2024.3378378
|
| [13] |
H. Cai, C. Kundu, J. Liu, W. Yin, Deeply learned robust matrix completion for large-scale low-rank data recovery, IEEE Trans. Pattern Anal. Mach. Intell., 48 (2026), 6541–6556. https://doi.org/10.1109/TPAMI.2026.3659041 doi: 10.1109/TPAMI.2026.3659041
|
| [14] |
Z. Lin, M. Chen, Y. Ma, The augmented Lagrange multiplier method for exact recovery of corrupted low-rank matrices, arXiv: 1009.5055v3. |
| [15] |
E. Candès, X. Li, Y. Ma, J. Wright, Robust principal component analysis? J. ACM., 58 (2011), 1–37. https://doi.org/10.1145/1970392.1970395 |
| [16] |
L. Yang, T. Pong, X. Chen, Alternating direction method of multipliers for a class of nonconvex and nonsmooth problems with applications to background/foreground extraction, SIAM J. Imaging Sci., 10 (2017), 74–110. https://doi.org/10.1137/15M1027528 doi: 10.1137/15M1027528
|
| [17] |
A. Ganesh, Z. Lin, J. Wright, L. Wu, M. Chen, Y. Ma, Fast algorithms for recovering a corrupted low-rank matrix, IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP), 2009, 213–216. https://doi.org/10.1109/CAMSAP.2009.5413299 |
| [18] |
X. Long, J. Nie, G. Li, Z. Peng, An accelerated preconditioned primal-dual gradient algorithm for nonconvex composite optimization problems with applications, J. Comput. Math., 44 (2026), 1867–1889. https://doi.org/10.4208/jcm.2512-m2024-0107 doi: 10.4208/jcm.2512-m2024-0107
|
| [19] |
X. Long, J. Nie, Z. Gou, X. Sun, G. Li, An accelerated preconditioned primal-dual gradient algorithm for structured nonconvex optimization problems, Commun. Nonlinear Sci. Numer. Simulat., 153 (2026), 109480. https://doi.org/10.1016/j.cnsns.2025.109480 doi: 10.1016/j.cnsns.2025.109480
|
| [20] |
Y. Chen, J. Fan, C. Ma, Y. Yan, Bridging convex and nonconvex optimization in robust PCA: Noise, outliers, and missing data, Ann. Statist., 49 (2021), 2948–2971. https://doi.org/10.1214/21-AOS2066 doi: 10.1214/21-AOS2066
|
| [21] |
P. Netrapalli, U. Niranjan, S. Sanghavi, Non-convex robust PCA, arXiv: 1410.7660v1. |
| [22] |
Z. Wang, X. Li, H. So, Z. Liu, Robust PCA via non-convex half-quadratic regularization, Signal Process., 204 (2023), 108816. https://doi.org/10.1016/j.sigpro.2022.108816 doi: 10.1016/j.sigpro.2022.108816
|
| [23] |
Y. Xie, S. Gu, Y. Liu, W. Zuo, Weighted Schatten $p$-norm minimization for image denoising and background subtraction, IEEE Trans. Image Process., 25 (2016), 4842–4857. https://doi.org/10.1109/TIP.2016.2599290 doi: 10.1109/TIP.2016.2599290
|
| [24] |
K. Quach, C. Duong, K. Luu, T. Bui, Non-convex online robust PCA: enhance sparsity via $\ell_p$-norm minimization, Comput. Vis. Image. Underst., 158 (2017), 126–140. https://doi.org/10.1016/j.cviu.2017.03.002 doi: 10.1016/j.cviu.2017.03.002
|
| [25] |
Z. Xu, Y. Lu, J. Wu, Adaptive weighted robust principal component analysis, IEEE Conference on Industrial Electronics and Applications (ICIEA), 2020, 19–24. https://doi.org/10.1109/ICIEA48937.2020.9248290 |
| [26] |
Z. Kang, C. Peng, Q. Cheng, Robust PCA via nonconvex rank approximation, IEEE International Conference on Data Mining (ICDM), 2015, 211–220. https://doi.org/10.1109/ICDM.2015.15 |
| [27] |
S. Fang, Z. Xu, S. Wu, S. Xie, Efficient robust principal component analysis via block Krylov iteration and cur decomposition, IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2023, 1348–1357. https://doi.org/10.1109/CVPR52729.2023.00136 |
| [28] |
F. Wen, R. Ying, P. Liu, R. Qiu, Robust PCA using generalized nonconvex regularization, IEEE Trans. Circuits Syst. Video. Technol., 30 (2019), 1497–1510. https://doi.org/10.1109/TCSVT.2019.2908833 doi: 10.1109/TCSVT.2019.2908833
|
| [29] |
Z. Xu, H. Xing, S. Fang, Double-weighted low-rank matrix recovery based on rank estimation, IEEE/CVF International Conference on Computer Vision (ICCVW), 2021, 172–180. https://doi.org/10.1109/ICCVW54120.2021.00024 |
| [30] |
M. Indibi, S. Aviyente, Higher-order grouped outlier robust PCA for spatio-temporal anomaly detection, IEEE Statistical Signal Processing Workshop (SSP), 2025, 176–180. https://doi.org/10.1109/SSP64130.2025.11073198 |
| [31] |
H. Likassa, D. Chen, K. Chen, Robust PCA with $L_{w, *}$ and $L_{2, 1}$ norms: a novel method for low-quality retinal image enhancement, J. Imaging, 10 (2024), 151. https://doi.org/10.3390/jimaging10070151 doi: 10.3390/jimaging10070151
|
| [32] |
H. Likassa, W. Fang, J. Leu, Robust image recovery via affine transformation and $L_{2, 1}$ norm, IEEE Access, 7 (2019), 125011–125021. https://doi.org/10.1109/ACCESS.2019.2932470 doi: 10.1109/ACCESS.2019.2932470
|
| [33] |
H. Yang, Y. Zhao, J. Liu, Sparse regularization tensor robust PCA based on t-product and its application in cancer genomic data, IEEE International Conference on Bioinformatics and Biomedicine (BIBM), 2020, 2131–2138. https://doi.org/10.1109/BIBM49941.2020.9313596 |
| [34] |
S. Ebadi, E. Izquierdo, Foreground segmentation with tree-structured sparse RPCA, IEEE Trans. Pattern Anal. Mach. Intell., 40 (2017), 2273–2280. https://doi.org/10.1109/TPAMI.2017.2745573 doi: 10.1109/TPAMI.2017.2745573
|
| [35] |
L. Zhao, X. Hou, H. Yang, GRPCA21 for recovering a corrupted low-rank matrix, Int. J. Mach. Learn. Cybern., 11 (2020), 1293–1305. https://doi.org/10.1007/s13042-019-01039-9 doi: 10.1007/s13042-019-01039-9
|
| [36] |
Y. Zhang, N. Zhang, D. Sun, K. Toh, An efficient Hessian based algorithm for solving large-scale sparse group Lasso problems, Math. Program., 179 (2020), 223–263. https://doi.org/10.1007/s10107-018-1329-6 doi: 10.1007/s10107-018-1329-6
|
| [37] |
T. Thang, Bregman proximal point algorithms for quasi-equilibrium problems beyond prox-convexity, J. Optim. Theory. Appl., 210 (2026), 19. https://doi.org/10.1007/s10957-026-03039-6 doi: 10.1007/s10957-026-03039-6
|
| [38] |
R. Rockafellar, R. Wets, Variational Analysis, Berlin: Springer, 1998. https://doi.org/10.1007/978-3-642-02431-3 |
| [39] |
Y. Chen, N. Xiu, D. Peng, Global solutions of non-Lipschitz $S_2$-$S_p$ minimization over the positive semidefinite cone, Optim. Lett., 8 (2014), 2053–2064. https://doi.org/10.1007/s11590-013-0701-y doi: 10.1007/s11590-013-0701-y
|
| [40] |
Z. Xu, X. Chang, F. Xu, H. Zhang, $L_{1/2}$ regularization: a thresholding representation theory and a fast solver, IEEE Trans. Neural Netw. Learning Sys., 23 (2012), 1013–1027. https://doi.org/10.1109/TNNLS.2012.2197412 doi: 10.1109/TNNLS.2012.2197412
|
| [41] |
C. Zeng, Proximal linearization methods for Schatten $p$-quasi-norm minimization, Numer. Math., 153 (2023), 213–248. https://doi.org/10.1007/s00211-022-01335-7 doi: 10.1007/s00211-022-01335-7
|
| [42] |
H. Attouch, J. Bolte, On the convergence of the proximal algorithm for nonsmooth functions involving analytic features, Math. Program. Ser. B, 116 (2009), 5–16. https://doi.org/10.1007/s10107-007-0133-5 doi: 10.1007/s10107-007-0133-5
|
| [43] |
S. Ma, D. Goldfarb, L. Chen, Fixed point and Bregman iterative methods for matrix rank minimization, Math. Program, 128 (2011), 321–353. https://doi.org/10.1007/s10107-009-0306-5 doi: 10.1007/s10107-009-0306-5
|
| [44] |
S. Gu, Q. Xie, D. Meng, W. Zuo, Weighted nuclear norm minimization and its applications to low level vision, Int. J. Comput. Vis., 121 (2017), 183–208. https://doi.org/10.1007/s11263-016-0930-5 doi: 10.1007/s11263-016-0930-5
|
| [45] |
N. Goyette, P. Jodoin, F. Porikli, J. Konrad, P. Ishwar, Changedetection.net: A new change detection benchmark dataset, In: IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), 2012, 1–8. https://doi.org/10.1109/CVPRW.2012.6238919 |
| [46] |
L. Li, W. Huang, I. Gu, Q. Tian, Statistical modeling of complex backgrounds for foreground object detection, IEEE Trans. Image Process, 13 (2004), 1459–1472. https://doi.org/10.1109/TIP.2004.836169 doi: 10.1109/TIP.2004.836169
|
| [47] |
A. Vacavant, T. Chateau, A. Wilhelm, L. Lequièvre, A benchmark dataset for outdoor foreground/background extraction, Computer Vision - ACCV 2012 Workshops, 2013, 291–300. https://doi.org/10.1007/978-3-642-37410-4_25 |
| [48] |
B. Alawode, S. Javed, Unsupervised background subtraction using generator-discriminator learning, IEEE T. Circ. Syst. Vid., 36 (2026), 986–1002. https://doi.org/10.1109/tcsvt.2025.3598078 doi: 10.1109/tcsvt.2025.3598078
|
Numerical performance of APGP under different choices of $ p $
Numerical performance of APGP and APGP_full under different values of $ (p_r, p_{re}) $
Visual results of APGP on the CDnet and I2R short-video dataset
Visual results of APGP on the BMC long-video dataset. (a) Video_001. (b) Video_002. (c) Video_003. (d) Video_004. (e) Video_005. (f) Video_006. (g) Video_007. (h) Video_008. (i) Video_009