# American Institute of Mathematical Sciences

December  2019, 8(4): 695-708. doi: 10.3934/eect.2019034

## A penalty decomposition method for nuclear norm minimization with l1 norm fidelity term

 1 School of Mathematics and Statistics, Henan University of Science and Technology, Luoyang 471023, China 2 Henan Joint International Research Laboratory of Cyberspace Security Applications, Luoyang 471023, China

* Corresponding author: jinzhengfen@whu.edu.cn

Received  April 2018 Revised  February 2019 Published  December 2019 Early access  June 2019

Fund Project: This work of Y. Shang is supported by the National Natural Science Foundation of China(No.11471102). This work of Z.-F Jin is supported by the National Natural Science Foundation of China(No.61370220) and the Plan for Scientific Innovation Talent of Henan Province(No.174200510011). This work of Duo Wang is supported by the National Natural Science Foundation of China(No.11701150).

It is well known that the nuclear norm minimization problems are widely used in numerous fields such as machine learning, system recognition, and image processing, etc. It has captured considerable attention and taken good progress. Many researchers have made great contributions to the nuclear norm minimization problem with $l_{2}$ norm fidelity term, which is just able to deal with those problems with Gaussian noise. In this paper, we propose an efficient penalty decomposition(PD) method to solve the nuclear norm minimization problem with $l_{1}$ norm fidelity term. One subproblem admits a closed-form solution due to its special structure, and another can also get a closed-form solution by linearizing its quadratic term. The convergence results of the proposed method are given as well. Finally, the effectiveness and efficiency of the proposed method are verified by some numerical experiments.

Citation: Duo Wang, Zheng-Fen Jin, Youlin Shang. A penalty decomposition method for nuclear norm minimization with l1 norm fidelity term. Evolution Equations and Control Theory, 2019, 8 (4) : 695-708. doi: 10.3934/eect.2019034
##### References:
 [1] E. Abreu, M. Lightstone, S. K. Mitra and K. Arakawa, A new efficient approach for the removal of impulse noise from highly corrupted images, IEEE Transactions on Image Processing, 5 (1996), 1012-1025.  doi: 10.1109/83.503916. [2] S. Alliney, A property of the minimum vectors of a regularizing functional defined by means of the absolute norm, IEEE Transactions on Signal Processing, 45 (1997), 913-917.  doi: 10.1109/78.564179. [3] H. Attouch, J. Bolte and B. F. Svaiter, Convergence of descent methods for semi-algebraic and tame problems: Proximal algorithms, forward–backward splitting, and regularized gauss–seidel methods, Mathematical Programming, 137 (2013), 91-129.  doi: 10.1007/s10107-011-0484-9. [4] A. Beck and L. Tetruashvili, On the convergence of block coordinate descent type methods, SIAM Journal on Optimization, 23 (2013), 2037-2060.  doi: 10.1137/120887679. [5] D. P. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods, Athena Scientific, Belmont, MA, 2014. [6] P. Bloomfield and W. Steiger, Least Absolute Deviations, Theory, Applications, and Algorithms, Progress in Probability and Statistics, 6. Birkhäuser Boston, Inc., Boston, MA, 1983. [7] J. Bolte, S. Sabach and M. Teboulle, Proximal alternating linearized minimization for nonconvex and nonsmooth problems, Mathematical Programming, 146 (2014), 459-494.  doi: 10.1007/s10107-013-0701-9. [8] J. F. Cai, E. J. Cand$\grave{e}$s and Z. Shen, A singular value thresholding algorithm for matrix completion, Siam Journal on Optimization, 20 (2008), 1956-1982.  doi: 10.1137/080738970. [9] J. F. Cai, R. H. Chan and M. Nikolova, Two-phase approach for deblurring images corrupted by impulse plus gaussian noise, Inverse Problems and Imaging, 2 (2012), 187-204.  doi: 10.3934/ipi.2008.2.187. [10] C. Chen, B. He and X. Yuan, Matrix completion via an alternating direction method, Ima Journal of Numerical Analysis, 32 (2012), 227-245.  doi: 10.1093/imanum/drq039. [11] Z. Dong and W. Zhu, An improvement of the penalty decomposition method for sparse approximation, Signal Processing, 113 (2015), 52-60.  doi: 10.1016/j.sigpro.2015.01.012. [12] M. Fazel, H. Hindi and S. P. Boyd, Rank minimization and applications in system theory, in American Control Conference, 2004. Proceedings of the IEEE, 4 (2004). doi: 10.23919/ACC.2004.1384521. [13] M. Fazel, H. Hindi and S. P. Boyd, A rank minimization heuristic with application to minimum order system approximation, in American Control Conference, 2001. Proceedings of the IEEE, 6 (2001). doi: 10.1109/ACC.2001.945730. [14] S. Gu, L. Zhang, W. Zuo and X. Feng, Weighted nuclear norm minimization with application to image denoising, in Computer Vision and Pattern Recognition, 2014, 2862–2869. doi: 10.1109/CVPR.2014.366. [15] H. Ji, C. Liu, Z. Shen and Y. Xu, Robust video denoising using low rank matrix completion, in Computer Vision and Pattern Recognition, 2010, 1791–1798. doi: 10.1109/CVPR.2010.5539849. [16] Z. F. Jin, Z. Wan, X. Zhao and Y. Xiao, A penalty decomposition method for rank minimization problem with affine constraints, Applied Mathematical Modelling, 39 (2015), 4859-4870.  doi: 10.1016/j.apm.2015.03.054. [17] Z. F. Jin, Q. Wang and Z. Wan, Recovering low-rank matrices from corrupted observations via the linear conjugate gradient algorithm, Journal of Computational and Applied Mathematics, 256 (2014), 114-120.  doi: 10.1016/j.cam.2013.07.009. [18] Z. Lu and Y. Zhang, Penalty decomposition methods for rank minimization, Optimization Methods and Software, 30 (2015), 531-558.  doi: 10.1080/10556788.2014.936438. [19] S. Ma, D. Goldfarb and L. Chen, Fixed point and Bregman iterative methods for matrix rank minimization, Mathematical Programming, 128 (2011), 321-353.  doi: 10.1007/s10107-009-0306-5. [20] Y. Marnissi, Y. Zheng, E. Chouzenoux and J. C. Pesquet, A Variational Bayesian Approach for Restoring Data Corrupted with Non-Gaussian Noise, Research report, Laboratoire Informatique Gaspard Monge, 2016. [21] C. A. Micchelli, L. Shen, Y. Xu and X. Zeng, Proximity algorithms for the l1/tv image denoising model, Advances in Computational Mathematics, 38 (2013), 401-426.  doi: 10.1007/s10444-011-9243-y. [22] K. Mohan and M. Fazel, Reweighted nuclear norm minimization with application to system identification, in American Control Conference, 2010, 2953–2959. doi: 10.1109/ACC.2010.5531594. [23] M. Nikolova, A variational approach to remove outliers and impulse noise, Journal of Mathematical Imaging and Vision, 20 (2004), 99-120.  doi: 10.1023/B:JMIV.0000011920.58935.9c. [24] J. Nocedal and S. J. Wright, Numerical Optimization, Springer, 1999. doi: 10.1007/b98874. [25] J. F. Sturm, Using SeDuMi 1.02, a matlab toolbox for optimization over symmetric cones, Optimization Methods and Software, 11 (1999), 625-653.  doi: 10.1080/10556789908805766. [26] K. C. Toh and S. W. Yun, An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems, Pacific Journal of Optimization, 6 (2010), 615-640. [27] P. Tseng, Convergence of a block coordinate descent method for nondifferentiable minimization, Journal of Optimization Theory and Applications, 109 (2001), 475-494.  doi: 10.1023/A:1017501703105. [28] R. H. Tütüncü, K. C. Toh and M. J. Todd, Solving semidefinite-quadratic-linear programs using SDPT3, Mathematical Programming, 95 (2003), 189-217.  doi: 10.1007/s10107-002-0347-5. [29] Y. H. Xiao and Z. F. Jin, An alternating direction method for linear-constrained matrix nuclear norm minimization, Numerical Linear Algebra with Applications, 19 (2012), 541-554.  doi: 10.1002/nla.783. [30] J. Yang, L. Luo, J. Qian, Y. Tai, F. Zhang and Y. Xu, Nuclear norm based matrix regression with applications to face recognition with occlusion and illumination changes, IEEE Transactions on Pattern Analysis and Machine Intelligence, 39 (2016), 156-171. [31] J. Yang and X. Yuan, Linearized augmented lagrangian and alternating direction methods for nuclear norm minimization, Mathematics of Computation, 82 (2013), 301-329.  doi: 10.1090/S0025-5718-2012-02598-1.

show all references

##### References:
 [1] E. Abreu, M. Lightstone, S. K. Mitra and K. Arakawa, A new efficient approach for the removal of impulse noise from highly corrupted images, IEEE Transactions on Image Processing, 5 (1996), 1012-1025.  doi: 10.1109/83.503916. [2] S. Alliney, A property of the minimum vectors of a regularizing functional defined by means of the absolute norm, IEEE Transactions on Signal Processing, 45 (1997), 913-917.  doi: 10.1109/78.564179. [3] H. Attouch, J. Bolte and B. F. Svaiter, Convergence of descent methods for semi-algebraic and tame problems: Proximal algorithms, forward–backward splitting, and regularized gauss–seidel methods, Mathematical Programming, 137 (2013), 91-129.  doi: 10.1007/s10107-011-0484-9. [4] A. Beck and L. Tetruashvili, On the convergence of block coordinate descent type methods, SIAM Journal on Optimization, 23 (2013), 2037-2060.  doi: 10.1137/120887679. [5] D. P. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods, Athena Scientific, Belmont, MA, 2014. [6] P. Bloomfield and W. Steiger, Least Absolute Deviations, Theory, Applications, and Algorithms, Progress in Probability and Statistics, 6. Birkhäuser Boston, Inc., Boston, MA, 1983. [7] J. Bolte, S. Sabach and M. Teboulle, Proximal alternating linearized minimization for nonconvex and nonsmooth problems, Mathematical Programming, 146 (2014), 459-494.  doi: 10.1007/s10107-013-0701-9. [8] J. F. Cai, E. J. Cand$\grave{e}$s and Z. Shen, A singular value thresholding algorithm for matrix completion, Siam Journal on Optimization, 20 (2008), 1956-1982.  doi: 10.1137/080738970. [9] J. F. Cai, R. H. Chan and M. Nikolova, Two-phase approach for deblurring images corrupted by impulse plus gaussian noise, Inverse Problems and Imaging, 2 (2012), 187-204.  doi: 10.3934/ipi.2008.2.187. [10] C. Chen, B. He and X. Yuan, Matrix completion via an alternating direction method, Ima Journal of Numerical Analysis, 32 (2012), 227-245.  doi: 10.1093/imanum/drq039. [11] Z. Dong and W. Zhu, An improvement of the penalty decomposition method for sparse approximation, Signal Processing, 113 (2015), 52-60.  doi: 10.1016/j.sigpro.2015.01.012. [12] M. Fazel, H. Hindi and S. P. Boyd, Rank minimization and applications in system theory, in American Control Conference, 2004. Proceedings of the IEEE, 4 (2004). doi: 10.23919/ACC.2004.1384521. [13] M. Fazel, H. Hindi and S. P. Boyd, A rank minimization heuristic with application to minimum order system approximation, in American Control Conference, 2001. Proceedings of the IEEE, 6 (2001). doi: 10.1109/ACC.2001.945730. [14] S. Gu, L. Zhang, W. Zuo and X. Feng, Weighted nuclear norm minimization with application to image denoising, in Computer Vision and Pattern Recognition, 2014, 2862–2869. doi: 10.1109/CVPR.2014.366. [15] H. Ji, C. Liu, Z. Shen and Y. Xu, Robust video denoising using low rank matrix completion, in Computer Vision and Pattern Recognition, 2010, 1791–1798. doi: 10.1109/CVPR.2010.5539849. [16] Z. F. Jin, Z. Wan, X. Zhao and Y. Xiao, A penalty decomposition method for rank minimization problem with affine constraints, Applied Mathematical Modelling, 39 (2015), 4859-4870.  doi: 10.1016/j.apm.2015.03.054. [17] Z. F. Jin, Q. Wang and Z. Wan, Recovering low-rank matrices from corrupted observations via the linear conjugate gradient algorithm, Journal of Computational and Applied Mathematics, 256 (2014), 114-120.  doi: 10.1016/j.cam.2013.07.009. [18] Z. Lu and Y. Zhang, Penalty decomposition methods for rank minimization, Optimization Methods and Software, 30 (2015), 531-558.  doi: 10.1080/10556788.2014.936438. [19] S. Ma, D. Goldfarb and L. Chen, Fixed point and Bregman iterative methods for matrix rank minimization, Mathematical Programming, 128 (2011), 321-353.  doi: 10.1007/s10107-009-0306-5. [20] Y. Marnissi, Y. Zheng, E. Chouzenoux and J. C. Pesquet, A Variational Bayesian Approach for Restoring Data Corrupted with Non-Gaussian Noise, Research report, Laboratoire Informatique Gaspard Monge, 2016. [21] C. A. Micchelli, L. Shen, Y. Xu and X. Zeng, Proximity algorithms for the l1/tv image denoising model, Advances in Computational Mathematics, 38 (2013), 401-426.  doi: 10.1007/s10444-011-9243-y. [22] K. Mohan and M. Fazel, Reweighted nuclear norm minimization with application to system identification, in American Control Conference, 2010, 2953–2959. doi: 10.1109/ACC.2010.5531594. [23] M. Nikolova, A variational approach to remove outliers and impulse noise, Journal of Mathematical Imaging and Vision, 20 (2004), 99-120.  doi: 10.1023/B:JMIV.0000011920.58935.9c. [24] J. Nocedal and S. J. Wright, Numerical Optimization, Springer, 1999. doi: 10.1007/b98874. [25] J. F. Sturm, Using SeDuMi 1.02, a matlab toolbox for optimization over symmetric cones, Optimization Methods and Software, 11 (1999), 625-653.  doi: 10.1080/10556789908805766. [26] K. C. Toh and S. W. Yun, An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems, Pacific Journal of Optimization, 6 (2010), 615-640. [27] P. Tseng, Convergence of a block coordinate descent method for nondifferentiable minimization, Journal of Optimization Theory and Applications, 109 (2001), 475-494.  doi: 10.1023/A:1017501703105. [28] R. H. Tütüncü, K. C. Toh and M. J. Todd, Solving semidefinite-quadratic-linear programs using SDPT3, Mathematical Programming, 95 (2003), 189-217.  doi: 10.1007/s10107-002-0347-5. [29] Y. H. Xiao and Z. F. Jin, An alternating direction method for linear-constrained matrix nuclear norm minimization, Numerical Linear Algebra with Applications, 19 (2012), 541-554.  doi: 10.1002/nla.783. [30] J. Yang, L. Luo, J. Qian, Y. Tai, F. Zhang and Y. Xu, Nuclear norm based matrix regression with applications to face recognition with occlusion and illumination changes, IEEE Transactions on Pattern Analysis and Machine Intelligence, 39 (2016), 156-171. [31] J. Yang and X. Yuan, Linearized augmented lagrangian and alternating direction methods for nuclear norm minimization, Mathematics of Computation, 82 (2013), 301-329.  doi: 10.1090/S0025-5718-2012-02598-1.
Numerical comparisons of model (22) and (23) with three noisy cases(m = n = 500, r = 10, sr = 0.5)
Numerical comparisons of model (22) and (23) with noiseless(m = n = 500). First row: $r = 10$, $sr$ is $0.3,0.5,0.7$ respectively. Second row: $sr = 0.5$, $r$ is $5,15,30$ respectively
(a): Original gray image($512\times 512$); (b): Corresponding low rank images with $r = 30$; (c): Randomly masked image from rank $30$ with $sr = 70\%$ and $q = 0.01$; (e):Randomly masked image from rank $30$ with $sr = 70\%$ and $\sigma = 0.001$, $q = 0.01$; (d), (f): Recovered images by $PD-l_{1}$, whose "RelErr" are $4.760e-3$, $4.827e-3$ respectively
Numerical results of $PD-l_{1}$ for problem (7) with impulsive noise: m = n = 500, r = 10, sr = 0.5, 0.7, 0.9, q = 0.01
Numerical results of $PD-l_{1}$ for (7), m = n, sr = 0.5, q = 0.01
 $PD-l_{1}$ $(m, r)$ p/dr Iter Time RelErr $(100, 5)$ 5.13 392 2.84 9.905e-004 $(200, 5)$ 10.13 187 4.03 9.881e-004 $(300, 5)$ 15.13 130 6.51 9.916e-004 $(400, 5)$ 20.13 99 9.26 9.947e-004 $(500, 5)$ 25.13 91 14.44 9.709e-004 $(600, 5)$ 30.13 78 19.31 9.853e-004 $(700, 5)$ 35.13 85 36.56 9.984e-004 $(800, 5)$ 40.13 88 54.63 9.889e-004 $(900, 5)$ 45.13 60 51.40 9.793e-004 $(1000, 5)$ 50.13 62 72.48 9.737e-004
 $PD-l_{1}$ $(m, r)$ p/dr Iter Time RelErr $(100, 5)$ 5.13 392 2.84 9.905e-004 $(200, 5)$ 10.13 187 4.03 9.881e-004 $(300, 5)$ 15.13 130 6.51 9.916e-004 $(400, 5)$ 20.13 99 9.26 9.947e-004 $(500, 5)$ 25.13 91 14.44 9.709e-004 $(600, 5)$ 30.13 78 19.31 9.853e-004 $(700, 5)$ 35.13 85 36.56 9.984e-004 $(800, 5)$ 40.13 88 54.63 9.889e-004 $(900, 5)$ 45.13 60 51.40 9.793e-004 $(1000, 5)$ 50.13 62 72.48 9.737e-004
Numerical results of $PD-l_{1}$ for (7), m = n, sr = 0.5
 $PD-l_{1}$ $(m, r)$ p/dr q $\sigma$ Time RelErr $(500, 10)$ 12.63 0.01 0.00 21.43 9.905e-004 $(500, 10)$ 12.63 0.01 0.001 21.65 9.822e-004 $(500, 10)$ 12.63 0.01 0.0001 21.77 9.781e-004 $(500, 10)$ 12.63 0.001 0.0001 20.61 8.054e-004 $(500, 10)$ 12.63 0.005 0.0001 20.53 8.659e-004 $(500, 10)$ 12.63 0.00 0.0001 2.15 7.722e-005
 $PD-l_{1}$ $(m, r)$ p/dr q $\sigma$ Time RelErr $(500, 10)$ 12.63 0.01 0.00 21.43 9.905e-004 $(500, 10)$ 12.63 0.01 0.001 21.65 9.822e-004 $(500, 10)$ 12.63 0.01 0.0001 21.77 9.781e-004 $(500, 10)$ 12.63 0.001 0.0001 20.61 8.054e-004 $(500, 10)$ 12.63 0.005 0.0001 20.53 8.659e-004 $(500, 10)$ 12.63 0.00 0.0001 2.15 7.722e-005
 [1] Huiyuan Guo, Quan Yu, Xinzhen Zhang, Lulu Cheng. Low rank matrix minimization with a truncated difference of nuclear norm and Frobenius norm regularization. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022045 [2] Ahmad Mousavi, Zheming Gao, Lanshan Han, Alvin Lim. Quadratic surface support vector machine with L1 norm regularization. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1835-1861. doi: 10.3934/jimo.2021046 [3] Yuan Shen, Xin Liu. An alternating minimization method for matrix completion problems. Discrete and Continuous Dynamical Systems - S, 2020, 13 (6) : 1757-1772. doi: 10.3934/dcdss.2020103 [4] Liqun Qi, Shenglong Hu, Yanwei Xu. Spectral norm and nuclear norm of a third order tensor. Journal of Industrial and Management Optimization, 2022, 18 (2) : 1101-1113. doi: 10.3934/jimo.2021010 [5] Braxton Osting, Jérôme Darbon, Stanley Osher. Statistical ranking using the $l^{1}$-norm on graphs. Inverse Problems and Imaging, 2013, 7 (3) : 907-926. doi: 10.3934/ipi.2013.7.907 [6] Pia Heins, Michael Moeller, Martin Burger. Locally sparse reconstruction using the $l^{1,\infty}$-norm. Inverse Problems and Imaging, 2015, 9 (4) : 1093-1137. doi: 10.3934/ipi.2015.9.1093 [7] P. R. Zingano. Asymptotic behavior of the $L^1$ norm of solutions to nonlinear parabolic equations. Communications on Pure and Applied Analysis, 2004, 3 (1) : 151-159. doi: 10.3934/cpaa.2004.3.151 [8] Yingying Li, Stanley Osher. Coordinate descent optimization for l1 minimization with application to compressed sensing; a greedy algorithm. Inverse Problems and Imaging, 2009, 3 (3) : 487-503. doi: 10.3934/ipi.2009.3.487 [9] Yifu Feng, Min Zhang. A $p$-spherical section property for matrix Schatten-$p$ quasi-norm minimization. Journal of Industrial and Management Optimization, 2020, 16 (1) : 397-407. doi: 10.3934/jimo.2018159 [10] Vladimir Gaitsgory, Tanya Tarnopolskaya. Threshold value of the penalty parameter in the minimization of $L_1$-penalized conditional value-at-risk. Journal of Industrial and Management Optimization, 2013, 9 (1) : 191-204. doi: 10.3934/jimo.2013.9.191 [11] Lidan Li, Hongwei Zhang, Liwei Zhang. Inverse quadratic programming problem with $l_1$ norm measure. Journal of Industrial and Management Optimization, 2020, 16 (5) : 2425-2437. doi: 10.3934/jimo.2019061 [12] Lei Wu, Zhe Sun. A new spectral method for $l_1$-regularized minimization. Inverse Problems and Imaging, 2015, 9 (1) : 257-272. doi: 10.3934/ipi.2015.9.257 [13] Zhen-Zhen Tao, Bing Sun. Galerkin spectral method for elliptic optimal control problem with $L^2$-norm control constraint. Discrete and Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021220 [14] Karina Samvelyan, Frol Zapolsky. Rigidity of the ${{L}^{p}}$-norm of the Poisson bracket on surfaces. Electronic Research Announcements, 2017, 24: 28-37. doi: 10.3934/era.2017.24.004 [15] Jiangang Qi, Bing Xie. Extremum estimates of the $L^1$-norm of weights for eigenvalue problems of vibrating string equations based on critical equations. Discrete and Continuous Dynamical Systems - B, 2021, 26 (7) : 3505-3516. doi: 10.3934/dcdsb.2020243 [16] Feishe Chen, Lixin Shen, Yuesheng Xu, Xueying Zeng. The Moreau envelope approach for the L1/TV image denoising model. Inverse Problems and Imaging, 2014, 8 (1) : 53-77. doi: 10.3934/ipi.2014.8.53 [17] Boshi Tian, Xiaoqi Yang, Kaiwen Meng. An interior-point $l_{\frac{1}{2}}$-penalty method for inequality constrained nonlinear optimization. Journal of Industrial and Management Optimization, 2016, 12 (3) : 949-973. doi: 10.3934/jimo.2016.12.949 [18] Yunhai Xiao, Soon-Yi Wu, Bing-Sheng He. A proximal alternating direction method for $\ell_{2,1}$-norm least squares problem in multi-task feature learning. Journal of Industrial and Management Optimization, 2012, 8 (4) : 1057-1069. doi: 10.3934/jimo.2012.8.1057 [19] Zhengshan Dong, Jianli Chen, Wenxing Zhu. Homotopy method for matrix rank minimization based on the matrix hard thresholding method. Numerical Algebra, Control and Optimization, 2019, 9 (2) : 211-224. doi: 10.3934/naco.2019015 [20] Sijia Zhong, Daoyuan Fang. $L^2$-concentration phenomenon for Zakharov system below energy norm II. Communications on Pure and Applied Analysis, 2009, 8 (3) : 1117-1132. doi: 10.3934/cpaa.2009.8.1117

2020 Impact Factor: 1.081