Convergence analysis of projected gradient descent for Schatten-\(p\) nonconvex matrix recovery. (English) Zbl 1331.65183

Summary: The matrix rank minimization problem arises in many engineering applications. As this problem is NP-hard, a nonconvex relaxation of matrix rank minimization, called the Schatten-\(p\) quasi-norm minimization \((0<p<1)\), has been developed to approximate the rank function closely. We study the performance of projected gradient descent algorithm for solving the Schatten-\(p\) quasi-norm minimization \((0<p<1)\) problem. Based on the matrix restricted isometry property (M-RIP), we give the convergence guarantee and error bound for this algorithm and show that the algorithm is robust to noise with an exponential convergence rate.


65Y20 Complexity and performance of numerical algorithms
15A83 Matrix completion problems
65F99 Numerical linear algebra
90C25 Convex programming
Full Text: DOI


[1] Bahmani S, Raj B. A unifying analysis of projected gradient descent for lp-constrained least squares. Appl Comput Harmon Anal, 2013, 34: 366-378 · Zbl 1268.65054
[2] Blumensath T, Davies M. Iterative thresholding for sparse approximations. J Fourier Anal Appl, 2008, 14: 629-654 · Zbl 1175.94060
[3] Blumensath T, Davies M. Iterative hard thresholding for compressed sensing. Appl Comput Harmon Anal, 2009, 27: 265-274 · Zbl 1174.94008
[4] Cai J F, Candès E J, Shen Z W. A singular value thresholding algorithm for matrix completion. SIAM J Optim, 2010, 20: 1956-1982 · Zbl 1201.90155
[5] Cai T, Zhang A. Sharp RIP bound for sparse signal and low-rank matrix recovery. Appl Comput Harmon Anal, 2013, 35: 74-93 · Zbl 1310.94021
[6] Cai T, Zhang A. Sparse representation of a polytope and recovery of sparse signals and low-rank matrices. IEEE Trans Inform Theory, 2014, 60: 122-132 · Zbl 1364.94114
[7] Candès E J, Plan Y. Tight oracle inequalities for low-rank matrix recovery from a minimal number of noisy random measurements. IEEE Trans Inform Theory, 2011, 57: 2342-2359 · Zbl 1366.90160
[8] Candès E J, Recht B. Exact matrix completion via convex optimization. Found Comput Math, 2009, 9: 717-772 · Zbl 1219.90124
[9] Deng Y, Dai Q, Liu R, et al. Low-rank structure learning via nonconvex heuristic recovery. IEEE Trans Neural Netw Learn Syst, 2013, 24: 383-396
[10] Fazel M. Matrix rank minimization with applications. PhD thesis. Stanford: Stanford University, 2002
[11] Fornasier M, Rauhut H, Ward R. Low-rank matrix recovery via iteratively reweighted least squares minimization. SIAM J Optim, 2011, 21: 1614-1640 · Zbl 1236.65044
[12] Foucart S. Sparse recovery algorithms: Sufficient conditions in terms of restricted isometry constants. Springer Proc Math, 2012, 13: 65-77 · Zbl 1250.65057
[13] Goldfarb D, Ma S. Convergence of fixed-point continuation algorithms for matrix rank minimization. Found Comput Math, 2011, 11: 183-210 · Zbl 1219.90195
[14] Gross D. Recovery Low-rank matrices from few coefficients in any basis. IEEE Trans Inform Theory, 2011, 57: 1548-1566 · Zbl 1366.94103
[15] Gross D, Liu Y K, Flammia S T, et al. Quantum state tomography via compressed sensing. Phys Rev Lett, 2010, 105: 150401
[16] Haldar, J.; Liang, Z., Spatiotemporal imaging with partially separable functions: A matrix recovery approach, 716-719 (2010), New York
[17] Ji, H.; Liu, C.; Shen, Z. W.; etal., Robust video denoising using low rank matrix completion, 1791-1798 (2010), San Francisco, CA
[18] Kramer F, Ward R. New and improved Johnson-Lindenstrauss embeddings via the restricted isometry property. SIAM J Math Anal, 2011, 43: 1269-1281 · Zbl 1247.15019
[19] Lai M, Xu Y, Yin W. Improved iteratively reweighted least square for unconstrained smoothed lq minimization. SIAM J Numer Anal, 2013, 51: 927-957 · Zbl 1268.49038
[20] Lee K, Bresler Y. ADMiRA: Atomic decomposition for minimum rank approximation. IEEE Trans Inform Theory, 2010, 56: 4402-4416 · Zbl 1366.94112
[21] Lewis A S. The convex analysis of unitarily invariant matrix norms. J Convex Anal, 1995, 2: 173-183 · Zbl 0860.15026
[22] Lin J, Li S. Convergence of projected Landweber iteration for matrix rank minimization. Appl Comput Harmon Anal, 2014, 36: 316-325 · Zbl 1302.65144
[23] Liu L, Huang W, Chen D R. Exact minimum rank approximation via Schatten p-norm minimization. J Comput Appl Math, 2014, 267: 218-227 · Zbl 1293.65056
[24] Liu Z, Vandenberghe L. Interior-point method for nuclear norm approximation with application to system identification. SIAM J Matrix Anal Appl, 2008, 31: 1235-1256 · Zbl 1201.90151
[25] Ma S, Goldfarb D, Chen L. Fixed point and Bregman iterative methods for matrix rank minimization. Math Program, 2011, 128: 321-353 · Zbl 1221.65146
[26] Majumdar A, Ward R K. An algorithm for sparse MRI reconstruction by Schatten p-norm minimization. Magnetic Resonance Imaging, 2011, 29: 408-417
[27] Marjanovic G, Solo V. On lq Optimization and Matrix Completion. IEEE Trans Signal Process, 2012, 60: 5714-5724 · Zbl 1393.94353
[28] Mazumder R, Hastie T, Tibshirani R. Spectral regularization algorithms for learning large incomplete matrices. J Mach Learn Res, 2010, 11: 2287-2322 · Zbl 1242.68237
[29] Meka R, Jain P, Dhillon L S. Guaranteed rank minimization via singular value projection. ArXiv:0909.5457, 2009
[30] Mohan, K.; Fazel, M., Reweighted nuclear norm minimization with application to system identification, 2953-2959 (2010), Piscataway, NJ
[31] Mohan, K.; Fazel, M., Iterative reweighted least squares for matrix rank minimization, 653-661 (2010), Piscataway, NJ
[32] Needell D, Tropp J. CoSaMP: Iterative signal recovery from incomplete and inaccurate samples. Appl Comput Harmon Anal, 2009, 26: 301-321 · Zbl 1163.94003
[33] Netflix Prize [Online]. Available: http://www.netflixprize.com/. · Zbl 1273.90156
[34] Oymak, S.; Mohan, K.; Fazel, M.; etal., A simplified approach to recovery conditions for low rank matrices, 2318-2322 (2011), Piscataway, NJ
[35] Recht B, Fazel M, Parrilo P. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Rev, 2010, 52: 471-501 · Zbl 1198.90321
[36] Singer A. A remark on global positioning from local distances. Proc Natl Acad Sci USA, 2008, 105: 9507 · Zbl 1205.86043
[37] Srebro, N.; Rennie, J. F M.; Jakola, T. S., Maximum-margin matrix factorization (2005), Cambridge-Massachusetts
[38] Toh K C, Yun S W. An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems. Pac J Optim, 2010, 6: 615-640 · Zbl 1205.90218
[39] Wang H, Li S. The bounds of restricted isometry constants for low rank matrices recovery. Sci China Math, 2013, 56: 1117-1127 · Zbl 1273.90156
[40] Zhang H, Cheng L Z. Projected Landweber iteration for matrix completion. J Comput Appl Math, 2010, 235: 593-601 · Zbl 1225.65049
[41] Zhang M, Huang Z, Zhang Y. Restricted p-Isometry Properties of Nonconvex matrix recovery. IEEE Trans Inform Theory, 2013, 59: 4316-4323 · Zbl 1364.94179
[42] Zhao, B.; Haldar, J.; Brinegar, C.; etal., Low rank matrix recovery for real-time cardiac MRI, 996-999 (2010), New York
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.