PaperlayerView exact revision on arXiv

Source-linked AI summary

Exact and Stable Recovery of Rotations for Robust Synchronization

Lanhui Wang, Amit Singer

arXiv:1211.2441v4cs.IT

TL;DR

Rotation synchronization estimates unknown rotations from noisy pairwise ratios, a problem used in several vision, graphics, and localization applications. The paper introduces LUD, a semidefinite-relaxed unsquared-residual method solved by ADM, and proves exact and stable recovery under complete and random graph models. Experiments report improved accuracy, while broader graph classes remain future work.

  • Problem

    Rotation synchronization must estimate unknown SO(d) rotations from noisy pairwise ratio measurements, with existing least-squares relaxations sensitive to outliers.

  • Method

    LUD minimizes unsquared residuals, applies semidefinite relaxation, and uses the alternating direction method to solve the resulting optimization problem.

  • Results

    The paper proves exact and stable recovery under stated noise conditions for complete and random measurement graphs, and reports improved estimation accuracy over EIG and SDP.

  • Takeaways & Limitations

    LUD provides a robust synchronization approach whose stability to perturbations distinguishes it from cycle-based algorithms in applications with small measurement noise.

  • Takeaways & Limitations

    The analysis covers complete and random ER measurement graphs, while exact and stable recovery for more general or weighted graphs remains future work.

Abstract

from arXiv · show

The synchronization problem over the special orthogonal group $SO(d)$ consists of estimating a set of unknown rotations $R_1,R_2,...,R_n$ from noisy measurements of a subset of their pairwise ratios $R_{i}^{-1}R_{j}$. The problem has found applications in computer vision, computer graphics, and sensor network localization, among others. Its least squares solution can be approximated by either spectral relaxation or semidefinite programming followed by a rounding procedure, analogous to the approximation algorithms of \textsc{Max-Cut}. The contribution of this paper is three-fold: First, we introduce a robust penalty function involving the sum of unsquared deviations and derive a relaxation that leads to a convex optimization problem; Second, we apply the alternating direction method to minimize the penalty function; Finally, under a specific model of the measurement noise and for both complete and random measurement graphs, we prove that the rotations are exactly and stably recovered, exhibiting a phase transition behavior in terms of the proportion of noisy measurements. Numerical simulations confirm the phase transition behavior for our method as well as its improved accuracy compared to existing methods.

1. Introduction.

Rotation synchronization estimates unknown rotations from noisy pairwise ratio measurements on a graph. The paper replaces outlier-sensitive least squares with a robust method that supports exact and stable recovery under stated conditions.

  • Synchronization estimates rotations in SO(d) from a subset of noisy measurements of pairwise ratios R_i^-1R_j.
  • The problem supports applications including ranking, image reconstruction, sensor localization, structure from motion, 3-D scan alignment, and molecular structure determination.
  • Spanning-tree recovery is unique up to a global rotation in noiseless connected graphs, but noisy ratios cause error accumulation.
  • Cycle-based methods can identify noise-free ratios under random noise, but their complexity grows exponentially with cycle length and they are unstable to small perturbations.
  • Least-squares methods use spectral or semidefinite relaxations but are sensitive to unstructured outliers.
  • The paper minimizes unsquared residuals, applies semidefinite relaxation and alternating direction optimization, and proves exact and stable recovery under stated graph and noise conditions.

2. Approximating the Least Squares Solution.

Least-squares synchronization is non-convex over SO(d), motivating spectral and semidefinite relaxations. These methods optimize matrix surrogates and recover rotations through eigenvector- or SVD-based rounding.

  • The least-squares objective minimizes weighted squared deviations between estimated rotation ratios and noisy measurements, but its feasible set SO(d)^n is non-convex.
  • Semidefinite Programming Relaxation: The semidefinite relaxation represents rotations through a Gram matrix G and relaxes rank and determinant constraints while retaining positive semidefiniteness and block-diagonal identity constraints.
  • Semidefinite Programming Relaxation: For d = 1, the relaxation reduces to the SDP for Max-Cut because synchronization over O(1) is equivalent to Max-Cut.
  • Rounding: After solving the SDP, random or deterministic rounding uses orthonormal directions or leading eigenvectors followed by SVD to estimate the rotations.
  • Spectral Relaxation: Spectral methods use the smallest-eigenvalue eigenvectors of the graph connection Laplacian, followed by SVD rounding; connectivity affects synchronization difficulty through Laplacian eigenvalues.
  • The paper motivates unsquared residuals because least-squares approaches may be suboptimal when many measurements are outliers.

3. Least Unsquared Deviation (LUD) and Semidefinite Relaxation.

LUD replaces squared residuals with unsquared residuals to reduce the influence of large outliers. Its non-convex formulation is converted into a convex semidefinite relaxation and solved using rounding procedures.

  • LUD minimizes a robust self-consistency error formed from the sum of unsquared residuals rather than squared residuals.
  • The LUD optimization is non-convex when rotation orthogonality and determinant constraints are imposed.
  • Rewriting the objective with the Gram matrix and relaxing rank and determinant constraints produces a natural convex semidefinite relaxation.
  • Once G is obtained, deterministic or random rounding procedures estimate the rotations.

4. Exact Recovery of the Gram matrix G.

The supplied passages introduce the weighted LUD setting and Gram-matrix representation used for recovery analysis, but do not state the exact-recovery conditions themselves.

  • For simplicity, the analysis considers unit weights w_ij = 1 for measured edges, while allowing a general weighted formulation.
  • The Gram matrix is formed from blocks G_ij = R_i^T R_j, encoding pairwise relationships among the unknown rotations.

4.1. Main Theorem.

Theorem 4.1 establishes a critical proportion of correct measurements above which the convex program exactly recovers the Gram matrix with high probability. The result assumes all pairwise ratios are measured under the specified random noise model and provides an explicit upper bound for the critical probability.

  • 4.1. Main Theorem.: The measurements use independent Bernoulli indicators with probability p for correct ratios and Haar-uniform random rotations for incorrect ratios.All pairwise ratios are assumed measured, and the correct-edge set follows G(n, p).
  • 4.1. Main Theorem.: An explicit upper bound pc(d) is given for the critical probability p∗c(d).The bound depends on dimension through constants c(d) and c1(d).
  • 4.1. Main Theorem.: The optimization program exactly recovers the Gram matrix G with high probability when p exceeds a critical probability p∗c(d).The probability tends to 1 as n →∞.
  • 4.1. Main Theorem.: For d = 1, the analogous sign-recovery threshold has pc(1) = 0 when the proportion of correct measurements exceeds 1/2.This special case concerns the orthogonal-group analogue and is described as trivial for SO(1).
  • 4.1. Main Theorem.: The proof reduces arbitrary rotations to the identity case and analyzes perturbations of the corresponding Gram matrix.The reduction uses a bijection preserving feasibility and objective value.

4.2. Proof of Theorem 4.1.

The proof compares objective-function gains from incorrect measurements with losses from correct measurements. A perturbation decomposition and concentration bounds show that, above the threshold p > 1/2 in the stated argument, the loss dominates with high probability.

  • 4.2. Proof of Theorem 4.1.: The proof decomposes each feasible perturbation into components across S ⊗ S, S ⊗ S̄, S̄ ⊗ S, and S̄ ⊗ S̄.The subspace S contains vectors whose d-sized blocks are identical, while S̄ is its orthogonal complement.
  • 4.2. Proof of Theorem 4.1.: Correct measurements generate a loss through diagonal and off-diagonal perturbation components, which counterbalance gains from incorrect edges.The proof separately tracks these contributions before combining the bounds.
  • 4.2. Proof of Theorem 4.1.: The matrix T in the S̄ ⊗ S̄ component is positive semidefinite, enabling trace-based bounds on its contribution.The argument follows from positive semidefiniteness of G + ∆ and orthogonality to S.
  • 4.2. Proof of Theorem 4.1.: Incorrect measurements contribute a gain that is bounded using the trace of T, norms of Q1, and concentration properties of random matrices.The proof also invokes Cauchy-Schwarz and Wigner-type spectral bounds.
  • 4.2. Proof of Theorem 4.1.: When p > 1/2, combining the gain and loss bounds yields the condition needed for the correct Gram matrix to minimize the objective with high probability.The final argument uses the preceding inequalities and an explicit dimension-dependent threshold bound.

5. Stability of LUD.

The stability analysis allows small perturbations on measurements that would otherwise be correct. Above a critical probability, the recovered Gram matrix remains close to the true one, with both weak and strong stability results.

  • 5. Stability of LUD.: The analysis models good measurements as perturbations of true ratios and retains the random-noise model on incorrect measurements.The gain from incorrect measurements is unchanged, while the loss from good measurements is modified.
  • 5. Stability of LUD.: The stability analysis also applies to bounded deterministic perturbations, not only random noise.This extends the stated scope of the perturbation model.
  • 5. Stability of LUD.: Under small perturbations of the good measurements, the solution Ĝ remains close to the true Gram matrix G when p exceeds a critical probability p∗c(d).The weak-stability theorem assumes a fixed small perturbation level ϵ > 0.
  • 5. Stability of LUD.: The weaker stability result requires ϵ ≫ 1/√n, whereas stronger analysis allows ϵ → 0 as n →∞.The strong-stability proof uses ideas similar to those in the exact-recovery analysis.
  • 5. Stability of LUD.: Strong stability permits arbitrary small ϵ > 0 while retaining closeness of Ĝ to G above a critical probability p∗c(d).The critical probability is tied to the same dimension-dependent quantity c(d) defined earlier.

6. A Generalization of LUD to random incomplete measurement graphs.

The paper extends exact and stable LUD recovery guarantees from complete measurements to random incomplete measurement graphs. Under Erdős-Rényi sampling, recovery exhibits critical measurement-noise probabilities for exact and stable estimation.

  • Random incomplete measurement graphs: The measured-edge graph is modeled as an Erdős-Rényi graph G(n, p1), with p1 ≥ 2 log(n)/n, and measurements follow the paper’s exact- or stable-recovery noise models.The good and bad edge sets are themselves modeled as Erdős-Rényi graphs with probabilities p1(1−p) and p1p, respectively.
  • Generalization: The incomplete-graph analysis generalizes the full-measurement exact and stable recovery arguments to random measurement graphs.The associated numerical results are reported separately in Section 8.2.
  • Exact recovery: Above a critical noise probability p∗c(d, p1), the Gram matrix G is exactly recovered with high probability as n →∞.The theorem provides an upper bound pc(d, p1) for the critical probability, with the complete-graph case satisfying pc(d, 1) = pc(d).
  • Weak stability: Under the weak-stability noise model, the recovered Gram matrix is close to the true Gram matrix when p exceeds p∗c(d, p1), with high probability.The critical probability again admits the upper bound pc(d, p1).
  • Strong stability: Under the strong-stability model and condition (5.2), the recovered solution is close to the true Gram matrix above a critical probability p∗c(d, p1).This result applies for an arbitrarily small ϵ > 0 and also uses the bound pc(d, p1) from (6.1).

7. Alternating Direction Augmented Lagrangian method (ADM).

The paper solves the nonsmooth convex optimization problem using an alternating direction method that updates dual and primal variables sequentially. Its implementation exploits the low-rank structure of the Gram matrix, while noisy cases may require more eigenvectors.

  • Dual derivation: The dual subproblems arise after separating minimization over G and each Xij, with dual feasibility enforcing Q(θ) + W + A∗(y) = 0.The Xij minimization also imposes the condition ∥θij∥ ≤ 1.
  • ADM formulation: ADM minimizes the dual augmented Lagrangian by alternating over the Lagrange multipliers, dual slack variables, and primal variables.The variables are updated sequentially while the others remain fixed during each subproblem.
  • Iteration: Each ADM iteration solves three subproblems sequentially and updates the Lagrange multiplier using an appropriately chosen step length.The method is described as a multiple-splitting algorithm for the augmented Lagrangian.
  • Computational considerations: ADM requires O(1/δ) iterations to reach δ accuracy, and eigenvalue decomposition is the most time-consuming step per iteration.The implementation uses Arnoldi iterations to compute the first few negative eigenvectors of Wk.
  • Computational considerations: In the noiseless setting, complementary slackness and rank(G) = d allow the eigenvalue computation to focus on negative eigenvectors of Wk.For noisy data, G may have rank greater than d and Wk may consequently have more than d negative eigenvalues.
  • Experiments: Numerical experiments simulate 100, 500, and 1000 rotations in SO(2) and SO(3) under random-graph and small-perturbation noise models.The experiments were run on two Intel Xeon X5570 CPUs, each with four cores at 2.93 GHz.

8. Numerical experiments.

The experiments evaluate LUD against EIG and SDP on synthetic complete and incomplete graphs, then test it on the Lucy 3D-scan dataset. Across synthetic settings, LUD achieves exact recovery, stability to perturbations, and higher rotation-recovery accuracy, while the real-data results show similar MSE but more concentrated residuals and more robust edge filtering.

  • Experimental setup: Experiments compare LUD with EIG and SDP using relative error and MSE over repeated trials.For each fixed d, n, p, and κ, 10 trials are run and mean relative errors and MSEs are recorded.
  • E1: Exact Recovery by LUD: When n is large, exact Gram-matrix recovery occurs near critical probabilities pc(2) ≈ 0.4570 and pc(3) ≈ 0.4912.These values are reported for SO(2) and SO(3) under the E1 noise model.
  • Experiments with incomplete measurements: On Erdős–Rényi incomplete measurement graphs, experiments demonstrate exact recovery and stability for LUD.The experiments vary the measured-edge probability p1 and good-edge probability p, using n = 500 rotations.
  • E5: Real data experiments: On the Lucy dataset, LUD and EIG have similar MSEs, but LUD yields more concentrated residuals and retains 1527 of 2006 edges versus 1040 for EIG.The largest connected components after filtering contain 312 scans for LUD and 299 for EIG.

9. Summary.

The paper contrasts cycle-based recovery with LUD, emphasizing LUD’s stability to small perturbations despite less favorable exact-recovery thresholds. It also identifies extensions and related robust estimation approaches.

  • 9. Summary.: The paper generalizes its theoretical analysis to incomplete measurement ratios drawn from an Erdős–Rényi random graph G(n, p1).The supplied passage identifies the random-graph setting but does not state the associated recovery bound.
  • 9. Summary.: Cycle-based methods can outperform LUD in critical probability for short cycles, but their computational cost grows exponentially with cycle length.For triangles, the critical probability is O(1/√n); longer cycles yield O(1/n^(1−ε)) for any ε > 0).
  • 9. Summary.: LUD is stable to small perturbations on good edges, whereas cycle-based algorithms are unstable under such noise.This stability is presented as LUD’s practical advantage when measurements contain small errors.
  • 9. Summary.: The authors plan to extend LUD to more general and possibly weighted measurement graphs beyond complete and random Erdős–Rényi graphs.They speculate that the second eigenvalue of the graph Laplacian may enter exact and stable recovery conditions.
  • 9. Summary.: The LUD framework can also be extended to a robust orthogonal Procrustes problem using a least-unsquared-deviations fit.The supplied passage describes this extension as straightforward, while noting that closed-form Procrustes solutions are available only for n = 2.

Appendix A. The value of c (d). Now let us study the constant c(d) such

The appendix analyzes the constant c(d) using the symmetry of the uniform distribution on SO(d), the Weyl integration formula, and bounds based on trace properties. It treats low-dimensional cases explicitly and studies limiting behavior as d grows.

  • Symmetry and integration: The function Tr(Id − R) is invariant under conjugation, so it is a class function on SO(d).This invariance follows from the trace and supports integration over the rotation group by conjugacy classes.
  • Low-dimensional evaluation: For d = 2 or 3, corresponding to m = 1, c(d) is computed using the Weyl integration formula.The calculation uses the rotation-group integral for the relevant function f(R).
  • Bounds: Concavity of the square-root function provides bounds on c(d) through inequalities involving Tr(Id − R).The derivation also uses the symmetry of Haar measure, including E[Tr(R)] = 0.
  • Bounds: The upper bound for c(d) is very close to c(d) for d = 2, 3, and 4.The appendix explicitly highlights the tightness of this upper bound in these dimensions.
  • Large-dimensional behavior: As d approaches infinity, the trace of a uniformly sampled rotation has limiting mean 0 and variance 1, which supports asymptotic control of c(d).This conclusion uses the convergence of trace moments to those of a standard normal variable and Chebyshev's inequality.
Loading 1211.2441v4…