• Previous Article
    Optimization of fourth order Sturm-Liouville type differential inclusions with initial point constraints
  • JIMO Home
  • This Issue
  • Next Article
    An accelerated augmented Lagrangian method for multi-criteria optimization problem
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  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 & Management Optimization, 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. KeshavanA. 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. LiY. 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. ZhangZ. 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. ZhengM. YuJ. JiaH. LiuD. XiangX. 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. KeshavanA. 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. LiY. 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. ZhangZ. 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. ZhengM. YuJ. JiaH. LiuD. XiangX. 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 & 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 & Imaging, 2015, 9 (2) : 601-624. doi: 10.3934/ipi.2015.9.601

[4]

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

[5]

Yu-Ning Yang, Su Zhang. On linear convergence of projected gradient method for a class of affine rank minimization problems. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1507-1519. doi: 10.3934/jimo.2016.12.1507

[6]

Yongge Tian. A survey on rank and inertia optimization problems of the matrix-valued function $A + BXB^{*}$. Numerical Algebra, Control & Optimization, 2015, 5 (3) : 289-326. doi: 10.3934/naco.2015.5.289

[7]

Xianchao Xiu, Lingchen Kong. Rank-one and sparse matrix decomposition for dynamic MRI. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 127-134. doi: 10.3934/naco.2015.5.127

[8]

Sihem Guerarra. Positive and negative definite submatrices in an Hermitian least rank solution of the matrix equation AXA*=B. Numerical Algebra, Control & Optimization, 2019, 9 (1) : 15-22. doi: 10.3934/naco.2019002

[9]

Manfred Einsiedler, Elon Lindenstrauss. On measures invariant under diagonalizable actions: the Rank-One case and the general Low-Entropy method. Journal of Modern Dynamics, 2008, 2 (1) : 83-128. doi: 10.3934/jmd.2008.2.83

[10]

Jiying Liu, Jubo Zhu, Fengxia Yan, Zenghui Zhang. Compressive sampling and $l_1$ minimization for SAR imaging with low sampling rate. Inverse Problems & Imaging, 2013, 7 (4) : 1295-1305. doi: 10.3934/ipi.2013.7.1295

[11]

Li-Xia Liu, Sanyang Liu, Chun-Feng Wang. Smoothing Newton methods for symmetric cone linear complementarity problem with the Cartesian $P$/$P_0$-property. Journal of Industrial & Management Optimization, 2011, 7 (1) : 53-66. doi: 10.3934/jimo.2011.7.53

[12]

Pierre-Étienne Druet. Higher $L^p$ regularity for vector fields that satisfy divergence and rotation constraints in dual Sobolev spaces, and application to some low-frequency Maxwell equations. Discrete & Continuous Dynamical Systems - S, 2015, 8 (3) : 475-496. doi: 10.3934/dcdss.2015.8.475

[13]

Alexander Barg, Oleg R. Musin. Codes in spherical caps. Advances in Mathematics of Communications, 2007, 1 (1) : 131-149. doi: 10.3934/amc.2007.1.131

[14]

Ryan Loxton, Qun Lin. Optimal fleet composition via dynamic programming and golden section search. Journal of Industrial & Management Optimization, 2011, 7 (4) : 875-890. doi: 10.3934/jimo.2011.7.875

[15]

Gang Bao, Jun Lai. Radar cross section reduction of a cavity in the ground plane: TE polarization. Discrete & Continuous Dynamical Systems - S, 2015, 8 (3) : 419-434. doi: 10.3934/dcdss.2015.8.419

[16]

Yanzhao Cao, Anping Liu, Zhimin Zhang. Special section on differential equations: Theory, application, and numerical approximation. Discrete & Continuous Dynamical Systems - B, 2015, 20 (5) : i-ii. doi: 10.3934/dcdsb.2015.20.5i

[17]

Umberto Martínez-Peñas. Rank equivalent and rank degenerate skew cyclic codes. Advances in Mathematics of Communications, 2017, 11 (2) : 267-282. doi: 10.3934/amc.2017018

[18]

Relinde Jurrius, Ruud Pellikaan. On defining generalized rank weights. Advances in Mathematics of Communications, 2017, 11 (1) : 225-235. doi: 10.3934/amc.2017014

[19]

Tomasz Downarowicz, Yonatan Gutman, Dawid Huczek. Rank as a function of measure. Discrete & Continuous Dynamical Systems - A, 2014, 34 (7) : 2741-2750. doi: 10.3934/dcds.2014.34.2741

[20]

Mason A. Porter, Richard L. Liboff. The radially vibrating spherical quantum billiard. Conference Publications, 2001, 2001 (Special) : 310-318. doi: 10.3934/proc.2001.2001.310

2017 Impact Factor: 0.994

Metrics

  • PDF downloads (5)
  • HTML views (45)
  • Cited by (0)

Other articles
by authors

[Back to Top]