English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Semidefinite programming (SDP) with diagonal constraints arise in manyoptimization problems, such as Max-Cut, community detection and groupsynchronization. Although SDPs can be solved to arbitrary precision inpolynomial time, generic convex solvers do not scale well with the dimension ofthe problem. In order to address this issue, Burer and Monteiro proposed toreduce the dimension of the problem by appealing to a low-rank factorizationand solve the subsequent non-convex problem instead. In this paper, we presentcoordinate ascent based methods to solve this non-convex problem with provableconvergence guarantees. More specifically, we prove that the block-coordinatemaximization algorithm applied to the non-convex Burer-Monteiro method globallyconverges to a first-order stationary point with a sublinear rate without anyassumptions on the problem. We further show that this algorithm convergeslinearly around a local maximum provided that the objective function exhibitsquadratic decay. We establish that this condition generically holds when therank of the factorization is sufficiently large. Furthermore, incorporatingLanczos method to the block-coordinate maximization, we propose an algorithmthat is guaranteed to return a solution that provides $1-O(1/r)$ approximationto the original SDP without any assumptions, where $r$ is the rank of thefactorization. This approximation ratio is known to be optimal (up toconstants) under the unique games conjecture, and we can explicitly quantifythe number of iterations to obtain such a solution.

Convergence Rate of Block-Coordinate Maximization Burer-Monteiro Method for Solving Large SDPs