Block-Coordinate Minimization for Large SDPs with Block-Diagonal Constraints

• X[i,j] denotes the (i, j)-th d×d block of a dn×dn matrix X.Source: Notations and Preliminaries · p. 1
• The Stiefel manifold St(d, r) consists of matrices Y ∈ R^{r×d} with orthonormal columns, equipped with the metric induced by its embedding.Source: Notations and Preliminaries · p. 1
• The product manifold St(d, r)^n contains concatenated blocks whose individual matrices belong to St(d, r).Source: Notations and Preliminaries · p. 1
• The Riemannian gradient is the orthogonal projection of the ambient Euclidean gradient onto the product manifold’s tangent space.Source: Notations and Preliminaries · p. 1

1 Problem Formulation

• Large-scale SDPs with identity diagonal blocks and a positive-semidefinite constraint arise as relaxations of non-convex and combinatorial problems.Source: §1 · pp. 1–2
• Applications include Max-Cut and graphical-model inference for d = 1, and pose-graph and rotation synchronization for d > 1.Pose-graph instances can have d × n well above 10^4, where interior-point methods are often impractical.Source: §1 · p. 2
• Burer and Monteiro address scale by imposing a low-rank factorization, yielding a non-convex problem equivalent to the SDP with rank(X) ≤ r.Source: §1 · p. 2
• A rank-deficient second-order critical point of the factorized problem is globally optimal and yields a globally optimal SDP solution.Source: §1 · p. 2
• The paper extends BCM and its global convergence-rate analysis from products of unit spheres to products of Stiefel manifolds St(d, r)^n for arbitrary d ≤ r.Source: §1 · p. 2

2 Algorithm

• BCM decomposes the overall cost into contributions from individual blocks and selects one block to update at each iteration.Source: §2 · p. 3
• Fixing all other blocks makes the single-block minimization over St(d, r) solvable in closed form using the SVD of −G_i.The optimal block is obtained from the singular vectors in that decomposition.Source: §2 · p. 3
• The block is sampled uniformly with p_i = 1/n or by importance with p_i proportional to ∥G_i∥_* across blocks.Source: §2 · p. 3

3 Global Convergence Analysis

• The analysis extends the sphere-product results of Erdogdu et al. to St(d, r)^n for any d ≤ r, reducing to their statements when d = 1.Source: §3 · p. 3
• BCM’s block updates produce nonincreasing cost values, with the decrease quantified using the selected block Yi and its Gi.The section also identifies the Frobenius norm of the Riemannian gradient as a quantity for the convergence analysis.Source: §3 · pp. 3–4
• Both uniform and importance sampling yield a solution with arbitrarily small gradient norm in expectation after sufficiently many iterations.The analysis generalizes the global convergence proof and rate estimates of Erdogdu et al..Source: §3 · p. 4
• For uniform sampling, the iteration threshold depends on 2dnC1(Q), the initial objective gap, and ε.Theorem 1 gives K ≥ ⌈2dnC1(Q)(F(Y0)−F⋆)/ε⌉; the supplied passage does not include the resulting gradient-norm bound.Source: §3 · p. 4
• The algorithm and analysis also extend to products with differing frame dimensions di ≤ r, with a similar sublinear rate and adjusted constants.For example, d in the constants is replaced by max_i di.Source: §3 · p. 4

Appendix A Proofs

• Each BCM iteration descends on the objective, as established by bounding the second term in the descent expression.The proof invokes the general von Neumann trace theorem for that bound.Source: Appendix A · p. 6
• The gradient-norm calculation expands the Riemannian gradient into blocks and sums their squared Frobenius norms.The derivation uses Q[i,i] = 0 to simplify a diagonal-block expression.Source: Appendix A · p. 7
• Theorem 1’s contradiction argument uses the objective’s lower bound to show that BCM returns a solution with the stated gradient criterion.The proof notes that F is continuous on the compact manifold St(d, r)^n, so F⋆ is bounded below.Source: Appendix A · pp. 8–9

Appendix B Miscellaneous Lemmas

• For a square matrix with ordered singular values, the appendix bounds sums of eigenvalue magnitudes and pairwise eigenvalue products using singular values.The inequalities are stated for sums of |λi|^p and of |λiλj|; the latter follows by applying the former to the second compound matrix.Source: Appendix B · p. 10
• The appendix proves the spectral inequalities using a singular-value inequality and the compound matrix’s eigenvalue and singular-value products.The cited result for the compound matrix gives eigenvalues λiλj and singular values σiσj.Source: Appendix B · p. 10
• Lemma 4 considers G ∈ R^{r×d} and Y ∈ St(d,r), defining σ_i(·) and λ_i(·) as the ith algebraically largest singular value and eigenvalue, respectively, for i ∈ [d].Source: Appendix B · p. 10
• The proof of Lemma 5 bounds an expression involving G and Y by invoking the earlier spectral lemmas.The supplied passage identifies Lemma 3 and Lemma 4 as sources of inequalities in that bound.Source: Appendix B · p. 11