- Previous Article
- IPI Home
- This Issue
-
Next Article
Reconstruction of the singularities of a potential from backscattering data in 2D and 3D
Strongly convex programming for exact matrix completion and robust principal component analysis
1. | Department of Mathematics and Systems Science, National University of Defense Technology, Changsha, Hunan 410073, China, China, China |
2. | Department of Mathematics, University of Iowa, Iowa City, IA 52242, United States |
References:
[1] |
A. Argyriou, T. Evgeniou and M. Pontil, Multi-task feature learning, Advances in Neural Information Processing Systems (NIPS), 2007. |
[2] |
J.-F. Cai, E.J. Candès and Z. Shen, A singular value thresholding algorithm for matrixcompletion, SIAM J. on Optimization, 20 (2010), 1956-1982.
doi: 10.1137/080738970. |
[3] |
J.-F. Cai, S. Osher and Z. Shen, Linearized Bregman iterations for compressed sensing, Math. Comp., 78 (2009), 1515-1536.
doi: 10.1090/S0025-5718-08-02189-3. |
[4] |
J.-F. Cai, S. Osher and Z. Shen, Convergence of the linearized Bregman iteration for ℓ$_1$-norm minimization, Math. Comp., 78 (2009), 2127-2136.
doi: 10.1090/S0025-5718-09-02242-X. |
[5] |
J.-F. Cai, S. Osher and Z. Shen, Linearized Bregman iterations for frame-based image deblurring, SIAM J. Imaging Sciences, 2 (2009), 226-252. |
[6] |
E. J. Candès and B. Recht, Exact matrix completion via convexoptimization, Foundations of Computational Mathematics, 9 (2009), 717-772. |
[7] |
E.J. Candès and T. Tao, The power of convex relaxation: Near-optimal matrix completion, IEEE Transactions on InformationTheory, 56 (2010), 2053-2086.
doi: 10.1109/TIT.2010.2044061. |
[8] |
E. J. Candès and Y. Plan, Matrix completion with noise, Proceeding of the IEEE, 98 (2010), 925-936.
doi: 10.1109/JPROC.2009.2035722. |
[9] |
E. J. Candès, X. Li, Y. Ma and J. Wright, Robust principal component analysis?, Journal of ACM, 58 (2011), 1-37. |
[10] |
E. J. Candès and T. Tao, Decoding by linear programming, IEEE Transactions on Information Theory, 51 (2006), 4203-4215. |
[11] |
E.J. Candès, J. Romberg and T. Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inform. Theory, 52 (2006), 489-509.
doi: 10.1109/TIT.2005.862083. |
[12] |
V. Chandrasekharan, S. Sanghavi, P. Parillo and A. Wilsky, Rank-sparsity incoherence for matrix decomposition, SIAM Journal on Optimization, 21 (2011), 572-596.
doi: 10.1137/090761793. |
[13] |
S. S. Chen, D. L. Donoho and M. A. Saunders, Atomic decomposition by basis pursuit, SIAM J. Sci. Comput., 20 (1998), 33-61.
doi: 10.1137/S1064827596304010. |
[14] |
D. L. Donoho, Compressed sensing, IEEE Trans. Inform. Theory, 52 (2006), 1289-1306.
doi: 10.1109/TIT.2006.871582. |
[15] |
M. Fazel, "Matrix Rank Minimization with Applications," Ph.D. thesis, Stanford University, 2002. |
[16] |
M. P. Friedlander and P. Tseng, Exact regularization of convex programs, SIAM J. Optim., 18 (2007), 1326-1350.
doi: 10.1137/060675320. |
[17] |
H. Gao, J.-F. Cai, Z. Shen and H. Zhao, Robust principalcomponent analysis-based four-dimensional computed tomography, Physics in Medicine and Biology, 56 (2011), 3181-3198. |
[18] |
D. Gross, Recovering low-rank matrices from few coefficients in any basis, IEEE Trans. Inform. Theory, 57 (2011), 1548-1566.
doi: 10.1109/TIT.2011.2104999. |
[19] |
H. Ji, S. Huang, Z. Shen and Y. Xu, Robust video restoration by joint sparse and low rank matrix approximation, SIAM Journal on Imaging Sciences, 4 (2011), 1122-1142. |
[20] |
H. Ji, C. Liu, Z. W. Shen and Y. Xu, Robust video denoising using low rank matrix completion, IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), San Francisco, (2010), 1791-1798. |
[21] |
Z. Liu and L. Vandenberghe, Interior-point method for nuclear norm approximation with application to system identification, SIAM Journal on Matrix Analysis and Applications, 31 (2009), 1235-1256.
doi: 10.1137/090755436. |
[22] |
Z. Lin, A. Ganesh, J. Wright, L. Wu, M. Chen and Y. Ma, Fastconvex optimization algorithms for exact recovery of a corrupted low-rank matrix, Technical Report UILU-ENG-09-2214, 2010. |
[23] |
Z. Lin, M. Chen, L. Wu and Y. Ma, The augmentedLagrange multiplier method for exact recovery of corrupted low-rankmatrices, Technical Report UILU-ENG-09-2215, 2010. |
[24] |
K. Min, Z. D. Zhang, J. Writht and Y. Ma, Decomposing background topic from keywords by principle component pursuit, Proceeding of the 19th ACM Interational Conference on Information and Knowledge, (2010), 269-278. |
[25] |
J. Meng, W. Yin, E. Houssain and Z. Han, Collaborative spectrum sensing from sparse observations using matrix completion for cognitive radio networks, Proceedings of ICASSP, (2010), 3114-3117. |
[26] |
S. Ma, D. Goldfarb and L. Chen, Fixed point and Bregman iterativemethods for matrix rank minimization, Mathematical Programming Series A, 128 (2011), 321-353.
doi: 10.1007/s10107-009-0306-5. |
[27] |
M. Mesbahi and G. P. Papavassilopoulos, On the rank minimization problem over a positive semidefinite linear matrix inequality, IEEE Transactions on Automatic Control, 42 (1997), 239-243.
doi: 10.1109/9.554402. |
[28] |
Y. Nesterov, Smooth minimization of non-smooth functions, Math. Program. Serie A, 103 (2005), 127-152. |
[29] |
S. Osher, Y. Mao, B. Dong and W. Yin, Fast linearized Bregman iteration for compressive sensing and sparse denoising, Comm. in Math. Sciences, 1 (2010), 93-111. |
[30] |
B. Recht, M. Fazel and P. Parrilo, Guaranteed minimum rank solutionsof matrix equations via nuclear norm minimization, SIAM Review, 52 (2010), 471-501.
doi: 10.1137/070697835. |
[31] |
B. Recht, W. Xu and B. Hassibi, Necessary and sufficient conditions forsuccess of the nuclear norm heuristic for rank minimization, Proceedings of the 47th IEEE Conference on Decision and Control, (2008), 3065-3070. |
[32] |
B. Recht, W. Xu and B. Hassibi, Null space conditions and thresholds for rank minimization, Mathematics Programming, 127 (2011), 175-202.
doi: 10.1007/s10107-010-0422-2. |
[33] |
B. Recht, A simpler approach to matrix completion, J. Machine Learning Res., 12 (2011), 3413-3430. |
[34] |
R. T. Rockafellar, "Convex Analysis," Princeton University Press, Princeton, NJ, 1970. |
[35] |
K. C. Toh and S. Yun, An accelerated proximal gradient algorithm fornuclear norm regularized least squares problems, Pacific Journal of Optimization, 6 (2009), 615-640. |
[36] |
C. Tomasi and T. Kanade, Shape and motion from image streams under orthography: A factorization method, International Journal of Computer Vision, 9 (1992), 137-154. |
[37] |
J. Wright, A. Ganesh, S. Rao and Y. Ma, Robust principal component analysis: Exact recovery of corrupted low-rank matrices via convex optimization, submitted to Journal of the ACM, 2009, arXiv:0905.0233. |
[38] |
W. Yin, Analysis and generalizations of the linearized Bregman method, SIAM Journal on Image Science, 3 (2010), 856-877. |
[39] |
W. Yin, S. Osher, D. Goldfarb and J. Darbon, Bregman iterative algorithms for $l_1$ minimization with applications to compressed sensing, SIAM J. Imaging Sciences, 1 (2008), 143-168. |
[40] |
Z. D. Zhang, X. Liang, A. Ganesh and Y. Ma, TILT: Transform invariant low-rank textures, Computer Vision-ACCV, (2010), 314-328. |
[41] |
H. Zhang and L. Z. Cheng, Projected Landweber iteration for matrix completion, Journal of Computational and Applied Mathematics, 235 (2010), 593-601.
doi: 10.1016/j.cam.2010.06.010. |
[42] |
H. Zhang, L. Z. Cheng and W. Zhu, A lower bound guaranteeing exact matrix completion via singular value thresholding algorithm, Applied and Computational Harmonic Analysis, 31 (2011), 454-459.
doi: 10.1016/j.acha.2011.04.004. |
[43] |
H. Zhang, L. Z. Cheng and W. Zhu, Nuclear norm regularization with low-rank constraint for matrix completion, Inverse Problems, 26 (2010), 115009, 15 pp.
doi: 10.1088/0266-5611/26/11/115009. |
show all references
References:
[1] |
A. Argyriou, T. Evgeniou and M. Pontil, Multi-task feature learning, Advances in Neural Information Processing Systems (NIPS), 2007. |
[2] |
J.-F. Cai, E.J. Candès and Z. Shen, A singular value thresholding algorithm for matrixcompletion, SIAM J. on Optimization, 20 (2010), 1956-1982.
doi: 10.1137/080738970. |
[3] |
J.-F. Cai, S. Osher and Z. Shen, Linearized Bregman iterations for compressed sensing, Math. Comp., 78 (2009), 1515-1536.
doi: 10.1090/S0025-5718-08-02189-3. |
[4] |
J.-F. Cai, S. Osher and Z. Shen, Convergence of the linearized Bregman iteration for ℓ$_1$-norm minimization, Math. Comp., 78 (2009), 2127-2136.
doi: 10.1090/S0025-5718-09-02242-X. |
[5] |
J.-F. Cai, S. Osher and Z. Shen, Linearized Bregman iterations for frame-based image deblurring, SIAM J. Imaging Sciences, 2 (2009), 226-252. |
[6] |
E. J. Candès and B. Recht, Exact matrix completion via convexoptimization, Foundations of Computational Mathematics, 9 (2009), 717-772. |
[7] |
E.J. Candès and T. Tao, The power of convex relaxation: Near-optimal matrix completion, IEEE Transactions on InformationTheory, 56 (2010), 2053-2086.
doi: 10.1109/TIT.2010.2044061. |
[8] |
E. J. Candès and Y. Plan, Matrix completion with noise, Proceeding of the IEEE, 98 (2010), 925-936.
doi: 10.1109/JPROC.2009.2035722. |
[9] |
E. J. Candès, X. Li, Y. Ma and J. Wright, Robust principal component analysis?, Journal of ACM, 58 (2011), 1-37. |
[10] |
E. J. Candès and T. Tao, Decoding by linear programming, IEEE Transactions on Information Theory, 51 (2006), 4203-4215. |
[11] |
E.J. Candès, J. Romberg and T. Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inform. Theory, 52 (2006), 489-509.
doi: 10.1109/TIT.2005.862083. |
[12] |
V. Chandrasekharan, S. Sanghavi, P. Parillo and A. Wilsky, Rank-sparsity incoherence for matrix decomposition, SIAM Journal on Optimization, 21 (2011), 572-596.
doi: 10.1137/090761793. |
[13] |
S. S. Chen, D. L. Donoho and M. A. Saunders, Atomic decomposition by basis pursuit, SIAM J. Sci. Comput., 20 (1998), 33-61.
doi: 10.1137/S1064827596304010. |
[14] |
D. L. Donoho, Compressed sensing, IEEE Trans. Inform. Theory, 52 (2006), 1289-1306.
doi: 10.1109/TIT.2006.871582. |
[15] |
M. Fazel, "Matrix Rank Minimization with Applications," Ph.D. thesis, Stanford University, 2002. |
[16] |
M. P. Friedlander and P. Tseng, Exact regularization of convex programs, SIAM J. Optim., 18 (2007), 1326-1350.
doi: 10.1137/060675320. |
[17] |
H. Gao, J.-F. Cai, Z. Shen and H. Zhao, Robust principalcomponent analysis-based four-dimensional computed tomography, Physics in Medicine and Biology, 56 (2011), 3181-3198. |
[18] |
D. Gross, Recovering low-rank matrices from few coefficients in any basis, IEEE Trans. Inform. Theory, 57 (2011), 1548-1566.
doi: 10.1109/TIT.2011.2104999. |
[19] |
H. Ji, S. Huang, Z. Shen and Y. Xu, Robust video restoration by joint sparse and low rank matrix approximation, SIAM Journal on Imaging Sciences, 4 (2011), 1122-1142. |
[20] |
H. Ji, C. Liu, Z. W. Shen and Y. Xu, Robust video denoising using low rank matrix completion, IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), San Francisco, (2010), 1791-1798. |
[21] |
Z. Liu and L. Vandenberghe, Interior-point method for nuclear norm approximation with application to system identification, SIAM Journal on Matrix Analysis and Applications, 31 (2009), 1235-1256.
doi: 10.1137/090755436. |
[22] |
Z. Lin, A. Ganesh, J. Wright, L. Wu, M. Chen and Y. Ma, Fastconvex optimization algorithms for exact recovery of a corrupted low-rank matrix, Technical Report UILU-ENG-09-2214, 2010. |
[23] |
Z. Lin, M. Chen, L. Wu and Y. Ma, The augmentedLagrange multiplier method for exact recovery of corrupted low-rankmatrices, Technical Report UILU-ENG-09-2215, 2010. |
[24] |
K. Min, Z. D. Zhang, J. Writht and Y. Ma, Decomposing background topic from keywords by principle component pursuit, Proceeding of the 19th ACM Interational Conference on Information and Knowledge, (2010), 269-278. |
[25] |
J. Meng, W. Yin, E. Houssain and Z. Han, Collaborative spectrum sensing from sparse observations using matrix completion for cognitive radio networks, Proceedings of ICASSP, (2010), 3114-3117. |
[26] |
S. Ma, D. Goldfarb and L. Chen, Fixed point and Bregman iterativemethods for matrix rank minimization, Mathematical Programming Series A, 128 (2011), 321-353.
doi: 10.1007/s10107-009-0306-5. |
[27] |
M. Mesbahi and G. P. Papavassilopoulos, On the rank minimization problem over a positive semidefinite linear matrix inequality, IEEE Transactions on Automatic Control, 42 (1997), 239-243.
doi: 10.1109/9.554402. |
[28] |
Y. Nesterov, Smooth minimization of non-smooth functions, Math. Program. Serie A, 103 (2005), 127-152. |
[29] |
S. Osher, Y. Mao, B. Dong and W. Yin, Fast linearized Bregman iteration for compressive sensing and sparse denoising, Comm. in Math. Sciences, 1 (2010), 93-111. |
[30] |
B. Recht, M. Fazel and P. Parrilo, Guaranteed minimum rank solutionsof matrix equations via nuclear norm minimization, SIAM Review, 52 (2010), 471-501.
doi: 10.1137/070697835. |
[31] |
B. Recht, W. Xu and B. Hassibi, Necessary and sufficient conditions forsuccess of the nuclear norm heuristic for rank minimization, Proceedings of the 47th IEEE Conference on Decision and Control, (2008), 3065-3070. |
[32] |
B. Recht, W. Xu and B. Hassibi, Null space conditions and thresholds for rank minimization, Mathematics Programming, 127 (2011), 175-202.
doi: 10.1007/s10107-010-0422-2. |
[33] |
B. Recht, A simpler approach to matrix completion, J. Machine Learning Res., 12 (2011), 3413-3430. |
[34] |
R. T. Rockafellar, "Convex Analysis," Princeton University Press, Princeton, NJ, 1970. |
[35] |
K. C. Toh and S. Yun, An accelerated proximal gradient algorithm fornuclear norm regularized least squares problems, Pacific Journal of Optimization, 6 (2009), 615-640. |
[36] |
C. Tomasi and T. Kanade, Shape and motion from image streams under orthography: A factorization method, International Journal of Computer Vision, 9 (1992), 137-154. |
[37] |
J. Wright, A. Ganesh, S. Rao and Y. Ma, Robust principal component analysis: Exact recovery of corrupted low-rank matrices via convex optimization, submitted to Journal of the ACM, 2009, arXiv:0905.0233. |
[38] |
W. Yin, Analysis and generalizations of the linearized Bregman method, SIAM Journal on Image Science, 3 (2010), 856-877. |
[39] |
W. Yin, S. Osher, D. Goldfarb and J. Darbon, Bregman iterative algorithms for $l_1$ minimization with applications to compressed sensing, SIAM J. Imaging Sciences, 1 (2008), 143-168. |
[40] |
Z. D. Zhang, X. Liang, A. Ganesh and Y. Ma, TILT: Transform invariant low-rank textures, Computer Vision-ACCV, (2010), 314-328. |
[41] |
H. Zhang and L. Z. Cheng, Projected Landweber iteration for matrix completion, Journal of Computational and Applied Mathematics, 235 (2010), 593-601.
doi: 10.1016/j.cam.2010.06.010. |
[42] |
H. Zhang, L. Z. Cheng and W. Zhu, A lower bound guaranteeing exact matrix completion via singular value thresholding algorithm, Applied and Computational Harmonic Analysis, 31 (2011), 454-459.
doi: 10.1016/j.acha.2011.04.004. |
[43] |
H. Zhang, L. Z. Cheng and W. Zhu, Nuclear norm regularization with low-rank constraint for matrix completion, Inverse Problems, 26 (2010), 115009, 15 pp.
doi: 10.1088/0266-5611/26/11/115009. |
[1] |
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 |
[2] |
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 |
[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] |
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 |
[5] |
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 |
[6] |
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 |
[7] |
Ningyu Sha, Lei Shi, Ming Yan. Fast algorithms for robust principal component analysis with an upper bound on the rank. Inverse Problems and Imaging, 2021, 15 (1) : 109-128. doi: 10.3934/ipi.2020067 |
[8] |
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 |
[9] |
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 |
[10] |
Henry Adams, Lara Kassab, Deanna Needell. An adaptation for iterative structured matrix completion. Foundations of Data Science, 2021, 3 (4) : 769-791. doi: 10.3934/fods.2021028 |
[11] |
Paul Skerritt, Cornelia Vizman. Dual pairs for matrix groups. Journal of Geometric Mechanics, 2019, 11 (2) : 255-275. doi: 10.3934/jgm.2019014 |
[12] |
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, 2022 doi: 10.3934/jimo.2022045 |
[13] |
Yuhong Dai, Nobuo Yamashita. Convergence analysis of sparse quasi-Newton updates with positive definite matrix completion for two-dimensional functions. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 61-69. doi: 10.3934/naco.2011.1.61 |
[14] |
Yuan Shen, Xin Liu. An alternating minimization method for matrix completion problems. Discrete and Continuous Dynamical Systems - S, 2020, 13 (6) : 1757-1772. doi: 10.3934/dcdss.2020103 |
[15] |
Yi Yang, Jianwei Ma, Stanley Osher. Seismic data reconstruction via matrix completion. Inverse Problems and Imaging, 2013, 7 (4) : 1379-1392. doi: 10.3934/ipi.2013.7.1379 |
[16] |
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 |
[17] |
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 |
[18] |
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 |
[19] |
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 |
[20] |
Vladimir Pozdyayev. 2D system analysis via dual problems and polynomial matrix inequalities. Numerical Algebra, Control and Optimization, 2016, 6 (4) : 491-504. doi: 10.3934/naco.2016022 |
2020 Impact Factor: 1.639
Tools
Metrics
Other articles
by authors
[Back to Top]