×

zbMATH — the first resource for mathematics

Matrix optimization over low-rank spectral sets: stationary points and local and global minimizers. (English) Zbl 1432.90124
Summary: In this paper, we consider matrix optimization with the variable as a matrix that is constrained into a low-rank spectral set, where the low-rank spectral set is the intersection of a low-rank set and a spectral set. Three typical spectral sets are considered, yielding three low-rank spectral sets. For each low-rank spectral set, we first calculate the projection of a given point onto this set and the formula of its normal cone, based on which the induced stationary points of matrix optimization over low-rank spectral sets are then investigated. Finally, we reveal the relationship between each stationary point and each local/global minimizer.
MSC:
90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming
90C46 Optimality conditions and duality in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Recht, B.; Fazel, M.; Parrilo, Pa, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev., 52, 3, 471-501 (2010) · Zbl 1198.90321
[2] Markovsky, I., Low Rank Approximation (2012), London: Springer, London · Zbl 1245.93005
[3] Ding, C.: An introduction to a class of matrix optimization problems. Ph.D. thesis, National University of Singapore (2012)
[4] Udell, M.; Horn, C.; Zadeh, Rb; Boyd, Sp, Generalized low rank models, Mach. Learn., 9, 1, 1-118 (2016) · Zbl 1350.68221
[5] Davenport, Ma; Romberg, J., An overview of low-rank matrix recovery from incomplete observations, IEEE J. Sel. Top. Signal Process., 10, 4, 608-622 (2016)
[6] Fazel, M.: Matrix rank minimization with applications. Ph.D. thesis, Stanford University (2002)
[7] Candès, Ej; Tao, T., The power of convex relaxation: near-optimal matrix completion, IEEE Trans. Inf. Theory, 56, 5, 2053-2080 (2010) · Zbl 1366.15021
[8] Marjanovic, G.; Solo, V., On \(l_q\) optimization and matrix completion, IEEE Trans. Signal Process., 60, 11, 5714-5724 (2012) · Zbl 1393.94353
[9] Mohan, K.; Fazel, M., Iterative reweighted algorithms for matrix rank minimization, J. Mach. Learn. Res., 13, Nov, 3441-3473 (2012) · Zbl 1436.65055
[10] Nie, F., Wang, H., Cai, X., Huang, H., Ding, C.: Robust matrix completion via joint schatten p-norm and \(l_p\)-norm minimization. In: IEEE International Conference on Data Mining, pp. 566-574 (2012)
[11] Chen, Y.; Xiu, N.; Peng, D., Global solutions of non-lipschitz \(s_2-s_p\) minimization over the positive semidefinite cone, Optim. Lett., 8, 7, 2053-2064 (2014) · Zbl 1326.90063
[12] Zhao, Yb, An approximation theory of matrix rank minimization and its application to quadratic equations, Linear Algebra Appl., 437, 1, 77-93 (2012) · Zbl 1242.65086
[13] Yao, H.; Debing, Z.; Jieping, Y.; Xuelong, L.; Xiaofei, H., Fast and accurate matrix completion via truncated nuclear norm regularization, IEEE Trans. Pattern Anal. Mach. Intell., 35, 9, 2117-2130 (2013)
[14] Burer, S.; Monteiro, Rdc, A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization, Math. Program., 95, 2, 329-357 (2003) · Zbl 1030.90077
[15] Journée, M.; Bach, F.; Absil, Pa; Sepulchre, R., Low-rank optimization on the cone of positive semidefinite matrices, SIAM J. Optim., 20, 5, 2327-2351 (2010) · Zbl 1215.65108
[16] Wen, Z.; Yin, W.; Zhang, Y., Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm, Math. Program. Comput., 4, 4, 333-361 (2012) · Zbl 1271.65083
[17] Jain, P., Netrapalli, P., Sanghavi, S.: Low-rank matrix completion using alternating minimization. In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pp. 665-674. ACM (2013) · Zbl 1293.65073
[18] Hardt, M.: Understanding alternating minimization for matrix completion. In: 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS), pp. 651-660. IEEE (2014)
[19] Sun, R.; Luo, Z., Guaranteed matrix completion via non-convex factorization, IEEE Trans. Inf. Theory, 62, 11, 6535-6579 (2016) · Zbl 1359.94179
[20] Gao, Y.: Structured low rank matrix optimization problems: A penalty approach. Ph.D. thesis, National University of Singapore (2010)
[21] Kim, Sj; Moon, Yh, Structurally constrained \({H}_2\) and \({H}_{\infty }\) control: a rank-constrained LMI approach, Automatica, 42, 9, 1583-1588 (2006) · Zbl 1128.93325
[22] Delgado, Ra; Agüero, Jc; Goodwin, Gc, A rank-constrained optimization approach: application to factor analysis, IFAC Proc. Vol., 47, 3, 10373-10378 (2014)
[23] Bi, S.; Pan, S., Error bounds for rank constrained optimization problems and applications, Oper. Res. Lett., 44, 3, 336-341 (2016) · Zbl 1408.90279
[24] Zhou, S.; Xiu, N.; Qi, H., A fast matrix majorization-projection method for penalized stress minimization with box constraints, IEEE Trans. Signal Process., 66, 16, 4331-4346 (2018) · Zbl 1414.90260
[25] Luke, Dr, Prox-regularity of rank constraint sets and implications for algorithms, J. Math. Imaging Vis., 47, 3, 231-238 (2013) · Zbl 1311.90142
[26] Rockafellar, Rt; Wets, Rj, Variational Analysis (1998), Berlin: Springer, Berlin
[27] Cason, Tp; Absil, Pa; Dooren, Pv, Iterative methods for low rank approximation of graph similarity matrices, Linear Algebra Appl., 438, 4, 1863-1882 (2013) · Zbl 1264.65060
[28] Schneider, R.; Uschmajew, A., Convergence results for projected line-search methods on varieties of low-rank matrices via łojasiewicz inequality, SIAM J. Optim., 25, 1, 622-646 (2015) · Zbl 1355.65079
[29] Zhou, G.; Huang, W.; Gallivan, Ka; Van Dooren, P.; Absil, Pa, A Riemannian rank-adaptive method for low-rank optimization, Neurocomputing, 192, 72-80 (2016)
[30] Li, X.; Song, W.; Xiu, N., Optimality conditions for rank-constrained matrix optimization, J. Oper. Res. Soc. China, 7, 2, 285-301 (2019) · Zbl 1438.90272
[31] Linial, N.; London, E.; Rabinovich, Y., The geometry of graphs and some of its algorithmic applications, Combinatorica, 15, 2, 215-245 (1995) · Zbl 0827.05021
[32] Biswas, P., Ye, Y.: Semidefinite programming for ad hoc wireless sensor network localization. In: International Symposium on Information Processing in Sensor Networks (2004) · Zbl 1100.90029
[33] Ji, S., Sze, K.F., Zhou, Z., So, M.C., Ye, Y.: Beyond convex relaxation: a polynomial-time non-convex optimization approach to network localization. In: IEEE Infocom (2013)
[34] Borsdorf, R.; Higham, Nj; Raydan, M., Computing a nearest correlation matrix with factor structure, SIAM J. Matrix Anal. Appl., 31, 5, 2603-2622 (2010) · Zbl 1213.65022
[35] Higham, Nj, Computing the nearest correlation matrix a problem from finance, IMA J. Numer. Anal., 22, 3, 329-343 (2018) · Zbl 1006.65036
[36] Dukanovic, I.; Rendl, F., Semidefinite programming relaxations for graph coloring and maximal clique problems, Math. Program., 109, 2-3, 345-365 (2007) · Zbl 1278.90299
[37] Kalev, A.; Kosut, Rl; Deutsch, Ih, Quantum tomography protocols with positivity are compressed sensing protocols, Nat. Partn. J. Quantum Inf., 1, 1, 15018 (2015)
[38] Lewis, As, Group invariance and convex matrix analysis, SIAM J. Matrix Anal. Appl., 17, 4, 927-949 (1996) · Zbl 0876.15016
[39] Tam, Mk, Regularity properties of non-negative sparsity sets, J. Math. Anal. Appl., 447, 2, 758-777 (2017) · Zbl 1353.15030
[40] Lu, Z.; Zhang, Y.; Li, X., Penalty decomposition methods for rank minimization, Optim. Methods Softw., 30, 3, 531-558 (2015) · Zbl 1323.65070
[41] Kyrillidis, A.: Rigorous optimization recipes for sparse and low rank inverse problems with applications in data sciences. Ph.D. thesis, École Polytechnique Fédérale de Lausanne (2014)
[42] Mordukhovich, Bs, Variational Analysis and Generalized Differentiation I: Basic Theory (2006), Berlin: Springer, Berlin
[43] Hiriart-Urruty, Jb; Lemaréchal, C., Fundamentals of Convex Analysis (2012), Berlin: Springer, Berlin
[44] Drusvyatskiy, D.; Kempton, C., Variational analysis of spectral functions simplified, J. Convex Anal., 25, 1, 119-134 (2018) · Zbl 1398.49012
[45] Lu, Z.: Optimization over sparse symmetric sets via a nonmonotone projected gradient method (2015). arXiv preprint arXiv:1509.08581
[46] Pan, L.; Xiu, N.; Fan, J., Optimality conditions for sparse nonlinear programming, Sci. China Math., 60, 5, 1-18 (2017) · Zbl 1365.90220
[47] Beck, A.; Eldar, Yc, Sparsity constrained nonlinear optimization: optimality conditions and algorithms, SIAM J. Optim., 23, 3, 1480-1509 (2013) · Zbl 1295.90051
[48] Horn, Ra; Johnson, Cr, Matrix Analysis (2013), New York: Cambridge University Press, New York
[49] Pan, L.; Zhou, S.; Xiu, N.; Qi, Hd, A convergent iterative hard thresholding for nonnegative sparsity optimization, Pac. J. Optim., 13, 2, 325-353 (2017) · Zbl 1384.90078
[50] Bertsekas, Dp, Nonlinear Programming (1999), Belmont: Athena Scientific, Belmont
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.