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

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

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

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

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

Keywords: Low-rank matrix recovery, Schatten-p minimization, spherical section property.

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

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

Tools

Metrics

Other articles
by authors

on AIMS
Yifu Feng Min Zhang
on Google Scholar
Yifu Feng Min Zhang

2020 Impact Factor: 1.801

Tools

Article outline

2020 Impact Factor: 1.801

Tools

Metrics

Other articles
by authors

on AIMS
Yifu Feng Min Zhang
on Google Scholar
Yifu Feng Min Zhang

[Back to Top]