American Institute of Mathematical Sciences

• 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

* 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.

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:

show all references

References:
The distributions of nondominated solutions, dominated solutions and Pareto front in the objective space of the two objectives problem.
Error of sparse component recovering by the ADM method for LRSMD with different choices of the parameter $\lambda$
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.
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$.
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$.
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.
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.
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.
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
 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
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
 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] 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 [2] 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 [3] 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 [4] 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 [5] 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 [6] 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 [7] 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 [8] 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 [9] 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 [10] 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 [11] 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 [12] 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 [13] Giancarlo Bigi. Componentwise versus global approaches to nonsmooth multiobjective optimization. Journal of Industrial & Management Optimization, 2005, 1 (1) : 21-32. doi: 10.3934/jimo.2005.1.21 [14] 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 [15] Jinyuan Zhang, Aimin Zhou, Guixu Zhang, Hu Zhang. A clustering based mate selection for evolutionary optimization. Big Data & Information Analytics, 2017, 2 (1) : 77-85. doi: 10.3934/bdia.2017010 [16] K. T. Arasu, Manil T. Mohan. Optimization problems with orthogonal matrix constraints. Numerical Algebra, Control & Optimization, 2018, 8 (4) : 413-440. doi: 10.3934/naco.2018026 [17] Zhifeng Dai, Fenghua Wen. A generalized approach to sparse and stable portfolio optimization problem. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1651-1666. doi: 10.3934/jimo.2018025 [18] Giuseppe Geymonat, Françoise Krasucki. Hodge decomposition for symmetric matrix fields and the elasticity complex in Lipschitz domains. Communications on Pure & Applied Analysis, 2009, 8 (1) : 295-309. doi: 10.3934/cpaa.2009.8.295 [19] Huseyin Coskun. Nonlinear decomposition principle and fundamental matrix solutions for dynamic compartmental systems. Discrete & Continuous Dynamical Systems - B, 2019, 24 (12) : 6553-6605. doi: 10.3934/dcdsb.2019155 [20] Lingling Lv, Zhe Zhang, Lei Zhang, Weishu Wang. An iterative algorithm for periodic sylvester matrix equations. Journal of Industrial & Management Optimization, 2018, 14 (1) : 413-425. doi: 10.3934/jimo.2017053

Impact Factor: