
-
Previous Article
Well-posedness and asymptotic behavior of the dissipative Ostrovsky equation
- EECT Home
- This Issue
-
Next Article
Simultaneous controllability of two vibrating strings with variable coefficients
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 |
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.
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. |




$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 |
$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
Tools
Metrics
Other articles
by authors
[Back to Top]