Article Contents
Article Contents

# A $p$-spherical section property for matrix Schatten-$p$ quasi-norm minimization

• * Corresponding author: Min Zhang
• 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$).

Mathematics Subject Classification: 90C26, 94A12, 90C59.

 Citation:

•  [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.