American Institute of Mathematical Sciences

January  2020, 16(1): 397-407. doi: 10.3934/jimo.2018159

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

* Corresponding author: Min Zhang

Received  February 2016 Revised  August 2017 Published  January 2020 Early access  October 2018

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$).

Citation: Yifu Feng, Min Zhang. A $p$-spherical section property for matrix Schatten-$p$ quasi-norm minimization. Journal of Industrial and Management Optimization, 2020, 16 (1) : 397-407. doi: 10.3934/jimo.2018159
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