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: |
[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.![]() ![]() |