Figure 1.
Comparison of random data with $ p = 0.5 $
-
Previous Article
B2C online ride-hailing pricing and service optimization under competitions
- JIMO Home
- This Issue
-
Next Article
Online channel design in the presence of price self-matching: Self-operating or e-marketplace?
doi: 10.3934/jimo.2022045
Online First
Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.
Readers can access Online First articles via the “Online First” tab for the selected journal.
Low rank matrix minimization with a truncated difference of nuclear norm and Frobenius norm regularization
School of Mathematics, Tianjin University, Tianjin 300350, China |
In this paper, we present a novel regularization with a truncated difference of nuclear norm and Frobenius norm of form $ L_{t,*-\alpha F} $ with an integer $ t $ and parameter $ \alpha $ for rank minimization problem. The forward-backward splitting (FBS) algorithm is proposed to solve such a regularization problem, whose subproblems are shown to have closed-form solutions. We show that any accumulation point of the sequence generated by the FBS algorithm is a first-order stationary point. In the end, the numerical results demonstrate that the proposed FBS algorithm outperforms the existing methods.
Mathematics Subject Classification:
Primary: 15A83, 15A29, 65F55.
Citation:
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, doi: 10.3934/jimo.2022045
![]()
References:
| [1] |
A. Argyriou, T. Evgeniou and M. Pontil,
Convex multi-task feature learning, Mach. Learn., 73 (2008), 243-272.
doi: 10.1007/s10994-007-5040-8. |
| [2] |
J. F. Cai, E. J. Candes and Z. Shen,
A singular value thresholding algorithm for matrix completion, SIAM J. Optim., 20 (2010), 1956-1928.
doi: 10.1137/080738970. |
| [3] |
E. J. Cands and B. Recht,
Exact matrix completion via convex optimization, Found. Comput. Math., 9 (2009), 717-772.
doi: 10.1007/s10208-009-9045-5. |
| [4] |
R. Chartrand,
Exact reconstruction of sparse signals via nonconvex minimization, IEEE Signal Process. Lett., 14 (2007), 707-710.
doi: 10.1109/LSP.2007.898300. |
| [5] |
F. H. Clarke, Optimization and Nonsmooth Analysis, 2$^{nd}$ edition, Society for Industrial and Applied Mathematics, 1990.
doi: 10.1137/1.9781611971309. |
| [6] |
M. Fazel, H. Hindi and S. P. Boyd,
A rank minimization heuristic with application to minimum order system approximation, Proceedings of the 2001 American Control Conference, 6 (2001), 4734-4739.
doi: 10.1109/ACC.2001.945730. |
| [7] |
M. Fornasier, H. Rauhut and R. Ward,
Low-rank matrix recovery via iteratively reweighted least squares minimization, SIAM J. Optim., 21 (2011), 1614-1640.
doi: 10.1137/100811404. |
| [8] |
M. Lai, Y. Xu and W. Yin,
Improved iteratively reweighted least squares for unconstrained smoothed $l_{q}$ minimization, SIAM J. Numer. Anal, 51 (2013), 927-957.
doi: 10.1137/110840364. |
| [9] |
A. S. Lewis and H. S. Sendov,
Nonsmooth analysis of singular values. Part Ⅱ: Applications, Set-Valued Analysis, 13 (2005), 243-264.
doi: 10.1007/s11228-004-7198-6. |
| [10] |
G. Liu, Z. Lin, S. Yan, J. Sun, Y. Yu and Y. Ma,
Robust recovery of subspace structures by low-rank representation, IEEE Trans. Pattern Anal. Mach. Intell., 35 (2013), 171-184.
doi: 10.1109/TPAMI.2012.88. |
| [11] |
Y. Lou and M. Yan,
Fast $L_1-L_2$ minimization via a proximal operator, J. Sci. Comput., 74 (2018), 767-785.
doi: 10.1007/s10915-017-0463-2. |
| [12] |
Z. Lu, Y. Zhang and X. Li,
Penalty decomposition methods for rank minimization, Optim. Methods Softw., 30 (2015), 531-558.
doi: 10.1080/10556788.2014.936438. |
| [13] |
S. Ma, D. Goldfarb and L. Chen,
Fixed point and Bregman iterative methods for matrix rank minimization, Math. Program., 128 (2011), 321-353.
doi: 10.1007/s10107-009-0306-5. |
| [14] |
Z. Ming, L. Zhang, Y. Xu and M. Bakshi,
An algorithm for matrix recovery of high-loss-rate network traffic data, Appl. Math. Model., 96 (2021), 645-656.
doi: 10.1016/j.apm.2021.03.036. |
| [15] |
D. Phan and T. Nguyen, An accelerated IRNN-Iteratively reweighted nuclear norm algorithm for nonconvex nonsmooth low rank minimization problems, J. Comput. Appl. Math., 396 (2021), Paper No. 113602, 14 pp.
doi: 10.1016/j.cam.2021.113602. |
| [16] |
B. Recht, M. Fazel and P. A. Parrilo,
Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev., 52 (2010), 471-501.
doi: 10.1137/070697835. |
| [17] |
Rockafellar. R. T, Convex Analysis, Princeton University Press, 1997. |
| [18] |
K. Toh and S. Yun,
An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems, Pac. J. Optim., 6 (2010), 615-640.
|
| [19] |
Z. Wen, W. Yin and Y. Zhang,
Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm, Math. Program. Comput., 4 (2012), 333-361.
doi: 10.1007/s12532-012-0044-1. |
| [20] |
P. Yin, Y. Lou, Q. He and J. Xin,
Minimization of $l_{1-2}$ for compressed sensing, SIAM J. Sci. Comput., 37 (2015), 536-563.
doi: 10.1137/140952363. |
show all references
References:
| [1] |
A. Argyriou, T. Evgeniou and M. Pontil,
Convex multi-task feature learning, Mach. Learn., 73 (2008), 243-272.
doi: 10.1007/s10994-007-5040-8. |
| [2] |
J. F. Cai, E. J. Candes and Z. Shen,
A singular value thresholding algorithm for matrix completion, SIAM J. Optim., 20 (2010), 1956-1928.
doi: 10.1137/080738970. |
| [3] |
E. J. Cands and B. Recht,
Exact matrix completion via convex optimization, Found. Comput. Math., 9 (2009), 717-772.
doi: 10.1007/s10208-009-9045-5. |
| [4] |
R. Chartrand,
Exact reconstruction of sparse signals via nonconvex minimization, IEEE Signal Process. Lett., 14 (2007), 707-710.
doi: 10.1109/LSP.2007.898300. |
| [5] |
F. H. Clarke, Optimization and Nonsmooth Analysis, 2$^{nd}$ edition, Society for Industrial and Applied Mathematics, 1990.
doi: 10.1137/1.9781611971309. |
| [6] |
M. Fazel, H. Hindi and S. P. Boyd,
A rank minimization heuristic with application to minimum order system approximation, Proceedings of the 2001 American Control Conference, 6 (2001), 4734-4739.
doi: 10.1109/ACC.2001.945730. |
| [7] |
M. Fornasier, H. Rauhut and R. Ward,
Low-rank matrix recovery via iteratively reweighted least squares minimization, SIAM J. Optim., 21 (2011), 1614-1640.
doi: 10.1137/100811404. |
| [8] |
M. Lai, Y. Xu and W. Yin,
Improved iteratively reweighted least squares for unconstrained smoothed $l_{q}$ minimization, SIAM J. Numer. Anal, 51 (2013), 927-957.
doi: 10.1137/110840364. |
| [9] |
A. S. Lewis and H. S. Sendov,
Nonsmooth analysis of singular values. Part Ⅱ: Applications, Set-Valued Analysis, 13 (2005), 243-264.
doi: 10.1007/s11228-004-7198-6. |
| [10] |
G. Liu, Z. Lin, S. Yan, J. Sun, Y. Yu and Y. Ma,
Robust recovery of subspace structures by low-rank representation, IEEE Trans. Pattern Anal. Mach. Intell., 35 (2013), 171-184.
doi: 10.1109/TPAMI.2012.88. |
| [11] |
Y. Lou and M. Yan,
Fast $L_1-L_2$ minimization via a proximal operator, J. Sci. Comput., 74 (2018), 767-785.
doi: 10.1007/s10915-017-0463-2. |
| [12] |
Z. Lu, Y. Zhang and X. Li,
Penalty decomposition methods for rank minimization, Optim. Methods Softw., 30 (2015), 531-558.
doi: 10.1080/10556788.2014.936438. |
| [13] |
S. Ma, D. Goldfarb and L. Chen,
Fixed point and Bregman iterative methods for matrix rank minimization, Math. Program., 128 (2011), 321-353.
doi: 10.1007/s10107-009-0306-5. |
| [14] |
Z. Ming, L. Zhang, Y. Xu and M. Bakshi,
An algorithm for matrix recovery of high-loss-rate network traffic data, Appl. Math. Model., 96 (2021), 645-656.
doi: 10.1016/j.apm.2021.03.036. |
| [15] |
D. Phan and T. Nguyen, An accelerated IRNN-Iteratively reweighted nuclear norm algorithm for nonconvex nonsmooth low rank minimization problems, J. Comput. Appl. Math., 396 (2021), Paper No. 113602, 14 pp.
doi: 10.1016/j.cam.2021.113602. |
| [16] |
B. Recht, M. Fazel and P. A. Parrilo,
Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev., 52 (2010), 471-501.
doi: 10.1137/070697835. |
| [17] |
Rockafellar. R. T, Convex Analysis, Princeton University Press, 1997. |
| [18] |
K. Toh and S. Yun,
An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems, Pac. J. Optim., 6 (2010), 615-640.
|
| [19] |
Z. Wen, W. Yin and Y. Zhang,
Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm, Math. Program. Comput., 4 (2012), 333-361.
doi: 10.1007/s12532-012-0044-1. |
| [20] |
P. Yin, Y. Lou, Q. He and J. Xin,
Minimization of $l_{1-2}$ for compressed sensing, SIAM J. Sci. Comput., 37 (2015), 536-563.
doi: 10.1137/140952363. |
Figure 2.
As can be seen, the distribution of the singular values has a fast decaying distribution, and the information is dominated by the top 50 singular values
Figure 3.
An empirical study of Male images data
Figure 4.
Comparison of the four algorithms with different sampling ratio $ p $
Figure 5.
Testing images. "Clock": grayscale image of $ 256 \times 256 $ pixels. "Male": grayscale image of $ 512 \times 512 $ pixels. "Pixel ruler": grayscale image of $ 512 \times 512 $ pixels. "Walter Cronkite": grayscale image of $ 256 \times 256 $ pixels
Figure 6.
Recovered images of the masked images
Figure 7.
Comparison of four algorithms for the first $ 100 $ frames
Figure 8.
Comparison results of the MRI volume dataset
Table 1.
Numerical results of different images
| Method | Clock | Male | Pixel ruler | Walter Cronkite | |||||||
| rel.err | time | rel.err | time | rel.err | time | rel.err | time | ||||
| FBS-TM | 2.96e-02 | 5.47 | 4.63e-02 | 40.28 | 4.31e-02 | 9.66 | 1.77e-02 | 7.62 | |||
| LMaFit | 7.95e-02 | 0.05 | 1.74e-01 | 0.16 | 8.74e-02 | 1.43 | 1.27e-01 | 0.05 | |||
| SVT | 4.93e-02 | 19.05 | 1.02e-01 | 39.51 | 3.09e-01 | 45.64 | 7.23e-02 | 19.39 | |||
| FPCA | 7.60e-02 | 2.82 | 1.36e-01 | 14.69 | 1.30e-01 | 14.69 | 8.29e-02 | 2.94 | |||
| Method | Clock | Male | Pixel ruler | Walter Cronkite | |||||||
| rel.err | time | rel.err | time | rel.err | time | rel.err | time | ||||
| FBS-TM | 2.96e-02 | 5.47 | 4.63e-02 | 40.28 | 4.31e-02 | 9.66 | 1.77e-02 | 7.62 | |||
| LMaFit | 7.95e-02 | 0.05 | 1.74e-01 | 0.16 | 8.74e-02 | 1.43 | 1.27e-01 | 0.05 | |||
| SVT | 4.93e-02 | 19.05 | 1.02e-01 | 39.51 | 3.09e-01 | 45.64 | 7.23e-02 | 19.39 | |||
| FPCA | 7.60e-02 | 2.82 | 1.36e-01 | 14.69 | 1.30e-01 | 14.69 | 8.29e-02 | 2.94 | |||
Table 2.
Numerical results of masked images
| FBS-TM | LMaFit | SVT | FPCA | |||||||
| time | rel.err | time | rel.err | time | rel.err | time | ||||
| 2.95e-02 | 25.45 | 1.43e-01 | 0.49 | 1.70e-01 | 11.26 | 7.26e-01 | 16.51 | |||
| 1.50e-02 | 25.10 | 1.12e-01 | 0.26 | 3.04e-02 | 52.21 | 5.35e-01 | 15.43 | |||
| FBS-TM | LMaFit | SVT | FPCA | |||||||
| time | rel.err | time | rel.err | time | rel.err | time | ||||
| 2.95e-02 | 25.45 | 1.43e-01 | 0.49 | 1.70e-01 | 11.26 | 7.26e-01 | 16.51 | |||
| 1.50e-02 | 25.10 | 1.12e-01 | 0.26 | 3.04e-02 | 52.21 | 5.35e-01 | 15.43 | |||
| [1] |
Xiao Ding, Deren Han. A modification of the forward-backward splitting method for maximal monotone mappings. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 295-307. doi: 10.3934/naco.2013.3.295 |
| [2] |
Jiongmin Yong. Forward-backward evolution equations and applications. Mathematical Control and Related Fields, 2016, 6 (4) : 653-704. doi: 10.3934/mcrf.2016019 |
| [3] |
Fabio Paronetto. Elliptic approximation of forward-backward parabolic equations. Communications on Pure and Applied Analysis, 2020, 19 (2) : 1017-1036. doi: 10.3934/cpaa.2020047 |
| [4] |
G. Bellettini, Giorgio Fusco, Nicola Guglielmi. A concept of solution and numerical experiments for forward-backward diffusion equations. Discrete and Continuous Dynamical Systems, 2006, 16 (4) : 783-842. doi: 10.3934/dcds.2006.16.783 |
| [5] |
Xin Chen, Ana Bela Cruzeiro. Stochastic geodesics and forward-backward stochastic differential equations on Lie groups. Conference Publications, 2013, 2013 (special) : 115-121. doi: 10.3934/proc.2013.2013.115 |
| [6] |
Yufeng Shi, Tianxiao Wang, Jiongmin Yong. Optimal control problems of forward-backward stochastic Volterra integral equations. Mathematical Control and Related Fields, 2015, 5 (3) : 613-649. doi: 10.3934/mcrf.2015.5.613 |
| [7] |
Flavia Smarrazzo, Alberto Tesei. Entropy solutions of forward-backward parabolic equations with Devonshire free energy. Networks and Heterogeneous Media, 2012, 7 (4) : 941-966. doi: 10.3934/nhm.2012.7.941 |
| [8] |
Andrés Contreras, Juan Peypouquet. Forward-backward approximation of nonlinear semigroups in finite and infinite horizon. Communications on Pure and Applied Analysis, 2021, 20 (5) : 1893-1906. doi: 10.3934/cpaa.2021051 |
| [9] |
Kaitong Hu, Zhenjie Ren, Nizar Touzi. On path-dependent multidimensional forward-backward SDEs. Numerical Algebra, Control and Optimization, 2022 doi: 10.3934/naco.2022010 |
| [10] |
Jiongmin Yong. Forward-backward stochastic differential equations: Initiation, development and beyond. Numerical Algebra, Control and Optimization, 2022 doi: 10.3934/naco.2022011 |
| [11] |
Ke Wei, Jian-Feng Cai, Tony F. Chan, Shingyu Leung. Guarantees of riemannian optimization for low rank matrix completion. Inverse Problems and Imaging, 2020, 14 (2) : 233-265. doi: 10.3934/ipi.2020011 |
| [12] |
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 |
| [13] |
Fabio Paronetto. A Harnack type inequality and a maximum principle for an elliptic-parabolic and forward-backward parabolic De Giorgi class. Discrete and Continuous Dynamical Systems - S, 2017, 10 (4) : 853-866. doi: 10.3934/dcdss.2017043 |
| [14] |
Flavia Smarrazzo, Andrea Terracina. Sobolev approximation for two-phase solutions of forward-backward parabolic problems. Discrete and Continuous Dynamical Systems, 2013, 33 (4) : 1657-1697. doi: 10.3934/dcds.2013.33.1657 |
| [15] |
Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006 |
| [16] |
Yangyang Xu, Ruru Hao, Wotao Yin, Zhixun Su. Parallel matrix factorization for low-rank tensor completion. Inverse Problems and Imaging, 2015, 9 (2) : 601-624. doi: 10.3934/ipi.2015.9.601 |
| [17] |
Jie Xiong, Shuaiqi Zhang, Yi Zhuang. A partially observed non-zero sum differential game of forward-backward stochastic differential equations and its application in finance. Mathematical Control and Related Fields, 2019, 9 (2) : 257-276. doi: 10.3934/mcrf.2019013 |
| [18] |
Adel Chala, Dahbia Hafayed. On stochastic maximum principle for risk-sensitive of fully coupled forward-backward stochastic control of mean-field type with application. Evolution Equations and Control Theory, 2020, 9 (3) : 817-843. doi: 10.3934/eect.2020035 |
| [19] |
Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems and Imaging, 2021, 15 (1) : 159-183. doi: 10.3934/ipi.2020076 |
| [20] |
Yun Cai, Song Li. Convergence and stability of iteratively reweighted least squares for low-rank matrix recovery. Inverse Problems and Imaging, 2017, 11 (4) : 643-661. doi: 10.3934/ipi.2017030 |
2021 Impact Factor: 1.411
Tools
Metrics
Other articles
by authors
[Back to Top]