×

zbMATH — the first resource for mathematics

Rank optimality for the Burer-Monteiro factorization. (English) Zbl 1451.90114
MSC:
90C22 Semidefinite programming
90C26 Nonconvex programming, global optimization
65K10 Numerical optimization and variational techniques
Software:
CSDP; SDPLR
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] E. Abbe, A. S. Bandeira, and G. Hall, Exact recovery in the stochastic block model, Trans. Inform. Theory, 62 (2016), pp. 471-487. · Zbl 1359.94047
[2] P.-A. Absil, R. Mahony, and R. Sepulchre, Optimization Algorithms on Matrix Manifolds, Princeton University Press, Princeton, NJ, 2009. · Zbl 1147.65043
[3] A. S. Bandeira, N. Boumal, and V. Voroninski, On the low-rank approach for semidefinite programs arising in synchronization and community detection, in Proceedings of the Conference on Computational Learning Theory, 2016. · Zbl 1445.90074
[4] S. Bhojanapalli, N. Boumal, P. Jain, and P. Netrapalli, Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form, in Proceedings of the 31st Conference on Learning Theory, 2018, pp. 3243-3270.
[5] B. Borchers and J. Young, Implementation of a primal-dual method for SDP on a shared memory parallel architecture, Comput. Optim. Appl., 37 (2007), pp. 355-369. · Zbl 1179.90256
[6] N. Boumal, A Riemannian Low-rank Method for Optimization over Semidefinite Matrices with Block-diagonal Constraints, Tech. report, http://arxiv.org/abs/1506.00575, 2015.
[7] N. Boumal, P.-A. Absil, and C. Cartis, Global rates of convergence for nonconvex optimization on manifolds, IMA J. Numer. Anal., 39 (2019), pp. 1-33. · Zbl 07208096
[8] N. Boumal, V. Voroninski, and A. S. Bandeira, Deterministic Guarantees for Burer-Monteiro Factorizations of Smooth Semidefinite Programs, preprint, https://arxiv.org/abs/1804.02008, 2018. · Zbl 1445.90074
[9] S. Burer and R. D. C. Monteiro, A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization, Math. Program., 95 (2003), pp. 329-357. · Zbl 1030.90077
[10] S. Burer and R. D. C. Monteiro, Local minima and convergence in low-rank semidefinite programming, Math. Program., 103 (2005), pp. 427-444. · Zbl 1099.90040
[11] C. Delorme and S. Poljak, Laplacian eigenvalues and the maximum cut problem, Math. Program., 62 (1993), pp. 557-574. · Zbl 0797.90107
[12] R. Ge, J. D. Lee, and T. Ma, Matrix Completion has no Spurious Local Minimum, in Advances in Neural Information Processing Systems 29, Curran Associates, 2016.
[13] M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM, 42 (1995), pp. 1115-1145. · Zbl 0885.68088
[14] M. Jaggi, Revisiting Frank-Wolfe: Projection-free sparse convex optimization, in Proceedings of the 30th International Conference on Machine Learning, 2013, pp. 427-435.
[15] M. Journée, F. Bach, P.-A. Absil, and R. Sepulchre, Low-rank optimization on the cone of positive semidefinite matrices, SIAM J. Optim., 20 (2010), pp. 2327-2351. · Zbl 1215.65108
[16] S. Laue, A hybrid algorithm for convex semidefinite optimization, in Proceedings of the 29th International Conference on Machine Learning, 2012, pp. 177-184.
[17] M. Laurent and F. Rendl, Semidefinite Programming and Integer Programming, Hand. Oper. Res. Management Sci., 12 (2005), pp. 393-514. · Zbl 1194.90066
[18] A. Lemon, A. M.-C. So, and Y. Ye, Low-rank Semidefinite Programming: Theory and Applications, Now Publishers, 2016.
[19] Q. Li, Z. Zhu, and G. Tang, The non-convex geometry of low-rank matrix optimization, Inform. Inference, 8 (2019), pp. 51-96. · Zbl 07127822
[20] Y. Nesterov, Smooth minimization of non-smooth functions, Math. Program., 103 (2005), pp. 127-152. · Zbl 1079.90102
[21] G. Pataki, On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues, Math. Oper. Res., 23 (1998), pp. 339-358. · Zbl 0977.90051
[22] S. Poljak and F. Rendl, Nonpolyhedral relaxations of graph-bisection problems, SIAM J. Optim., 5 (1995), pp. 467-487. · Zbl 0838.90130
[23] T. Pumir, S. Jelassi, and N. Boumal, Smoothed Analysis of the Low-rank Approach for Smooth Semidefinite Programs, in Advances in Neural Information Processing Systems, 2018.
[24] D. M. Rosen, L. Carlone, A. S. Bandeira, and J. J. Leonard, SE-Sync: A certifiably correct algorithm for synchronization over the special Euclidean group, to appear in Internat. J. Robotics Res., 38 (2019).
[25] J. Sun, Q. Qu, and J. Wright, A geometric analysis of phase retrieval, Found. Comput. Math., 18 (2018), pp. 1131-1198. · Zbl 1401.94049
[26] I. Waldspurger, A. d’Aspremont, and S. Mallat, Phase recovery, maxcut and complex semidefinite programming, Math. Program., 149 (2015), pp. 47-81. · Zbl 1329.94018
[27] I. Waldspurger and A. Waters, Rank Optimality for the Burer-Monteiro Factorization, preprint, https://arxiv.org/abs/1812.03046, 2018.
[28] H. Wolkowicz, R. Saigal, and L. Vandenberghe, Handbook of Semidefinite Programming: Theory, Algorithms, and Applications, Internat. Ser. Oper. Res. Management Sci. 27, Springer, New York, 2012. · Zbl 0962.90001
[29] A. Yurtsever, M. Udell, J. A. Tropp, and V. Cevher, Sketchy decisions: Convex low-rank matrix optimization with optimal storage, in Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, PMLR 54, 2017, pp. 1188-1196.
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.