PaperlayerView exact revision on arXiv

Source-linked AI summary

Distributed Certifiably Correct Pose-Graph Optimization

Yulun Tian, Kasra Khosoussi, David M. Rosen, Jonathan P. How

arXiv:1911.03721v6math.OCcs.RO

TL;DR

Distributed pose-graph optimization lacks methods that guarantee globally optimal solutions while avoiding the constraints of centralized approaches. This paper combines a sparse SDP relaxation with distributed low-rank optimization and critical-point verification. It reports recovery of globally optimal solutions under moderate noise and better estimation quality and convergence speed than alternative distributed methods.

  • Problem

    Distributed PGO methods based on local optimization do not guarantee globally optimal solutions, while centralized certifiably correct methods can be impractical to distribute.

    Source: §1 · p. 3

  • Method

    The method solves a sparse SDP relaxation through a distributed Riemannian Staircase with Riemannian block-coordinate descent and post hoc solution verification.

    Source: §3.2 · p. 10, §4.3 · p. 19, §9 · p. 34

  • Results

    The approach recovers globally optimal solutions under moderate noise and outperforms alternative distributed methods in estimation quality and convergence speed.

    Source: §9 · p. 35

  • Takeaways & Limitations

    The sparse relaxation provides a basis for distributed PGO with global-optimality guarantees under moderate measurement noise.

    Source: §9 · pp. 34–35

    RBCD and RBCD++ may not achieve SE-Sync's solution precision in tractable time because they are first-order methods and SE-Sync is second-order.

    Source: §9 · p. 34

Abstract

from arXiv · show

This paper presents the first certifiably correct algorithm for distributed pose-graph optimization (PGO), the backbone of modern collaborative simultaneous localization and mapping (CSLAM) and camera network localization (CNL) systems. Our method is based upon a sparse semidefinite relaxation that we prove provides globally-optimal PGO solutions under moderate measurement noise (matching the guarantees enjoyed by state-of-the-art centralized methods), but is amenable to distributed optimization using the low-rank Riemannian Staircase framework. To implement the Riemannian Staircase in the distributed setting, we develop Riemannian block coordinate descent (RBCD), a novel method for (locally) minimizing a function over a product of Riemannian manifolds. We also propose the first distributed solution verification and saddle escape methods to certify the global optimality of critical points recovered via RBCD, and to descend from suboptimal critical points (if necessary). All components of our approach are inherently decentralized: they require only local communication, provide privacy protection, and are easily parallelizable. Extensive evaluations on synthetic and real-world datasets demonstrate that the proposed method correctly recovers globally optimal solutions under moderate noise, and outperforms alternative distributed techniques in terms of solution precision and convergence speed.

1 Introduction

The paper introduces the first fully distributed, certifiably correct PGO algorithm to address the lack of global-optimality guarantees in distributed CSLAM. It combines a sparse semidefinite relaxation with distributed low-rank optimization, verification, and saddle escape.

1 Introduction

  • The paper proposes the first fully distributed PGO algorithm that is certifiably correct, addressing the absence of distributed methods that guarantee recovery of an optimal solution.The motivating application is collaborative mapping by teams of robots in unknown GPS-denied environments.Source: §1 · p. 3
  • The sparse SDP relaxation has the same exactness guarantees as the SE-Sync relaxation: under moderate measurement noise, its minimizers provide exact solutions to the original PGO problem.The method uses a distributed Riemannian Staircase and Riemannian block coordinate descent (RBCD) to solve low-rank subproblems.Source: §1 · p. 3
  • Distributed verification certifies whether RBCD-recovered critical points are globally optimal, and saddle escape can provide a descent direction from suboptimal critical points.The paper also describes distributed initialization and rounding procedures for producing a final PGO estimate.Source: §1 · p. 4

General Notations; Linear Algebra

  • The notation defines [n] as the index set {1, 2, . . . , n}, and introduces conventions for matrices, block indexing, and projection operators.The notation also specifies standard linear-algebra operators including block-diagonal assembly and symmetrization.Source: General Notations · p. 4, Linear Algebra · pp. 4–5

Differential Geometry of Riemannian Manifolds; Matrix submanifolds used in this work

2 Related Work

Prior centralized certifiably correct PGO methods face communication and privacy barriers, while distributed local-search methods generally lack global guarantees. The paper develops a sparse relaxation with exactness guarantees and a distributed Riemannian block-coordinate method to address these gaps.

2.1 Centralized Pose-Graph Optimization Algorithms

  • SE-Sync's dense SDP is difficult to distribute without exposing poses and requiring impractical communication, while the sparse Cartan-Sync relaxation had lacked exactness guarantees.The paper establishes correspondences between the Cartan-Sync and SE-Sync relaxations, extending the latter's exactness guarantees to the sparse relaxation.Source: §2.1 · pp. 6–7

2.2 Decentralized Pose-Graph Optimization Algorithms

  • Existing distributed PGO approaches use local search and cannot guarantee global optimality, whereas this work combines distributed search with verification and saddle escape.The method's local subproblem updates require only inexpensive approximate solutions, unlike the fully solved local subproblems described for.Source: §2.2 · p. 7

2.3 Block-Coordinate Descent Methods

  • Riemannian block-coordinate descent extends block-coordinate methods to product Riemannian manifolds, with a unified algorithm and global convergence-rate analysis.Prior block-coordinate methods could be unsuitable for large SLAM instances because they store dense matrices or require access to other agents' private poses.Source: §2.3 · p. 8

3 Certifiably Correct Pose-Graph Optimization

This section formulates collaborative pose-graph optimization and develops a sparse SDP relaxation with low-noise exactness guarantees. It then describes a distributed Riemannian Staircase and the complete algorithm for recovering and certifying PGO solutions.

3.1 Pose-Graph Optimization

  • PGO estimates unknown poses from noisy relative measurements, while collaborative PGO jointly estimates multiple robots’ trajectories in a common reference frame.Inter-robot loop closures define public poses and dependencies between robots; other poses are private.Source: §3.1 · p. 8, Collaborative PGO · p. 9, Figure 2 · p. 9

3.2 SDP Relaxation for PGO

  • The sparse SDP relaxation preserves the SE-Sync relaxation’s exactness without its generally dense cost matrix, which would make all poses public and increase communication.The relaxation lifts the pose variables into a matrix and drops non-convex rank and determinant constraints.Source: §3.2 · pp. 10–11
  • Under sufficiently low measurement noise, every minimizer of the sparse SDP relaxation yields a global minimizer of PGO, matching the exactness guarantee of the SE-Sync relaxation.The guarantee is quantified by the spectral-norm deviation of the connection Laplacian from its latent value.Source: §3.2 · p. 11

3.3 Solving the Relaxation: The Distributed Riemannian Staircase

  • The distributed Riemannian Staircase factors the SDP solution at increasing ranks and uses RBCD to find first-order critical points on a product manifold.A distributed dual-certificate check verifies optimality; a negative eigenvalue supplies a descent direction for saddle escape. RBCD provides first-order rather than second-order guarantees.Source: §3.3 · pp. 11–12
  • The staircase either terminates with an SDP minimizer or generates factors whose objective decreases toward the optimum while approximating the KKT condition.Implementations use a numerical tolerance, and real-world applications typically require only 1–3 iterations.Source: §3.3 · p. 13

3.4 The Complete Algorithm

  • DC2-PGO combines distributed initialization, the staircase, and distributed rounding to return a feasible PGO estimate and an SDP lower bound.The lower bound certifies global optimality when it equals the objective of the returned estimate.Source: §3.4 · pp. 13–14

4 Distributed Local Search via Riemannian Block-Coordinate Descent

This section develops Riemannian block-coordinate descent (RBCD) for finding first-order critical points on product matrix manifolds, including approximate trust-region updates and an accelerated variant. It also describes the accelerated method’s communication requirements and a coloring-based extension for parallel updates by non-neighboring robots.

4 Distributed Local Search via Riemannian Block-Coordinate Descent

  • RBCD targets first-order critical points on product matrix manifolds by updating one block at a time; in PGO, blocks are robots and updates use neighbors’ public variables.The selected robot solves its local problem without further communication, while robots collaboratively evaluate the total gradient norm for termination. Unlike prior BCM methods limited to spheres or Stiefel manifolds and quadratic costs, RBCD applies to matrix submanifolds and smooth costs satisfying a Lipschitz-type condition.Source: §4 · pp. 14–15

4.1 Block Selection Rules

  • RBCD selects blocks uniformly, proportional to squared block-gradient norm, or greedily by the largest squared norm; nonuniform rules require extra gradient-norm communication but yield more effective iterations.Uniform sampling can be coordinated with synchronized clocks and a common random seed; greedy selection is restricted to Gauss-Southwell because other variants require hard-to-obtain block Lipschitz constants.Source: §4.1 · pp. 15–16

4.2 Computing a Block Update

  • RBCD uses approximate trust-region block updates rather than intractable exact minimization, leveraging second-order information and accepting steps only when predicted and actual reductions agree sufficiently, ensuring descent under mild conditions.A truncated preconditioned conjugate-gradient method solves the subproblem; the default acceptance threshold is 1/4.Source: §4.2 · pp. 16–17

4.3 Accelerated Riemannian Block-Coordinate Descent

  • RBCD++ adapts ACDM through ambient-space updates and manifold projections; adaptive restart enforces sufficient descent by falling back to RBCD when needed.The underlying ACDM has an O(1/k^2) convergence rate for standard randomized coordinate descent. Adaptive restart requires aggregating cost and gradient information and may bottleneck communication; fixed-interval restart avoids this but is empirically inferior.Source: §4.3 · p. 19
  • Most accelerated RBCD operations require no communication, but robots exchange public components of Y with graph neighbors before the X update.With adaptive restart, they also communicate and aggregate global cost and gradient norms to evaluate the restart condition.Source: §4.3 · p. 20

4.4 Parallel Riemannian Block-Coordinate Descent

  • Robots can update in parallel when they share a color, provided they are not neighbors in the dependency graph and thus share no inter-robot loop closure.A coloring assigns different colors to adjacent robots; greedy algorithms can produce a (∆ + 1)-coloring, and the dependency graph’s maximum degree ∆ is often small due to sparsity.Source: §4.4 · p. 20
  • Each iteration selects a color using adapted block-selection rules, then robots of that color update their variables concurrently.The figure illustrates a 2-coloring whose aggregate blocks can contain variables from multiple robots, allowing those robots to update in parallel.Source: §4.4 · p. 20, Figure 3 · p. 20
  • The greedy coloring rule requires coordination to compute each color’s summed squared gradient norms before selecting a block.A naïve implementation floods current squared gradient norms through the network until all robots can aggregate the information for every color.Source: §4.4 · p. 20

5 Convergence Analysis for Riemannian Block-Coordinate Descent

The section establishes first-order convergence guarantees for RBCD and RBCD++ under mild conditions, including for the rank-restricted PGO subproblems. RBCD has a global sublinear rate, with a similar guarantee for RBCD++.

5 Convergence Analysis for Riemannian Block-Coordinate Descent

  • The RBCD convergence analysis assumes four mild technical conditions, including gradient and update-map properties and a lower bound on the initial trust-region radius.The analysis presents these as assumptions for its generic convergence results.Source: §5 · p. 21
  • RBCD's squared gradient norm decreases at O(1/K), and its block updates guarantee sufficient cost decrease.The decrease per update is bounded below by a constant times the squared gradient norm at the selected block.Source: §5 · p. 22
  • RBCD++ also has a global convergence guarantee, established using the same proof technique as for RBCD.The passage describes the guarantee as similar; it does not give a rate value there.Source: §5 · pp. 22–23
  • For PGO, the assumptions hold within the initial cost sublevel set, where descent keeps future iterates.Some assumptions do not hold globally because the translation search space is non-compact.Source: §5 · p. 23
  • Parallel execution can replace the rate estimate's N factor with the number of aggregate blocks, typically bounded by a small constant related to graph degree.The passage gives the maximum degree in the sparse robot-level dependency graph as an example bound.Source: §5 · p. 23

6 Distributed Verification

Distributed verification tests whether a critical point certifies a global minimizer and, if not, supplies a descent direction for continuing the Riemannian Staircase. The section develops a distributed minimum-eigenpair method and a descent procedure for suboptimal critical points.

6 Distributed Verification

  • S(X) ⪰ 0 certifies that Z = X⊤X is a global minimizer; otherwise, a negative eigenvector of S(X) yields a second-order descent direction at the lifted point.Theorem 6 uses the minimum eigenpair of the certificate matrix to distinguish these cases and support descent.Source: §6 · pp. 23–24

6.1 Distributed Minimum-eigenvalue Computation

  • Lanczos re-orthonormalization requires synchronized all-to-all communication, making it impractical when distributed communication is expensive or unreliable.The section therefore seeks alternatives requiring less coordination.Source: §6.1 · p. 25
  • Momentum lets accelerated power iteration match Lanczos’s O(1/√γ) eigengap dependence while retaining the standard power method’s communication pattern.The standard power method has O(1/γ) eigengap dependence; accelerated power iteration adds a Polyak momentum term.Source: §6.1 · p. 26
  • Algorithm 6 combines power iteration and spectral shifting to compute a minimum eigenpair of S(X) using accelerated power iterations.The method shifts S(X) to a positive semidefinite matrix whose maximum eigenvector is a minimum eigenvector of S(X).Source: §6.1 · pp. 26–27

6.2 Descent from Suboptimal Critical Points

  • A negative minimum eigenvalue identifies a suboptimal critical point, and Theorem 6 supplies a descent direction at its lifted point.Backtracking along that direction terminates finitely and returns a nonstationary point for local search at the next rank.Source: §6.2 · p. 27
  • The descent line search requires globally synchronized messages to evaluate trial objectives and gradient norms, but typically needs only a handful of lightweight iterations.The stepsize is halved until a trial point has lower objective and nonzero gradient.Source: §6.2 · p. 27

7 Distributed Initialization and Rounding

The initialization methods provide starting estimates for distributed local search, while the rounding procedure converts the low-rank solution into a feasible PGO solution. When the SDP relaxation is exact, rounding returns a global minimizer.

7.1 Distributed Initialization

  • Spanning-tree initialization is inexpensive but sensitive to noise on the selected pose-graph edges; chordal initialization is more resilient but heavier.The paper explicitly initializes translations with distributed Gauss-Seidel and caps rotation and translation initialization at 50 iterations to limit communication.Source: §7.1 · p. 28
  • Both initialization methods produce poses on the original PGO search space, which are lifted to the rank-restricted SDP space using a sampled random Stiefel point.The lifted starting point is formed as X = Y_rand T.Source: §7.1 · p. 28

7.2 Distributed Rounding

  • When the SDP relaxation is exact, distributed rounding returns a global minimizer of the original PGO problem.The procedure is described as requiring minimal computation and communication.Source: §7.2 · p. 28
  • Rounding projects rotations to SO(d) when the SDP relaxation is not exact, ensuring feasible rotations even though the projected estimates may not be globally optimal.The exact-relaxation case instead recovers globally optimal rotation and translation estimates.Source: §7.2 · p. 28
  • Figure 4 contrasts ground truth with the certified global minimizer returned by DC2-PGO in a 9-robot simulation with 125 poses per robot.Trajectories use different colors, and loop closures are dotted lines.Source: Figure 4 · p. 29

8 Experiments

The experiments evaluate distributed local search, solution verification, and the complete DC2-PGO algorithm on simulations and benchmark datasets. They report faster convergence and globally optimal solutions under tested conditions, including recovery from random initialization.

8.1 Evaluations of Distributed Local Search

  • On the 9-robot simulation, RBCD and RBCD++ outperform RGD in convergence speed and solution quality; RBCD++ reaches the global minimum with high precision in 100 iterations.Importance and greedy block selection converge faster than uniform sampling.Source: Figure 5 · p. 30, §8.1 · p. 30
  • A fixed restart period of 30 iterations performs similarly to adaptive restart; periods that are too short slow convergence, while long periods cause oscillations.The comparison tests fixed restart frequencies from every 5 to every 100 iterations.Source: Figure 6 · p. 31, §8.1 · p. 31
  • Increasing rotation noise slows RBCD and RBCD++, whereas increasing translation noise improves their convergence behavior in the 9-robot simulation.The authors conjecture that rotation noise and decreasing translation noise magnify ill-conditioning.Source: Figure 7 · p. 31, §8.1 · p. 31
  • As the simulation grows to 49 robots with 125 poses each, RBCD++ converges faster than RBCD; its optimality gap reaches 10^-5 despite a Riemannian gradient norm of 10^-2.RBCD begins to converge slowly above 16 robots.Source: §8.1 · pp. 31–32, Figure 8 · p. 32

8.2 Evaluations of Distributed Verification

  • For a global minimizer on Killian Court, accelerated power iteration is significantly faster than standard power iteration and converges nearly as fast as Lanczos.For a suboptimal critical point, the verification method needs only a direction v with vᵀS(X)v < 0 to escape.Source: Figure 9 · p. 32, §8.2 · p. 33

8.3 Evaluations of Complete Algorithm (Algorithm 2)

  • DC2-PGO verifies a global minimizer on every benchmark dataset and returns global minima, often with fewer iterations than DGS.Some objective values are slightly higher than SE-Sync because DC2-PGO uses a looser local-search convergence threshold.Source: §8.3 · pp. 33–34
  • Across the 9-robot noise tests, DC2-PGO finds global minimizers for all tested translation noise and rotation noise up to 11°.The first column of Figure 10 reports the relative suboptimality bound; zero means the relaxation is exact.Source: §8.3 · p. 33
  • From random initialization on Killian Court, verification detects the rank-3 suboptimal critical point and enables escape to the global minimizer at rank 4.The first rank-3 local search converges to a nonzero optimality gap before the algorithm escapes and descends.Source: §8.3 · p. 34

9 Conclusion

The paper concludes that its distributed PGO method recovers globally optimal solutions under moderate noise and outperforms alternative distributed methods in estimation quality and convergence speed. It identifies iteration complexity on hard instances, outlier measurements, and deteriorating network conditions as areas for future work.

9 Conclusion

  • The sparse SDP relaxation retains the exactness guarantees of centralized methods under moderate noise, while RBCD and distributed verification and saddle escape address distributed optimization.The paper notes that first-order RBCD methods may not match SE-Sync’s precision in tractable time because SE-Sync is second-order.Source: §9 · pp. 34–35
  • Extensive evaluations show globally optimal recovery under moderate noise and better estimation quality and convergence speed than alternative distributed methods.The benchmark table covers five-robot CSLAM scenarios and reports that DC2-PGO verifies its solution as the global minimizer on all datasets.Source: §9 · p. 35, Table 1 · p. 35
  • The authors identify improving iteration complexity on hard problem instances as future work.Source: §9 · p. 35
  • Future work includes certifiably correct distributed methods that handle outlier measurements in CSLAM and CNL.The cited robust approaches remain restricted to centralized settings because of high computational requirements.Source: §9 · p. 35
  • DC2-PGO is expected to perform worse as network conditions deteriorate, including with sparser topology or greater delay.Source: §9 · p. 35

A Exactness of SDP Relaxation

The appendix proves exactness of the sparse SDP relaxation by relating it to a rotation-only relaxation. The proof eliminates translations and establishes corresponding critical-point, certificate, and minimizer relations.

A Exactness of SDP Relaxation

  • A first-order critical point of the full problem induces a rotation-only critical point with the same objective value.The lemma relates the translation variables to the rotations and equates the two costs.Source: A Exactness of SDP Relaxation · pp. 42–44
  • The full and rotation-only certificate matrices are positive semidefinite together, so either relaxation's global minimizers correspond to those of the other.Source: A Exactness of SDP Relaxation · pp. 43, 45
  • The proof uses the translation-weighted graph Laplacian and relative translation measurements to separate translation and rotation variables.The cost is rewritten in terms of Euclidean translation variables and Stiefel rotation variables.Source: A Exactness of SDP Relaxation · pp. 42–43
  • For fixed rotations, translations can be analytically eliminated from the full relaxation, yielding the rotation-only rank-restricted problem.The translations satisfy a linear system, and substituting their minimizing values gives the rotation-only objective.Source: A Exactness of SDP Relaxation · p. 45

A.1 Proof of Theorem 1

The proof establishes that the full SDP relaxation and its rotation-only counterpart have optimal solutions of the same rank. It constructs each solution from the other using the correspondence between rotations and translations.

A.1 Proof of Theorem 1

  • The proof constructs a rotation-only minimizer of the same rank from any full-relaxation minimizer, and conversely constructs a full-relaxation minimizer from a rotation-only one.The construction factors the full solution, extracts its rotational components, and then combines rotations with optimal translations for the reverse direction.Source: §A.1 · p. 45

A.2 Proof of Theorem 2

The proof establishes exactness of the full SDP relaxation by transferring a low-noise condition from the rotation-only relaxation. Continuity of its cost matrix ensures that sufficiently small data perturbations preserve the condition.

A.2 Proof of Theorem 2

  • The full relaxation inherits exactness because the full and rotation-only relaxations have corresponding minimizers of the same rank.Source: §A.2 · p. 46
  • If the rotation-only cost matrix differs from its noiseless value by less than β, its SDP has a unique solution corresponding to globally optimal PGO rotations.Source: §A.2 · p. 46
  • Continuity of the rotation-only cost matrix with respect to noise ensures that sufficiently small perturbations satisfy the exactness condition.The proof relates perturbations in the original data matrix to those in the rotation-only cost matrix.Source: §A.2 · p. 47

B.1 Proof of Lemma 1

The proof establishes sufficient cost reduction for each block update using a Cauchy step, then shows that shrinking the trust-region radius makes the step acceptable even without the initial radius bound.

B.1 Proof of Lemma 1

  • In the first trust-region subproblem, the Cauchy step along the negative Riemannian gradient achieves the required cost decrement in Lemma 1, with step size αC∈[0,∆0/∥gb∥].Source: §B.1 · p. 47
  • Additional truncated conjugate-gradient iterations improve on the Cauchy step while retaining the required cost reduction.Each such iteration strictly decreases the model function, preserving the inequality used to establish the reduction.Source: §B.1 · p. 49
  • After each rejection, BlockUpdate divides the trust-region radius by four, so the Cauchy step is guaranteed to be accepted after O(log(4λ_b∥g_b∥/∆_0)) rejections.The radius then lies in [λ_b∥g_b∥, 4λ_b∥g_b∥].Source: §B.1 · p. 49

B.2 Proof of Theorem 4

The proof derives RBCD convergence rates from a per-update decrease in the global cost. It handles uniform, importance-weighted, and greedy block selection.

B.2 Proof of Theorem 4

  • Each block update decreases the global cost by at least the reduced-cost decrease for the selected block.The other blocks remain fixed, so the reduced-cost decrease equals the decrease in the global cost.Source: §B.2 · p. 49
  • Under uniform sampling, the expected cost decrease is bounded using the squared gradient norm across all variables and summed over iterations.The proof uses conditional expectations and a telescoping cost reduction.Source: §B.2 · pp. 49–50
  • Importance sampling selects each block with probability proportional to its squared gradient norm, while greedy selection chooses the block with the largest squared gradient norm.The proof applies expectation bounds for importance sampling and a deterministic telescoping argument for greedy selection.Source: §B.2 · p. 50

B.3 Proof of Theorem 5

The proof establishes descent and convergence guarantees for RBCD++ and verifies the technical conditions needed for the low-rank PGO subproblems. These conditions include pullback-gradient regularity and bounded Riemannian Hessians along the iterates.

B.3 Proof of Theorem 5

  • RBCD++ maintains a lower bound on cost reduction whether adaptive restart is triggered or not, allowing the convergence-rate proof to follow the argument for RBCD.The bound differs from the RBCD bound only in its constant.Source: §B.3 · p. 51

B.4 Convergence on Problem 4

  • For Problem 4, the proof checks the convergence assumptions, including Lipschitz-type pullback gradients and a bounded Riemannian Hessian.A sufficiently large initial trust-region radius satisfies the stated radius assumption.Source: §B.4 · p. 51

B.4.1 Verifying Assumption 1

  • The reduced block cost has Lipschitz-type gradient for pullbacks within the global cost’s sublevel set, using bounded gradients and retraction properties.Descent keeps RBCD and RBCD++ iterates in the initial sublevel set.Source: §B.4.1 · pp. 52–54

B.4.2 Verifying Assumption 3

  • The proof bounds the Riemannian Hessian along the iterates by bounding the certificate matrix within a cost sublevel set.It removes global-translation symmetry by centering translations; connectedness of the pose graph supplies the positive Laplacian eigenvalue used in the bound.Source: §B.4.2 · p. 55

C Proof of Theorem 3

The proof analyzes the distributed Riemannian Staircase through its rank sequence and certificate matrices. It establishes convergence to the optimum by treating positive-semidefinite certificates and ruling out a persistent negative eigenvalue through saddle escape.

C Proof of Theorem 3

  • When the limiting certificate matrix is positive semidefinite, monotone objective values and the correspondence with the rotation-only relaxation establish convergence to the optimal value.The proof uses compactness of the rotation-only relaxation’s feasible set to control the sequence of factors.Source: C Proof of Theorem 3 · pp. 56–57
  • The proof relates critical points of the full rank-restricted SDP to those of the rotation-only SDP to control the sequence across ranks.The rotation-only relaxation’s feasible set is compact.Source: C Proof of Theorem 3 · p. 56
  • A limiting certificate with a negative minimum eigenvalue would yield a fixed positive objective decrease at infinitely many saddle escapes, contradicting the relaxation’s finite lower bound.The proof derives a uniform escape step within the initial objective sublevel set.Source: C Proof of Theorem 3 · pp. 57–58
  • The saddle-escape descent bound uses a translation-centered parameterization, which leaves objective values and derivative norms invariant.Centering makes the subsequent bounds more convenient to calculate.Source: C Proof of Theorem 3 · p. 58

Related papers

Loading 1911.03721v6…