-
Previous Article
A hybrid chaos firefly algorithm for three-dimensional irregular packing problem
- JIMO Home
- This Issue
-
Next Article
Option pricing formulas for generalized fuzzy stock model
A $p$-spherical section property for matrix Schatten-$p$ quasi-norm minimization
1. | College of Mathematics, Jilin Normal University, Jilin Siping 136000, China |
2. | School of Mathematical Science, Chongqing Normal University 401131, China, and School of Elec Eng, Comp and Math Sci (EECMS), Curtin University 6102, Australia |
Low-rank matrix recovery has become a popular research topic with various applications in recent years. One of the most popular methods to dual with this problem for overcoming its NP-hardness is to relax it into some tractable optimization problems. In this paper, we consider a nonconvex relaxation, the Schatten-$p$ quasi-norm minimization ($0<p<1$), and discuss conditions for the equivalence between the original problem and this nonconvex relaxation. Specifically, based on null space analysis, we propose a $p$-spherical section property for the exact and approximate recovery via the Schatten-$p$ quasi-norm minimization ($0<p<1$).
References:
[1] |
T. T. Cai and A. Zhang,
Sparse representation of a polytope and recovery of sparse signals and low-rank matrices, IEEE Transactions on Information Theory, 60 (2014), 122-132.
doi: 10.1109/TIT.2013.2288639. |
[2] |
Y. Chen, S. Bhojanapalli, S. Sanghavi and R. Ward, Coherent matrix completion, in International Conference on Machine Learning, (2014), 674-682. |
[3] |
A. L. Chistov and D. Yu. Grigoriev, Complexity of quantifier elimination in the theory of algebraically closed fields, in Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, 176 (1984), 17-31.
doi: 10.1007/BFb0030287. |
[4] |
K. Dvijotham and M. Fazel, Nullspace conditions for the nuclear norm heuristic, In preparation, 2010. |
[5] |
K. Dvijotham and M. Fazel, A nullspace analysis of the nuclear norm heuristic for rank minimization, in Acoustics Speech and Signal Processing (ICASSP), IEEE, (2010), 3586-3589.
doi: 10.1109/ICASSP.2010.5495918. |
[6] |
M. Fazel, H. Hindi and S. Boyd, A rank minimization heuristic with application to minimum order system approximation, in Proceedings of the American Control Conference, IEEE, (2001), 4734-4739.
doi: 10.1109/ACC.2001.945730. |
[7] |
R. H. Keshavan, A. Montanari and S. Oh,
Matrix completion from a few entries, IEEE Transactions on Information Theory, 56 (2010), 2980-2998.
doi: 10.1109/TIT.2010.2046205. |
[8] |
L. C. Kong, L. Tuncel and N. H. Xiu, $s$-goodness for low-rank matrix recovery, Abstract and Applied Analysis, 2013 (2013), Art. ID 101974, 9 pp. |
[9] |
L. C. Kong and N. H. Xiu, Exact low-rank matrix recovery via nonconvex schatten $p$-minimization, Asia-Pacific Journal of Operational Research, 30 (2013), 1340010.
doi: 10.1142/S0217595913400101. |
[10] |
Y.-F. Li, Y. J. Zhang and Z.-H. Huang,
A reweighted nuclear norm minimization algorithm for low rank matrix recovery, Journal of Computational and Applied Mathematics, 263 (2014), 338-350.
doi: 10.1016/j.cam.2013.12.005. |
[11] |
L. Lu and R. Vidal, Combined central and subspace clustering for computer vision applications, in Proceedings of the 23rd International Conference on Machine Learning, ACM, 56 (2006), 593-600.
doi: 10.1145/1143844.1143919. |
[12] |
A. Majumdar and R. K. Ward,
An algorithm for sparse MRI reconstruction by Schatten $p$-norm minimization, Magnetic Resonance Imaging, 29 (2011), 408-417.
doi: 10.1016/j.mri.2010.09.001. |
[13] |
R. Meka, P. Jain, C. Caramanis and I. S. Dhillon, Rank minimization via online learning, in The International Conference on Machine learning, AMC, (2008), 656-663.
doi: 10.1145/1390156.1390239. |
[14] |
F. Nie, H. Huang and C.H.F. Ding, An algorithm for sparse MRI reconstruction by Schatten $p$-norm minimization, AAAI, 2012. |
[15] |
B. Recht, W. Xu and B. Hassibi, Necessary and sufficient condtions for success of the nuclear norm heuristic for rank minimization, in 47th IEEE Conference on Decision and Control, (2008), 3065-3070. |
[16] |
M.C. Yue and A. M. C. So,
A perturbation inequality for concave functions of singular values and its applications in low-rank matrix recovery, Applied and Computational Harmonic Analysis, 40 (2016), 396-416.
doi: 10.1016/j.acha.2015.06.006. |
[17] |
M. Zhang, Z. H. Huang and Y. Zhang,
Restricted $p$-isometry properties of nonconvex matrix recovery, IEEE Transactions on Information Theory, 59 (2013), 4316-4323.
doi: 10.1109/TIT.2013.2250577. |
[18] |
Y. Q. Zhao and J. Yang,
Hyperspectral image denoising via sparse representation and low-rank constraint, IEEE Transactions on Geoscience and Remote Sensing, 53 (2015), 296-308.
|
[19] |
Z. Zheng, M. Yu, J. Jia, H. Liu, D. Xiang, X. Huang and J. Yang,
Fisher discrimination based low rank matrix recovery for face recognition, Pattern Recognition, 47 (2014), 3502-3511.
doi: 10.1016/j.patcog.2014.05.001. |
show all references
References:
[1] |
T. T. Cai and A. Zhang,
Sparse representation of a polytope and recovery of sparse signals and low-rank matrices, IEEE Transactions on Information Theory, 60 (2014), 122-132.
doi: 10.1109/TIT.2013.2288639. |
[2] |
Y. Chen, S. Bhojanapalli, S. Sanghavi and R. Ward, Coherent matrix completion, in International Conference on Machine Learning, (2014), 674-682. |
[3] |
A. L. Chistov and D. Yu. Grigoriev, Complexity of quantifier elimination in the theory of algebraically closed fields, in Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, 176 (1984), 17-31.
doi: 10.1007/BFb0030287. |
[4] |
K. Dvijotham and M. Fazel, Nullspace conditions for the nuclear norm heuristic, In preparation, 2010. |
[5] |
K. Dvijotham and M. Fazel, A nullspace analysis of the nuclear norm heuristic for rank minimization, in Acoustics Speech and Signal Processing (ICASSP), IEEE, (2010), 3586-3589.
doi: 10.1109/ICASSP.2010.5495918. |
[6] |
M. Fazel, H. Hindi and S. Boyd, A rank minimization heuristic with application to minimum order system approximation, in Proceedings of the American Control Conference, IEEE, (2001), 4734-4739.
doi: 10.1109/ACC.2001.945730. |
[7] |
R. H. Keshavan, A. Montanari and S. Oh,
Matrix completion from a few entries, IEEE Transactions on Information Theory, 56 (2010), 2980-2998.
doi: 10.1109/TIT.2010.2046205. |
[8] |
L. C. Kong, L. Tuncel and N. H. Xiu, $s$-goodness for low-rank matrix recovery, Abstract and Applied Analysis, 2013 (2013), Art. ID 101974, 9 pp. |
[9] |
L. C. Kong and N. H. Xiu, Exact low-rank matrix recovery via nonconvex schatten $p$-minimization, Asia-Pacific Journal of Operational Research, 30 (2013), 1340010.
doi: 10.1142/S0217595913400101. |
[10] |
Y.-F. Li, Y. J. Zhang and Z.-H. Huang,
A reweighted nuclear norm minimization algorithm for low rank matrix recovery, Journal of Computational and Applied Mathematics, 263 (2014), 338-350.
doi: 10.1016/j.cam.2013.12.005. |
[11] |
L. Lu and R. Vidal, Combined central and subspace clustering for computer vision applications, in Proceedings of the 23rd International Conference on Machine Learning, ACM, 56 (2006), 593-600.
doi: 10.1145/1143844.1143919. |
[12] |
A. Majumdar and R. K. Ward,
An algorithm for sparse MRI reconstruction by Schatten $p$-norm minimization, Magnetic Resonance Imaging, 29 (2011), 408-417.
doi: 10.1016/j.mri.2010.09.001. |
[13] |
R. Meka, P. Jain, C. Caramanis and I. S. Dhillon, Rank minimization via online learning, in The International Conference on Machine learning, AMC, (2008), 656-663.
doi: 10.1145/1390156.1390239. |
[14] |
F. Nie, H. Huang and C.H.F. Ding, An algorithm for sparse MRI reconstruction by Schatten $p$-norm minimization, AAAI, 2012. |
[15] |
B. Recht, W. Xu and B. Hassibi, Necessary and sufficient condtions for success of the nuclear norm heuristic for rank minimization, in 47th IEEE Conference on Decision and Control, (2008), 3065-3070. |
[16] |
M.C. Yue and A. M. C. So,
A perturbation inequality for concave functions of singular values and its applications in low-rank matrix recovery, Applied and Computational Harmonic Analysis, 40 (2016), 396-416.
doi: 10.1016/j.acha.2015.06.006. |
[17] |
M. Zhang, Z. H. Huang and Y. Zhang,
Restricted $p$-isometry properties of nonconvex matrix recovery, IEEE Transactions on Information Theory, 59 (2013), 4316-4323.
doi: 10.1109/TIT.2013.2250577. |
[18] |
Y. Q. Zhao and J. Yang,
Hyperspectral image denoising via sparse representation and low-rank constraint, IEEE Transactions on Geoscience and Remote Sensing, 53 (2015), 296-308.
|
[19] |
Z. Zheng, M. Yu, J. Jia, H. Liu, D. Xiang, X. Huang and J. Yang,
Fisher discrimination based low rank matrix recovery for face recognition, Pattern Recognition, 47 (2014), 3502-3511.
doi: 10.1016/j.patcog.2014.05.001. |
[1] |
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 |
[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] |
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 |
[4] |
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 |
[5] |
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 |
[6] |
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 |
[7] |
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 |
[8] |
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 |
[9] |
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 |
[10] |
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 |
[11] |
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 |
[12] |
Meijuan Shang, Yanan Liu, Lingchen Kong, Xianchao Xiu, Ying Yang. Nonconvex mixed matrix minimization. Mathematical Foundations of Computing, 2019, 2 (2) : 107-126. doi: 10.3934/mfc.2019009 |
[13] |
Ting Chen, Fusheng Lv, Wenchang Sun. Uniform Approximation Property of Frames with Applications to Erasure Recovery. Communications on Pure and Applied Analysis, 2022, 21 (3) : 1093-1107. doi: 10.3934/cpaa.2022011 |
[14] |
Djemaa Messaoudi, Osama Said Ahmed, Komivi Souley Agbodjan, Ting Cheng, Daijun Jiang. Numerical recovery of magnetic diffusivity in a three dimensional spherical dynamo equation. Inverse Problems and Imaging, 2020, 14 (5) : 797-818. doi: 10.3934/ipi.2020037 |
[15] |
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 |
[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] |
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 |
[18] |
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 and Imaging, 2021, 15 (3) : 475-498. doi: 10.3934/ipi.2021001 |
[19] |
Yu-Ning Yang, Su Zhang. On linear convergence of projected gradient method for a class of affine rank minimization problems. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1507-1519. doi: 10.3934/jimo.2016.12.1507 |
[20] |
Yongge Tian. A survey on rank and inertia optimization problems of the matrix-valued function $A + BXB^{*}$. Numerical Algebra, Control and Optimization, 2015, 5 (3) : 289-326. doi: 10.3934/naco.2015.5.289 |
2020 Impact Factor: 1.801
Tools
Metrics
Other articles
by authors
[Back to Top]