
-
Previous Article
Adversarial defense via the data-dependent activation, total variation minimization, and adversarial training
- IPI Home
- This Issue
-
Next Article
Stochastic greedy algorithms for multiple measurement vectors
Fast algorithms for robust principal component analysis with an upper bound on the rank
1. | Department of Computational Mathematics, Science and Engineering, Michigan State University, East Lansing, MI 48824, USA |
2. | School of Mathematical Sciences, Shanghai Key Laboratory for Contemporary Applied Mathematics, Key Laboratory of Mathematics for Nonlinear Sciences (Fudan University), Ministry of Education, Fudan University, Shanghai, 200433, China |
3. | Department of Computational Mathematics, Science and Engineering, Department of Mathematics, Michigan State University, East Lansing, MI 48824, USA |
The robust principal component analysis (RPCA) decomposes a data matrix into a low-rank part and a sparse part. There are mainly two types of algorithms for RPCA. The first type of algorithm applies regularization terms on the singular values of a matrix to obtain a low-rank matrix. However, calculating singular values can be very expensive for large matrices. The second type of algorithm replaces the low-rank matrix as the multiplication of two small matrices. They are faster than the first type because no singular value decomposition (SVD) is required. However, the rank of the low-rank matrix is required, and an accurate rank estimation is needed to obtain a reasonable solution. In this paper, we propose algorithms that combine both types. Our proposed algorithms require an upper bound of the rank and SVD on small matrices. First, they are faster than the first type because the cost of SVD on small matrices is negligible. Second, they are more robust than the second type because an upper bound of the rank instead of the exact rank is required. Furthermore, we apply the Gauss-Newton method to increase the speed of our algorithms. Numerical experiments show the better performance of our proposed algorithms.
References:
[1] |
E. Amaldi and V. Kann,
On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems, Theoretical Computer Science, 209 (1998), 237-260.
doi: 10.1016/S0304-3975(97)00115-1. |
[2] |
T. Bouwmans and E. H. Zahzah,
Robust pca via principal component pursuit: A review for a comparative evaluation in video surveillance, Computer Vision and Image Understanding, 122 (2014), 22-34.
|
[3] |
H. Cai, J.-F. Cai and K. Wei,
Accelerated alternating projections for robust principal component analysis, The Journal of Machine Learning Research, 20 (2019), 685-717.
|
[4] |
E. J. Candès, X. Li, Y. Ma and J. Wright,
Robust principal component analysis?, Journal of the ACM (JACM), 58 (2011), 1-37.
doi: 10.1145/1970392.1970395. |
[5] |
R. Chartrand,
Exact reconstruction of sparse signals via nonconvex minimization, IEEE Signal Processing Letters, 14 (2007), 707-710.
doi: 10.1109/LSP.2007.898300. |
[6] |
J. P. Cunningham and Z. Ghahramani,
Linear dimensionality reduction: Survey, insights, and generalizations, The Journal of Machine Learning Research, 16 (2015), 2859-2900.
|
[7] |
J. F. P. Da Costa, H. Alonso and L. Roque,
A weighted principal component analysis and its application to gene expression data, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 8 (2009), 246-252.
|
[8] |
F. De la Torre and M. J. Black, Robust principal component analysis for computer vision, in Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001, vol. 1, IEEE, 2001, 362-369. |
[9] |
E. Elhamifar and R. Vidal,
Sparse subspace clustering: Algorithm, theory, and applications, IEEE transactions on pattern analysis and machine intelligence, 35 (2013), 2765-2781.
doi: 10.1109/TPAMI.2013.57. |
[10] |
J. Fan and R. Li,
Variable selection via nonconcave penalized likelihood and its oracle properties, Journal of the American statistical Association, 96 (2001), 1348-1360.
doi: 10.1198/016214501753382273. |
[11] |
R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge university press, 2013.
![]() ![]() |
[12] |
X.-L. Huang, L. Shi and M. Yan,
Nonconvex sorted $\ell_1$ minimization for sparse approximation, Journal of the Operations Research Society of China, 3 (2015), 207-229.
doi: 10.1007/s40305-014-0069-4. |
[13] |
G. Li and T. K. Pong,
Global convergence of splitting methods for nonconvex composite optimization, SIAM Journal on Optimization, 25 (2015), 2434-2460.
doi: 10.1137/140998135. |
[14] |
H. Li and Z. Lin, Accelerated proximal gradient methods for nonconvex programming, in Advances in Neural Information Processing Systems, 2015, 379-387. |
[15] |
Z. Lin, M. Chen and Y. Ma, The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices. 2010, arXiv preprint arXiv: 1009.5055, (2010), 663-670. |
[16] |
G. Liu, Z. Lin, S. Yan, J. Sun, Y. Yu and Y. Ma,
Robust recovery of subspace structures by low-rank representation, IEEE Transactions on Pattern Analysis and Machine Intelligence, 35 (2012), 171-184.
|
[17] |
X. Liu, Z. Wen and Y. Zhang,
An efficient Gauss-Newton algorithm for symmetric low-rank product matrix approximations, SIAM Journal on Optimization, 25 (2015), 1571-1608.
doi: 10.1137/140971464. |
[18] |
Y. Lou and M. Yan,
Fast l1-l2 minimization via a proximal operator, Journal of Scientific Computing, 74 (2018), 767-785.
doi: 10.1007/s10915-017-0463-2. |
[19] |
N. Sha, M. Yan and Y. Lin, Efficient seismic denoising techniques using robust principal component analysis, in SEG Technical Program Expanded Abstracts 2019, Society of Exploration Geophysicists, 2019, 2543-2547. |
[20] |
Y. Shen, H. Xu and X. Liu,
An alternating minimization method for robust principal component analysis, Optimization Methods and Software, 34 (2019), 1251-1276.
doi: 10.1080/10556788.2018.1496086. |
[21] |
M. Tao and X. Yuan,
Recovering low-rank and sparse components of matrices from incomplete and noisy observations, SIAM Journal on Optimization, 21 (2011), 57-81.
doi: 10.1137/100781894. |
[22] |
L. N. Trefethen and D. Bau â…¢, Numerical linear algebra, vol. 50, SIAM, 1997. |
[23] |
F. Wen, R. Ying, P. Liu and T.-K. Truong,
Nonconvex regularized robust PCA using the proximal block coordinate descent algorithm, IEEE Transactions on Signal Processing, 67 (2019), 5402-5416.
doi: 10.1109/TSP.2019.2940121. |
[24] |
Z. Wen, W. Yin and Y. Zhang,
Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm, Mathematical Programming Computation, 4 (2012), 333-361.
doi: 10.1007/s12532-012-0044-1. |
[25] |
J. Wright, A. Ganesh, S. Rao, Y. Peng and Y. Ma, Robust principal component analysis: Exact recovery of corrupted low-rank matrices via convex optimization, in Advances in Neural Information Processing Systems, 2009, 2080-2088. |
[26] |
X. Yuan and J. Yang, Sparse and low-rank matrix decomposition via alternating direction methods, preprint, 12 (2009). |
[27] |
C.-H. Zhang,
Nearly unbiased variable selection under minimax concave penalty, The Annals of Statistics, 38 (2010), 894-942.
doi: 10.1214/09-AOS729. |
show all references
References:
[1] |
E. Amaldi and V. Kann,
On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems, Theoretical Computer Science, 209 (1998), 237-260.
doi: 10.1016/S0304-3975(97)00115-1. |
[2] |
T. Bouwmans and E. H. Zahzah,
Robust pca via principal component pursuit: A review for a comparative evaluation in video surveillance, Computer Vision and Image Understanding, 122 (2014), 22-34.
|
[3] |
H. Cai, J.-F. Cai and K. Wei,
Accelerated alternating projections for robust principal component analysis, The Journal of Machine Learning Research, 20 (2019), 685-717.
|
[4] |
E. J. Candès, X. Li, Y. Ma and J. Wright,
Robust principal component analysis?, Journal of the ACM (JACM), 58 (2011), 1-37.
doi: 10.1145/1970392.1970395. |
[5] |
R. Chartrand,
Exact reconstruction of sparse signals via nonconvex minimization, IEEE Signal Processing Letters, 14 (2007), 707-710.
doi: 10.1109/LSP.2007.898300. |
[6] |
J. P. Cunningham and Z. Ghahramani,
Linear dimensionality reduction: Survey, insights, and generalizations, The Journal of Machine Learning Research, 16 (2015), 2859-2900.
|
[7] |
J. F. P. Da Costa, H. Alonso and L. Roque,
A weighted principal component analysis and its application to gene expression data, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 8 (2009), 246-252.
|
[8] |
F. De la Torre and M. J. Black, Robust principal component analysis for computer vision, in Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001, vol. 1, IEEE, 2001, 362-369. |
[9] |
E. Elhamifar and R. Vidal,
Sparse subspace clustering: Algorithm, theory, and applications, IEEE transactions on pattern analysis and machine intelligence, 35 (2013), 2765-2781.
doi: 10.1109/TPAMI.2013.57. |
[10] |
J. Fan and R. Li,
Variable selection via nonconcave penalized likelihood and its oracle properties, Journal of the American statistical Association, 96 (2001), 1348-1360.
doi: 10.1198/016214501753382273. |
[11] |
R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge university press, 2013.
![]() ![]() |
[12] |
X.-L. Huang, L. Shi and M. Yan,
Nonconvex sorted $\ell_1$ minimization for sparse approximation, Journal of the Operations Research Society of China, 3 (2015), 207-229.
doi: 10.1007/s40305-014-0069-4. |
[13] |
G. Li and T. K. Pong,
Global convergence of splitting methods for nonconvex composite optimization, SIAM Journal on Optimization, 25 (2015), 2434-2460.
doi: 10.1137/140998135. |
[14] |
H. Li and Z. Lin, Accelerated proximal gradient methods for nonconvex programming, in Advances in Neural Information Processing Systems, 2015, 379-387. |
[15] |
Z. Lin, M. Chen and Y. Ma, The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices. 2010, arXiv preprint arXiv: 1009.5055, (2010), 663-670. |
[16] |
G. Liu, Z. Lin, S. Yan, J. Sun, Y. Yu and Y. Ma,
Robust recovery of subspace structures by low-rank representation, IEEE Transactions on Pattern Analysis and Machine Intelligence, 35 (2012), 171-184.
|
[17] |
X. Liu, Z. Wen and Y. Zhang,
An efficient Gauss-Newton algorithm for symmetric low-rank product matrix approximations, SIAM Journal on Optimization, 25 (2015), 1571-1608.
doi: 10.1137/140971464. |
[18] |
Y. Lou and M. Yan,
Fast l1-l2 minimization via a proximal operator, Journal of Scientific Computing, 74 (2018), 767-785.
doi: 10.1007/s10915-017-0463-2. |
[19] |
N. Sha, M. Yan and Y. Lin, Efficient seismic denoising techniques using robust principal component analysis, in SEG Technical Program Expanded Abstracts 2019, Society of Exploration Geophysicists, 2019, 2543-2547. |
[20] |
Y. Shen, H. Xu and X. Liu,
An alternating minimization method for robust principal component analysis, Optimization Methods and Software, 34 (2019), 1251-1276.
doi: 10.1080/10556788.2018.1496086. |
[21] |
M. Tao and X. Yuan,
Recovering low-rank and sparse components of matrices from incomplete and noisy observations, SIAM Journal on Optimization, 21 (2011), 57-81.
doi: 10.1137/100781894. |
[22] |
L. N. Trefethen and D. Bau â…¢, Numerical linear algebra, vol. 50, SIAM, 1997. |
[23] |
F. Wen, R. Ying, P. Liu and T.-K. Truong,
Nonconvex regularized robust PCA using the proximal block coordinate descent algorithm, IEEE Transactions on Signal Processing, 67 (2019), 5402-5416.
doi: 10.1109/TSP.2019.2940121. |
[24] |
Z. Wen, W. Yin and Y. Zhang,
Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm, Mathematical Programming Computation, 4 (2012), 333-361.
doi: 10.1007/s12532-012-0044-1. |
[25] |
J. Wright, A. Ganesh, S. Rao, Y. Peng and Y. Ma, Robust principal component analysis: Exact recovery of corrupted low-rank matrices via convex optimization, in Advances in Neural Information Processing Systems, 2009, 2080-2088. |
[26] |
X. Yuan and J. Yang, Sparse and low-rank matrix decomposition via alternating direction methods, preprint, 12 (2009). |
[27] |
C.-H. Zhang,
Nearly unbiased variable selection under minimax concave penalty, The Annals of Statistics, 38 (2010), 894-942.
doi: 10.1214/09-AOS729. |




Algorithm 1: Proposed Algorithm |
Input: Output: ![]() |
Algorithm 1: Proposed Algorithm |
Input: Output: ![]() |
Algorithm 2: Accelerated algorithm with nonmonotone APG |
Input: Output: ![]() |
Algorithm 2: Accelerated algorithm with nonmonotone APG |
Input: Output: ![]() |
s | Shen et al.'s [20] | Alg. 1 | Alg.2 | ||||
25 | 20 | 0.0745 | 1318 | 0.0075 | 296 | 0.0075 | 68 |
50 | 20 | 0.0496 | 1434 | 0.0101 | 473 | 0.0088 | 77 |
25 | 40 | 0.0990 | 2443 | 0.0635 | 796 | 0.0915 | 187 |
s | Shen et al.'s [20] | Alg. 1 | Alg.2 | ||||
25 | 20 | 0.0745 | 1318 | 0.0075 | 296 | 0.0075 | 68 |
50 | 20 | 0.0496 | 1434 | 0.0101 | 473 | 0.0088 | 77 |
25 | 40 | 0.0990 | 2443 | 0.0635 | 796 | 0.0915 | 187 |
{s} | { |
ratio of missing entries | |
20 | 0.05 | 10% | 0.0079 |
20 | 0.05 | 20% | 0.0088 |
20 | 0.05 | 50% | 0.0201 |
5 | 0.01 | 50% | 0.0015 |
{s} | { |
ratio of missing entries | |
20 | 0.05 | 10% | 0.0079 |
20 | 0.05 | 20% | 0.0088 |
20 | 0.05 | 50% | 0.0201 |
5 | 0.01 | 50% | 0.0015 |
[1] |
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 |
[2] |
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 |
[3] |
Yitong Guo, Bingo Wing-Kuen Ling. Principal component analysis with drop rank covariance matrix. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2345-2366. doi: 10.3934/jimo.2020072 |
[4] |
Hui Zhang, Jian-Feng Cai, Lizhi Cheng, Jubo Zhu. Strongly convex programming for exact matrix completion and robust principal component analysis. Inverse Problems and Imaging, 2012, 6 (2) : 357-372. doi: 10.3934/ipi.2012.6.357 |
[5] |
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 and Imaging, 2020, 14 (2) : 339-361. doi: 10.3934/ipi.2020015 |
[6] |
Qingshan You, Qun Wan, Yipeng Liu. A short note on strongly convex programming for exact matrix completion and robust principal component analysis. Inverse Problems and Imaging, 2013, 7 (1) : 305-306. doi: 10.3934/ipi.2013.7.305 |
[7] |
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 |
[8] |
Simon Foucart, Richard G. Lynch. Recovering low-rank matrices from binary measurements. Inverse Problems and Imaging, 2019, 13 (4) : 703-720. doi: 10.3934/ipi.2019032 |
[9] |
Simon Arridge, Pascal Fernsel, Andreas Hauptmann. Joint reconstruction and low-rank decomposition for dynamic inverse problems. Inverse Problems and Imaging, 2022, 16 (3) : 483-523. doi: 10.3934/ipi.2021059 |
[10] |
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 |
[11] |
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 |
[12] |
Changming Song, Yun Wang. Nonlocal latent low rank sparse representation for single image super resolution via self-similarity learning. Inverse Problems and Imaging, 2021, 15 (6) : 1347-1362. doi: 10.3934/ipi.2021017 |
[13] |
Azam Moradi, Jafar Razmi, Reza Babazadeh, Ali Sabbaghnia. An integrated Principal Component Analysis and multi-objective mathematical programming approach to agile supply chain network design under uncertainty. Journal of Industrial and Management Optimization, 2019, 15 (2) : 855-879. doi: 10.3934/jimo.2018074 |
[14] |
Charles Curry, Stephen Marsland, Robert I McLachlan. Principal symmetric space analysis. Journal of Computational Dynamics, 2019, 6 (2) : 251-276. doi: 10.3934/jcd.2019013 |
[15] |
Chao Zhang, Jingjing Wang, Naihua Xiu. Robust and sparse portfolio model for index tracking. Journal of Industrial and Management Optimization, 2019, 15 (3) : 1001-1015. doi: 10.3934/jimo.2018082 |
[16] |
Mingchao Zhao, You-Wei Wen, Michael Ng, Hongwei Li. A nonlocal low rank model for poisson noise removal. Inverse Problems and Imaging, 2021, 15 (3) : 519-537. doi: 10.3934/ipi.2021003 |
[17] |
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 |
[18] |
Xianchao Xiu, Lingchen Kong. Rank-one and sparse matrix decomposition for dynamic MRI. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 127-134. doi: 10.3934/naco.2015.5.127 |
[19] |
Hang Xu, Song Li. Analysis non-sparse recovery for relaxed ALASSO. Communications on Pure and Applied Analysis, 2020, 19 (8) : 4055-4068. doi: 10.3934/cpaa.2020179 |
[20] |
Jing Zhou, Zhibin Deng. A low-dimensional SDP relaxation based spatial branch and bound method for nonconvex quadratic programs. Journal of Industrial and Management Optimization, 2020, 16 (5) : 2087-2102. doi: 10.3934/jimo.2019044 |
2020 Impact Factor: 1.639
Tools
Metrics
Other articles
by authors
[Back to Top]