An evolutionary multiobjective method for low-rank and sparse matrix decomposition

Tao Wu; Yu Lei; Jiao Shi; Maoguo Gong

doi:10.3934/bdia.2017006

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

Tao Wu ^, , Yu Lei , Jiao Shi and Maoguo Gong

School of Electronics and Information, Northwestern Polytechnical University, 127 West Youyi Road, Xi'an Shaanxi, 710072, China

* Corresponding author: Tao Wu

Published September 2017

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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[8]	K. Deb, Multi-objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, Ltd. , Chichester, 2001. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[21]	X. Yuan and J. Yang, Sparse and low-rank matrix decomposition via alternating direction methods, Pacific Journal of Optimization, 9 (2013), 167-180. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[8]	K. Deb, Multi-objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, Ltd. , Chichester, 2001. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[21]	X. Yuan and J. Yang, Sparse and low-rank matrix decomposition via alternating direction methods, Pacific Journal of Optimization, 9 (2013), 167-180. Google Scholar
[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. Google Scholar
[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 1. The distributions of nondominated solutions, dominated solutions and Pareto front in the objective space of the two objectives problem.

Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2. Error of sparse component recovering by the ADM method for LRSMD with different choices of the parameter $\lambda$

Figure Options

Download full-size image

Download as PowerPoint slide

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 Options

Download full-size image

Download as PowerPoint slide

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 Options

Download full-size image

Download as PowerPoint slide

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 Options

Download full-size image

Download as PowerPoint slide

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 Options

Download full-size image

Download as PowerPoint slide

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 Options

Download full-size image

Download as PowerPoint slide

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.

Figure Options

Download full-size image

Download as PowerPoint slide

Table 1. The Parameters in the MOLRSMD used in the Experiments

Parameter	Meaning	Value
$N$	The number of subproblems	100
$T$	The number of neighbors	20
$t_{max}$	The maximum of generations	300
$pc$	The probability of crossover	0.8
$pd$	The differential multiplier	0.5
$pm$	The probability of mutation	0.2
$ps$	The probability of mutation selection	0.85

Table Options

Download as excel

Parameter	Meaning	Value
$N$	The number of subproblems	100
$T$	The number of neighbors	20
$t_{max}$	The maximum of generations	300
$pc$	The probability of crossover	0.8
$pd$	The differential multiplier	0.5
$pm$	The probability of mutation	0.2
$ps$	The probability of mutation selection	0.85

Table 2. Errors of the proposed MOLRSMD compared with ADM and ALM.

Methods	$ErrLR$	$ErrSP$	$ErrT$
MOLRSMD	0.0100	0.1986	0
ADM	0.0299	0.1331	1.9135e-17
ALM	0.0148	0.0661	2.2412e-10

Table Options

Download as excel

Methods	$ErrLR$	$ErrSP$	$ErrT$
MOLRSMD	0.0100	0.1986	0
ADM	0.0299	0.1331	1.9135e-17
ALM	0.0148	0.0661	2.2412e-10

[1]	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 & Imaging, 2021, 15 (1) : 159-183. doi: 10.3934/ipi.2020076
[2]	Simon Arridge, Pascal Fernsel, Andreas Hauptmann. Joint reconstruction and low-rank decomposition for dynamic inverse problems. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021059
[3]	Yangyang Xu, Ruru Hao, Wotao Yin, Zhixun Su. Parallel matrix factorization for low-rank tensor completion. Inverse Problems & Imaging, 2015, 9 (2) : 601-624. doi: 10.3934/ipi.2015.9.601
[4]	Ke Wei, Jian-Feng Cai, Tony F. Chan, Shingyu Leung. Guarantees of riemannian optimization for low rank matrix completion. Inverse Problems & Imaging, 2020, 14 (2) : 233-265. doi: 10.3934/ipi.2020011
[5]	Xianchao Xiu, Lingchen Kong. Rank-one and sparse matrix decomposition for dynamic MRI. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 127-134. doi: 10.3934/naco.2015.5.127
[6]	Yun Cai, Song Li. Convergence and stability of iteratively reweighted least squares for low-rank matrix recovery. Inverse Problems & Imaging, 2017, 11 (4) : 643-661. doi: 10.3934/ipi.2017030
[7]	Wei Wan, Weihong Guo, Jun Liu, Haiyang Huang. Non-local blind hyperspectral image super-resolution via 4d sparse tensor factorization and low-rank. Inverse Problems & Imaging, 2020, 14 (2) : 339-361. doi: 10.3934/ipi.2020015
[8]	Zhouchen Lin. A review on low-rank models in data analysis. Big Data & Information Analytics, 2016, 1 (2&3) : 139-161. doi: 10.3934/bdia.2016001
[9]	Simon Foucart, Richard G. Lynch. Recovering low-rank matrices from binary measurements. Inverse Problems & Imaging, 2019, 13 (4) : 703-720. doi: 10.3934/ipi.2019032
[10]	Yong Wang, Wanquan Liu, Guanglu Zhou. An efficient algorithm for non-convex sparse optimization. Journal of Industrial & Management Optimization, 2019, 15 (4) : 2009-2021. doi: 10.3934/jimo.2018134
[11]	M. Delgado Pineda, E. A. Galperin, P. Jiménez Guerra. MAPLE code of the cubic algorithm for multiobjective optimization with box constraints. Numerical Algebra, Control & Optimization, 2013, 3 (3) : 407-424. doi: 10.3934/naco.2013.3.407
[12]	Yongge Tian. A survey on rank and inertia optimization problems of the matrix-valued function $A + BXB^{}$. Numerical Algebra, Control & Optimization*, 2015, 5 (3) : 289-326. doi: 10.3934/naco.2015.5.289
[13]	Changming Song, Yun Wang. Nonlocal latent low rank sparse representation for single image super resolution via self-similarity learning. Inverse Problems & Imaging, 2021, 15 (6) : 1347-1362. doi: 10.3934/ipi.2021017
[14]	Nguyen Van Thoai. Decomposition branch and bound algorithm for optimization problems over efficient sets. Journal of Industrial & Management Optimization, 2008, 4 (4) : 647-660. doi: 10.3934/jimo.2008.4.647
[15]	Haixia Liu, Jian-Feng Cai, Yang Wang. Subspace clustering by (k,k)-sparse matrix factorization. Inverse Problems & Imaging, 2017, 11 (3) : 539-551. doi: 10.3934/ipi.2017025
[16]	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
[17]	Yitong Guo, Bingo Wing-Kuen Ling. Principal component analysis with drop rank covariance matrix. Journal of Industrial & Management Optimization, 2021, 17 (5) : 2345-2366. doi: 10.3934/jimo.2020072
[18]	Zhengshan Dong, Jianli Chen, Wenxing Zhu. Homotopy method for matrix rank minimization based on the matrix hard thresholding method. Numerical Algebra, Control & Optimization, 2019, 9 (2) : 211-224. doi: 10.3934/naco.2019015
[19]	Chunrong Chen, T. C. Edwin Cheng, Shengji Li, Xiaoqi Yang. Nonlinear augmented Lagrangian for nonconvex multiobjective optimization. Journal of Industrial & Management Optimization, 2011, 7 (1) : 157-174. doi: 10.3934/jimo.2011.7.157
[20]	Yibing Lv, Zhongping Wan. Linear bilevel multiobjective optimization problem: Penalty approach. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1213-1223. doi: 10.3934/jimo.2018092

Impact Factor:

Tools

Metrics

Tools

Article outline

Figures and Tables

Impact Factor:

Tools

Figures and Tables

Impact Factor:

American Institute of Mathematical Sciences

An evolutionary multiobjective method for low-rank and sparse matrix decomposition

References:

References:

Tools

Metrics

Other articles
by authors

Tools

Tools

Tools

Metrics

Other articles
by authors

American Institute of Mathematical Sciences

An evolutionary multiobjective method for low-rank and sparse matrix decomposition

References:

References:

Tools

Metrics

Other articlesby authors

Tools

Tools

Tools

Metrics

Other articlesby authors

Other articles
by authors

Other articles
by authors