2019/12/31 by Alp Yurtsever, Joel A. Tropp, Olivier Fercoq +2 · 1 citation
Mathematics · #math.OC #math.CO #msc:90C22 #msc:65K05 #msc:65F99
paper · pdf · doi:10.1137/19m1305045
published as SIAM Journal on Mathematics of Data Science, vol. 3, num. 1, pp. 171-200, Feb. 2021
arxiv created 2021/03/25 · arxiv updated 2021/03/26
Semidefinite programming (SDP) is a powerful framework from convex optimization that has striking potential for data science applications. This paper develops a provably correct randomized algorithm for solving large, weakly constrained SDP problems by economizing on the storage and arithmetic costs. Numerical evidence shows that the method is effective for a range of applications, including relaxations of MaxCut, abstract phase retrieval, and quadratic assignment. Running on a laptop equivalent, the algorithm can handle SDP instances where the matrix variable has over 1014 entries.