Figure 1.
The distributions of nondominated solutions, dominated solutions and Pareto front in the objective space of the two objectives problem.
-
Previous Article
A moving block sequence-based evolutionary algorithm for resource investment project scheduling problems
- BDIA Home
- This Issue
-
Next Article
Selective further learning of hybrid ensemble for class imbalanced increment learning
January
2017, 2(1): 23-37.
doi: 10.3934/bdia.2017006
An evolutionary multiobjective method for low-rank and sparse matrix decomposition
School of Electronics and Information, Northwestern Polytechnical University, 127 West Youyi Road, Xi'an Shaanxi, 710072, China |
This paper addresses the problem of finding the low-rank and sparse components of a given matrix. The problem involves two conflicting objective functions, reducing the rank and sparsity of each part simultaneously. Previous methods combine two objectives into a single objective penalty function to solve with traditional numerical optimization approaches. The main contribution of this paper is to put forward a multiobjective method to decompose the given matrix into low-rank component and sparse part. We optimize two objective functions with an evolutionary multiobjective algorithm MOEA/D. Another contribution of this paper, a modified low-rank and sparse matrix model is proposed, which simplifying the variable of objective functions and improving the efficiency of multiobjective optimization. The proposed method obtains a set of solutions with different trade-off between low-rank and sparse objectives, and decision makers can choose one or more satisfied decomposed results according to different requirements directly. Experiments conducted on artificial datasets and nature images, show that the proposed method always obtains satisfied results, and the convergence, stability and robustness of the proposed method is acceptable.
Keywords:
Matrix decomposition,
evolutionary algorithm,
multiobjective optimization,
low-rank,
sparse.
Mathematics Subject Classification:
90C29, 92D15.
Citation:
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
![]()
References:
| [1] |
A. Beck and M. Teboulle,
A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM Journal on Imaging Sciences, 2 (2009), 183-202.
doi: 10.1137/080716542. |
| [2] |
J.-F. Cai, E. J. Candès and Z. Shen,
A singular value thresholding algorithm for matrix completion, SIAM Journal on Optimization, 20 (2010), 1956-1982.
doi: 10.1137/080738970. |
| [3] |
Z. Cai and Y. Wang,
A multiobjective optimization-based evolutionary algorithm for constrained optimization, IEEE Transactions on Evolutionary Computation, 10 (2006), 658-675.
doi: 10.1109/TEVC.2006.872344. |
| [4] |
E. J. Candès, X. Li, Y. Ma and J. Wright, Robust principal component analysis?
Journal of the ACM (JACM), 58 (2011), Art. 11, 37 pp.
doi: 10.1145/1970392.1970395. |
| [5] |
E. J. Candès and B. Recht,
Exact matrix completion via convex optimization, Foundations
of Computational Mathematics, 9 (2009), 717-772.
doi: 10.1007/s10208-009-9045-5. |
| [6] |
V. Chandrasekaran, S. Sanghavi, P. A. Parrilo and A. S. Willsky,
Rank-sparsity incoherence for matrix decomposition, SIAM Journal on Optimization, 21 (2011), 572-596.
doi: 10.1137/090761793. |
| [7] |
C. A. C. Coello, D. A. Van~Veldhuizen and G. B. Lamont,
Evolutionary Algorithms for Solving Multi-Objective Problems, Genetic Algorithms and Evolutionary Computation, 5. Kluwer Academic/Plenum Publishers, New York, 2002.
doi: 10.1007/978-1-4757-5184-0. |
| [8] |
K. Deb,
Multi-objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, Ltd. , Chichester, 2001. |
| [9] |
K. Deb, A. Pratap, S. Agarwal and T. Meyarivan,
A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ, IEEE Transactions on Evolutionary Computation, 6 (2002), 182-197.
doi: 10.1109/4235.996017. |
| [10] |
M. Fazel, H. Hindi and S. P. Boyd,
A rank minimization heuristic with application to minimum order system approximation, in Proceedings of the American Control Conference, IEEE, 6 (2001), 4734-4739.
doi: 10.1109/ACC.2001.945730. |
| [11] |
M. Gong, L. Jiao, H. Du and L. Bo,
Multiobjective immune algorithm with nondominated neighbor-based selection, Evolutionary Computation, 16 (2008), 225-255.
doi: 10.1162/evco.2008.16.2.225. |
| [12] |
Z. Lin, A. Ganesh, J. Wright, L. Wu, M. Chen and Y. Ma, Fast convex optimization algorithms for exact recovery of a corrupted low-rank matrix, Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP), vol. 61,2009. Google Scholar |
| [13] |
Z. Lin, M. Chen and Y. Ma, The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices, arXiv preprint, arXiv: 1009.5055, 2010. Google Scholar |
| [14] |
K. Miettinen,
Nonlinear Multiobjective Optimization, Kluwer Academic Publishers, Boston, MA, 1999. |
| [15] |
C. Qian, Y. Yu and Z.-H. Zhou, Pareto ensemble pruning, in AAAI, (2015), 2935-2941. Google Scholar |
| [16] |
————, Subset selection by pareto optimization, in Advances in Neural Information Processing Systems, (2015), 1774-1782. Google Scholar |
| [17] |
B. Recht, M. Fazel and P. A. Parrilo,
Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Review, 52 (2010), 471-501.
doi: 10.1137/070697835. |
| [18] |
J. D. Schaffer, Multiple objective optimization with vector evaluated genetic algorithms, in Proceedings of the 1st international Conference on Genetic Algorithms. L. Erlbaum Associates Inc. , (1985), 93-100. Google Scholar |
| [19] |
J. L. Starck, M. Elad and D. L. Donoho,
Image decomposition via the combination of sparse representations and a variational approach, IEEE Transactions on Image Processing, 14 (2005), 1570-1582.
doi: 10.1109/TIP.2005.852206. |
| [20] |
J. Yan, J. Liu, Y. Li, Z. Niu and Y. Liu,
Visual saliency detection via rank-sparsity decomposition, in IEEE International Conference on Image Processing, IEEE, (2010), 1089-1092.
doi: 10.1109/ICIP.2010.5652280. |
| [21] |
X. Yuan and J. Yang,
Sparse and low-rank matrix decomposition via alternating direction methods, Pacific Journal of Optimization, 9 (2013), 167-180.
|
| [22] |
C. Zhang, J. Liu, Q. Tian, C. Xu, H. Lu and S. Ma,
Image classification by non-negative
sparse coding, low-rank and sparse decomposition, IEEE Conference on Computer Vision and Pattern Recognition (CVPR), (2011), 1673-1680.
doi: 10.1109/CVPR.2011.5995484. |
| [23] |
Q. Zhang and H. Li, MOEA/D: A multiobjective evolutionary algorithm based on decomposition, IEEE Transactions on Evolutionary Computation, 11 (2007), 712-731. Google Scholar |
| [24] |
M. Zibulevsky and B. A. Pearlmutter, Blind source separation by sparse decomposition in a signal dictionary, Neural Computation, 13 (2001), 863-882. Google Scholar |
| [25] |
E. Zitzler, M. Laumanns and L. Thiele, SPEA2: Improving the strength pareto evolutionary algorithm, in Eurogen, 3242 (2001), 95-100. Google Scholar |
show all references
References:
| [1] |
A. Beck and M. Teboulle,
A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM Journal on Imaging Sciences, 2 (2009), 183-202.
doi: 10.1137/080716542. |
| [2] |
J.-F. Cai, E. J. Candès and Z. Shen,
A singular value thresholding algorithm for matrix completion, SIAM Journal on Optimization, 20 (2010), 1956-1982.
doi: 10.1137/080738970. |
| [3] |
Z. Cai and Y. Wang,
A multiobjective optimization-based evolutionary algorithm for constrained optimization, IEEE Transactions on Evolutionary Computation, 10 (2006), 658-675.
doi: 10.1109/TEVC.2006.872344. |
| [4] |
E. J. Candès, X. Li, Y. Ma and J. Wright, Robust principal component analysis?
Journal of the ACM (JACM), 58 (2011), Art. 11, 37 pp.
doi: 10.1145/1970392.1970395. |
| [5] |
E. J. Candès and B. Recht,
Exact matrix completion via convex optimization, Foundations
of Computational Mathematics, 9 (2009), 717-772.
doi: 10.1007/s10208-009-9045-5. |
| [6] |
V. Chandrasekaran, S. Sanghavi, P. A. Parrilo and A. S. Willsky,
Rank-sparsity incoherence for matrix decomposition, SIAM Journal on Optimization, 21 (2011), 572-596.
doi: 10.1137/090761793. |
| [7] |
C. A. C. Coello, D. A. Van~Veldhuizen and G. B. Lamont,
Evolutionary Algorithms for Solving Multi-Objective Problems, Genetic Algorithms and Evolutionary Computation, 5. Kluwer Academic/Plenum Publishers, New York, 2002.
doi: 10.1007/978-1-4757-5184-0. |
| [8] |
K. Deb,
Multi-objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, Ltd. , Chichester, 2001. |
| [9] |
K. Deb, A. Pratap, S. Agarwal and T. Meyarivan,
A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ, IEEE Transactions on Evolutionary Computation, 6 (2002), 182-197.
doi: 10.1109/4235.996017. |
| [10] |
M. Fazel, H. Hindi and S. P. Boyd,
A rank minimization heuristic with application to minimum order system approximation, in Proceedings of the American Control Conference, IEEE, 6 (2001), 4734-4739.
doi: 10.1109/ACC.2001.945730. |
| [11] |
M. Gong, L. Jiao, H. Du and L. Bo,
Multiobjective immune algorithm with nondominated neighbor-based selection, Evolutionary Computation, 16 (2008), 225-255.
doi: 10.1162/evco.2008.16.2.225. |
| [12] |
Z. Lin, A. Ganesh, J. Wright, L. Wu, M. Chen and Y. Ma, Fast convex optimization algorithms for exact recovery of a corrupted low-rank matrix, Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP), vol. 61,2009. Google Scholar |
| [13] |
Z. Lin, M. Chen and Y. Ma, The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices, arXiv preprint, arXiv: 1009.5055, 2010. Google Scholar |
| [14] |
K. Miettinen,
Nonlinear Multiobjective Optimization, Kluwer Academic Publishers, Boston, MA, 1999. |
| [15] |
C. Qian, Y. Yu and Z.-H. Zhou, Pareto ensemble pruning, in AAAI, (2015), 2935-2941. Google Scholar |
| [16] |
————, Subset selection by pareto optimization, in Advances in Neural Information Processing Systems, (2015), 1774-1782. Google Scholar |
| [17] |
B. Recht, M. Fazel and P. A. Parrilo,
Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Review, 52 (2010), 471-501.
doi: 10.1137/070697835. |
| [18] |
J. D. Schaffer, Multiple objective optimization with vector evaluated genetic algorithms, in Proceedings of the 1st international Conference on Genetic Algorithms. L. Erlbaum Associates Inc. , (1985), 93-100. Google Scholar |
| [19] |
J. L. Starck, M. Elad and D. L. Donoho,
Image decomposition via the combination of sparse representations and a variational approach, IEEE Transactions on Image Processing, 14 (2005), 1570-1582.
doi: 10.1109/TIP.2005.852206. |
| [20] |
J. Yan, J. Liu, Y. Li, Z. Niu and Y. Liu,
Visual saliency detection via rank-sparsity decomposition, in IEEE International Conference on Image Processing, IEEE, (2010), 1089-1092.
doi: 10.1109/ICIP.2010.5652280. |
| [21] |
X. Yuan and J. Yang,
Sparse and low-rank matrix decomposition via alternating direction methods, Pacific Journal of Optimization, 9 (2013), 167-180.
|
| [22] |
C. Zhang, J. Liu, Q. Tian, C. Xu, H. Lu and S. Ma,
Image classification by non-negative
sparse coding, low-rank and sparse decomposition, IEEE Conference on Computer Vision and Pattern Recognition (CVPR), (2011), 1673-1680.
doi: 10.1109/CVPR.2011.5995484. |
| [23] |
Q. Zhang and H. Li, MOEA/D: A multiobjective evolutionary algorithm based on decomposition, IEEE Transactions on Evolutionary Computation, 11 (2007), 712-731. Google Scholar |
| [24] |
M. Zibulevsky and B. A. Pearlmutter, Blind source separation by sparse decomposition in a signal dictionary, Neural Computation, 13 (2001), 863-882. Google Scholar |
| [25] |
E. Zitzler, M. Laumanns and L. Thiele, SPEA2: Improving the strength pareto evolutionary algorithm, in Eurogen, 3242 (2001), 95-100. Google Scholar |
Figure 2.
Error of sparse component recovering by the ADM method for LRSMD with different choices of the parameter $\lambda$
Figure 3.
The Pareto front, two objective functions corresponding to the solutions and box-plot for $ErrLR$ and $ErrSP$ by running 30 times independent experiments. Three rows represent experiment on the data with size:$20\times 20$ , rank: 5, sparsity: 0.2, size: $50\times 50$ , rank: 5, sparsity: 0.2 and size: $100\times 100$ , rank: 5, sparsity: 0.5 respectively.
Figure 4.
Box-plot about $ErrLR$ and $ErrSP$ for data with different noise. (a): number of noise points is 20, $\sigma=1$ . (b): number of noise points is 20, $\sigma=5$ . (c): number of noise points is 20, $\sigma=15$ . (d): number of noise points is 50, $\sigma=5$ . (e): number of noise points is 50, $\sigma=15$ .
Figure 5.
The Pareto front and two objective functions corresponding to the solutions for noise data. Noise type: number of noise points is 50 and $\sigma =15$ .
Figure 6.
The Pareto front and decomposed results with image lena. (a) is Pareto front of MOLRSMD and (b) is three different decomposed results selected form Pareto front, and they locate at the top, middle and bottom of Pareto front, respectively.
Figure 7.
The Pareto front and decomposed results with image face. (a) is Pareto front of MOLRSMD and (b) is three different decomposed results selected form Pareto front, and they locate at the top, middle and bottom of Pareto front, respectively.
Figure 8.
Results of the proposed MOLRSMD compared with ADM and ALM. The test dataset size is $50\times 50$ , rank equals 5 and sparsity is 0.2.
Table 1.
The Parameters in the MOLRSMD used in the Experiments
| Parameter | Meaning | Value |
| The number of subproblems | 100 | |
| The number of neighbors | 20 | |
| | The maximum of generations | 300 |
| | The probability of crossover | 0.8 |
| | The differential multiplier | 0.5 |
| | The probability of mutation | 0.2 |
| | The probability of mutation selection | 0.85 |
| Parameter | Meaning | Value |
| The number of subproblems | 100 | |
| The number of neighbors | 20 | |
| | The maximum of generations | 300 |
| | The probability of crossover | 0.8 |
| | The differential multiplier | 0.5 |
| | The probability of mutation | 0.2 |
| | The probability of mutation selection | 0.85 |
Table 2.
Errors of the proposed MOLRSMD compared with ADM and ALM.
| Methods | | | |
| MOLRSMD | 0.0100 | 0.1986 | 0 |
| ADM | 0.0299 | 0.1331 | 1.9135e-17 |
| ALM | 0.0148 | 0.0661 | 2.2412e-10 |
| Methods | | | |
| MOLRSMD | 0.0100 | 0.1986 | 0 |
| ADM | 0.0299 | 0.1331 | 1.9135e-17 |
| ALM | 0.0148 | 0.0661 | 2.2412e-10 |
| [1] |
Mingchao Zhao, You-Wei Wen, Michael Ng, Hongwei Li. A nonlocal low rank model for poisson noise removal. Inverse Problems & Imaging, 2021, 15 (3) : 519-537. doi: 10.3934/ipi.2021003 |
| [2] |
Manfred Einsiedler, Elon Lindenstrauss. On measures invariant under diagonalizable actions: the Rank-One case and the general Low-Entropy method. Journal of Modern Dynamics, 2008, 2 (1) : 83-128. doi: 10.3934/jmd.2008.2.83 |
| [3] |
Jiahui Chen, Rundong Zhao, Yiying Tong, Guo-Wei Wei. Evolutionary de Rham-Hodge method. Discrete & Continuous Dynamical Systems - B, 2021, 26 (7) : 3785-3821. doi: 10.3934/dcdsb.2020257 |
| [4] |
Najeeb Abdulaleem. $ V $-$ E $-invexity in $ E $-differentiable multiobjective programming. Numerical Algebra, Control & Optimization, 2021 doi: 10.3934/naco.2021014 |
| [5] |
Simone Cacace, Maurizio Falcone. A dynamic domain decomposition for the eikonal-diffusion equation. Discrete & Continuous Dynamical Systems - S, 2016, 9 (1) : 109-123. doi: 10.3934/dcdss.2016.9.109 |
| [6] |
Thomas Alazard. A minicourse on the low Mach number limit. Discrete & Continuous Dynamical Systems - S, 2008, 1 (3) : 365-404. doi: 10.3934/dcdss.2008.1.365 |
| [7] |
Lara Abi Rizk, Jean-Baptiste Burie, Arnaud Ducrot. Asymptotic speed of spread for a nonlocal evolutionary-epidemic system. Discrete & Continuous Dynamical Systems, 2021 doi: 10.3934/dcds.2021064 |
| [8] |
Mario Pulvirenti, Sergio Simonella. On the cardinality of collisional clusters for hard spheres at low density. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3903-3914. doi: 10.3934/dcds.2021021 |
| [9] |
J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008 |
| [10] |
Meng Ding, Ting-Zhu Huang, Xi-Le Zhao, Michael K. Ng, Tian-Hui Ma. Tensor train rank minimization with nonlocal self-similarity for tensor completion. Inverse Problems & Imaging, 2021, 15 (3) : 475-498. doi: 10.3934/ipi.2021001 |
| [11] |
Melis Alpaslan Takan, Refail Kasimbeyli. Multiobjective mathematical models and solution approaches for heterogeneous fixed fleet vehicle routing problems. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2073-2095. doi: 10.3934/jimo.2020059 |
| [12] |
Charles Fulton, David Pearson, Steven Pruess. Characterization of the spectral density function for a one-sided tridiagonal Jacobi matrix operator. Conference Publications, 2013, 2013 (special) : 247-257. doi: 10.3934/proc.2013.2013.247 |
| [13] |
Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069 |
| [14] |
Lars Grüne, Luca Mechelli, Simon Pirkelmann, Stefan Volkwein. Performance estimates for economic model predictive control and their application in proper orthogonal decomposition-based implementations. Mathematical Control & Related Fields, 2021 doi: 10.3934/mcrf.2021013 |
| [15] |
Yuri Fedorov, Božidar Jovanović. Continuous and discrete Neumann systems on Stiefel varieties as matrix generalizations of the Jacobi–Mumford systems. Discrete & Continuous Dynamical Systems, 2021, 41 (6) : 2559-2599. doi: 10.3934/dcds.2020375 |
| [16] |
F.J. Herranz, J. de Lucas, C. Sardón. Jacobi--Lie systems: Fundamentals and low-dimensional classification. Conference Publications, 2015, 2015 (special) : 605-614. doi: 10.3934/proc.2015.0605 |
| [17] |
Emily McMillon, Allison Beemer, Christine A. Kelley. Extremal absorbing sets in low-density parity-check codes. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021003 |
| [18] |
Jan Rychtář, Dewey T. Taylor. Moran process and Wright-Fisher process favor low variability. Discrete & Continuous Dynamical Systems - B, 2021, 26 (7) : 3491-3504. doi: 10.3934/dcdsb.2020242 |
| [19] |
Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781 |
| [20] |
Ashkan Ayough, Farbod Farhadi, Mostafa Zandieh, Parisa Rastkhadiv. Genetic algorithm for obstacle location-allocation problems with customer priorities. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1753-1769. doi: 10.3934/jimo.2020044 |
Impact Factor:
Tools
Metrics
Other articles
by authors
[Back to Top]