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

Yifu Feng; Min Zhang

doi:10.3934/jimo.2018159

Article Contents

2020, Volume 16, Issue 1: 397-407. Doi: 10.3934/jimo.2018159

This issue Previous Article Option pricing formulas for generalized fuzzy stock model Next Article A hybrid chaos firefly algorithm for three-dimensional irregular packing problem

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

Yifu Feng^1, and
Min Zhang^2, ,

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
* Corresponding author: Min Zhang

Received: January 31, 2016

Revised: July 31, 2017

Early access: October 2018

Published: October 2019

Abstract Full Text(HTML) Related Papers Cited by

Abstract

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

Keywords:

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

Citation:

Full Text(HTML)

Related Papers

Cited by

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.