pith. sign in

arxiv: 1907.07729 · v1 · pith:64B7U6DTnew · submitted 2019-07-17 · 🧮 math.OC

Convergence Analysis of Nonconvex ADMM for Rigid Registration

Aditya V. Singh , Kunal N. Chaudhury This is my paper

Pith reviewed 2026-05-24 20:06 UTC · model grok-4.3

classification 🧮 math.OC
keywords rigid registrationADMMsemidefinite programmingconvergence analysisnonconvex optimizationpoint set registrationKKT conditions
0
0 comments X

The pith

Any fixed point of REG-ADMM is a KKT point of the rank-constrained SDP for rigid registration, and an explicit ADMM parameter guarantees global convergence on clean data.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper analyzes convergence of REG-ADMM, an iterative solver obtained by applying the alternating direction method of multipliers to the rank-constrained semidefinite program that formulates least-squares rigid registration of multiple point sets. It shows that fixed points of the algorithm satisfy the KKT conditions of the SDP. For noise-free measurements the authors supply a closed-form choice of the penalty parameter ρ that forces convergence to the global optimum from any initialization, provided the underlying SDP relaxation is tight. The analysis further describes local convergence under low noise when initialized near the solution and instability under high noise when ρ falls below a threshold.

Core claim

Any fixed point of REG-ADMM is a stationary (KKT) point of REG-SDP. For clean measurements an explicit formula for the ADMM parameter ρ guarantees that REG-ADMM converges to the global optimum with arbitrary initialization, provided the convex relaxation is tight. When noise is low the iterates still reach the global optimum if started sufficiently close to it; when noise is high the method becomes unstable for ρ below a certain threshold regardless of initialization.

What carries the argument

REG-ADMM, the ADMM iteration applied to the rank-constrained SDP (REG-SDP) for rigid registration, whose fixed-point and convergence properties are derived by invoking tightness of the SDP relaxation.

If this is right

  • Fixed points of the algorithm are guaranteed to be stationary points of the original optimization problem.
  • For exact data the algorithm reaches the true registration from any starting point when ρ is set to the given formula.
  • Under low noise, convergence to the global solution occurs whenever the iterates begin near the optimum.
  • Under high noise the algorithm diverges whenever ρ is chosen below the identified threshold.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The explicit ρ formula may be used directly to stabilize the solver on data sets whose noise level is known to be small.
  • The same tightness-based argument could be tested on other registration or localization problems whose SDP relaxations are already known to be tight.
  • Monitoring the value of ρ relative to the noise level offers a practical safeguard against divergence in real deployments.

Load-bearing premise

The SDP relaxation of the registration problem must be tight, so that its solution already satisfies the rank constraint.

What would settle it

An instance of clean measurements in which REG-ADMM with the stated explicit ρ either fails to converge or converges to a point that is not the global optimum of REG-SDP.

Figures

Figures reproduced from arXiv: 1907.07729 by Aditya V. Singh, Kunal N. Chaudhury.

Figure 1
Figure 1. Figure 1: A simple registration scenario. (a) Ground truth network, where x¯1,...,x¯5 are the true global coordinates. (b) Three local coordinate systems (patches), where xk,i is the coordinate of the k-th node in the patch Pi . (c) Registered network. Note that the registered and the ground-truth networks are related by a global rigid transform, which is the best we can do with the given data. matrix composed of M … view at source ↗
Figure 2
Figure 2. Figure 2: Convergence behavior of REG-ADMM at different noise levels in the data [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Phase transition for C-SDP. The plot shows the rank of the global optimum [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
read the original abstract

We consider the problem of rigid registration, where we wish to jointly register multiple point sets via rigid transforms. This arises in applications such as sensor network localization, multiview registration, and protein structure determination. The least-squares estimator for this problem can be reduced to a rank-constrained semidefinite program (REG-SDP). It was recently shown that by formally applying the alternating direction method of multipliers (ADMM), we can derive an iterative solver (REG-ADMM) for REG-SDP, wherein each subproblem admits a simple closed-form solution. The empirical success of REG-ADMM has been demonstrated for multiview registration. However, its convergence does not follow from the existing literature on nonconvex ADMM. In this work, we study the convergence of REG-ADMM and our main findings are as follows. We prove that any fixed point of REG-ADMM is a stationary (KKT) point of REG-SDP. Moreover, for clean measurements, we give an explicit formula for the ADMM parameter $\rho$, for which REG-ADMM is guaranteed to converge to the global optimum (with arbitrary initialization). If the noise is low, we can still show that the iterates converge to the global optimum, provided they are initialized sufficiently close to the optimum. On the other hand, if the noise is high, we explain why REG-ADMM becomes unstable if $\rho$ is less than some threshold, irrespective of the initialization. We present simulation results to support our theoretical predictions. The novelty of our analysis lies in the fact that we exploit the notion of tightness of convex relaxation to arrive at our convergence results.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper analyzes convergence of REG-ADMM, a nonconvex ADMM algorithm derived from the rank-constrained SDP (REG-SDP) formulation of rigid registration of multiple point sets. It claims to prove that any fixed point of REG-ADMM is a KKT point of REG-SDP, supplies an explicit formula for the penalty parameter ρ guaranteeing global convergence to the optimum of the original problem for clean measurements from arbitrary initialization, shows local convergence under low noise when initialized near the optimum, and explains instability for high noise when ρ falls below a threshold. The analysis exploits tightness of the SDP relaxation.

Significance. If the central claims hold, the work supplies the first convergence theory for this empirically effective solver in multiview registration and related applications, with an explicit, initialization-independent parameter choice for the clean-data case. The use of tightness to obtain global optimality guarantees is a potentially reusable technique for nonconvex ADMM on other SDP relaxations.

major comments (2)
  1. [Abstract] Abstract and novelty paragraph: the guarantee that the explicit ρ yields convergence to the global optimum of the rank-constrained registration problem for clean measurements is obtained by invoking tightness of REG-SDP (i.e., that its solution is already rank-1). No derivation or citation is supplied showing that tightness holds for the clean-measurement instances under this specific ρ; without that step the global-optimality claim does not follow from the fixed-point-to-KKT result.
  2. [Convergence analysis] The section stating the fixed-point-to-KKT theorem: the manuscript asserts that any fixed point of REG-ADMM is a stationary point of REG-SDP, yet supplies no derivation steps, no explicit KKT conditions, and no verification that the ADMM updates satisfy the required stationarity conditions; this is load-bearing for both the clean-data and noisy-data claims.
minor comments (2)
  1. [Simulations] The simulation section should report the number of Monte-Carlo trials, the precise noise model, and error-bar statistics so that the empirical support for the theoretical predictions can be assessed.
  2. [Preliminaries] Notation for the registration problem and the SDP variables should be introduced once in a dedicated preliminaries section rather than piecemeal.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. The points raised highlight areas where the manuscript can be strengthened by adding missing details on tightness and the KKT derivation. We address each major comment below and will revise the manuscript to incorporate the requested clarifications.

read point-by-point responses

  1. Referee: [Abstract] Abstract and novelty paragraph: the guarantee that the explicit ρ yields convergence to the global optimum of the rank-constrained registration problem for clean measurements is obtained by invoking tightness of REG-SDP (i.e., that its solution is already rank-1). No derivation or citation is supplied showing that tightness holds for the clean-measurement instances under this specific ρ; without that step the global-optimality claim does not follow from the fixed-point-to-KKT result.

    Authors: We agree that the global-optimality claim for clean measurements relies on tightness of REG-SDP and that the manuscript does not supply an explicit derivation or citation for why tightness holds under the given ρ. In the revised version we will add either a reference to prior results establishing tightness of the SDP relaxation for clean rigid-registration instances or a short self-contained argument (in an appendix) showing that the relaxation remains tight for the clean case with the stated ρ. This addition will make the logical step from the fixed-point result to global optimality fully rigorous. revision: yes

  2. Referee: [Convergence analysis] The section stating the fixed-point-to-KKT theorem: the manuscript asserts that any fixed point of REG-ADMM is a stationary point of REG-SDP, yet supplies no derivation steps, no explicit KKT conditions, and no verification that the ADMM updates satisfy the required stationarity conditions; this is load-bearing for both the clean-data and noisy-data claims.

    Authors: We concur that the fixed-point-to-KKT theorem is central and that the current text states the result without supplying the explicit KKT conditions or the verification that the ADMM fixed-point equations imply stationarity. In the revision we will expand the relevant section to (i) state the full set of KKT conditions for REG-SDP, (ii) derive the stationarity conditions implied by the ADMM updates at a fixed point, and (iii) show the equivalence step by step. This will render the argument self-contained and directly address the load-bearing nature of the claim. revision: yes

Circularity Check

0 steps flagged

No significant circularity; claims rest on external tightness property

full rationale

The paper derives that any fixed point of REG-ADMM is a KKT point of REG-SDP via direct analysis of the algorithm iterates. The stronger global-optimum convergence claim for clean data is explicitly conditioned on the tightness of the REG-SDP relaxation (rank-1 attainment), which is invoked as a known external property rather than derived or fitted from the ADMM steps inside this manuscript. The derivation of REG-ADMM itself is referenced to prior work, but the new convergence results do not reduce to self-definition, fitted inputs called predictions, or a load-bearing self-citation chain that is unverified within the given text. The analysis remains self-contained against the stated assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central convergence claims rest on the domain assumption that the convex relaxation of REG-SDP is tight; no free parameters or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption Tightness of the convex relaxation for the rank-constrained SDP (REG-SDP)
    Explicitly cited in the abstract as the key device that enables the convergence results.

pith-pipeline@v0.9.0 · 5822 in / 1187 out tokens · 21081 ms · 2026-05-24T20:06:39.120530+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages

  1. [1]

    Princeton University Press

    Absil PA, Mahony R, Sepulchre R (2009) Optimization Algorithms on Matrix Manifolds. Princeton University Press

    work page 2009

  2. [2]

    Mathematical Programming 77(1):111–128

    Alizadeh F, Haeberly JPA, Overton ML (1997) Complementarity and nondegen- eracy in semidefinite programming. Mathematical Programming 77(1):111–128

    work page 1997

  3. [3]

    Mathematical Programming 163(1-2):145–167

    Bandeira AS, Boumal N, Singer A (2017) Tightness of the maximum likelihood semidefinite relaxation for angular synchronization. Mathematical Programming 163(1-2):145–167

    work page 2017

  4. [4]

    Athena Scientific Belmont

    Bertsekas DP (1999) Nonlinear Programming. Athena Scientific Belmont

    work page 1999

  5. [5]

    Springer Science & Business Media

    Bhatia R (2013) Matrix Analysis, vol 169. Springer Science & Business Media

    work page 2013

  6. [6]

    IEEE transactions on automation science and engineering 3(4):360–371

    Biswas P, Liang TC, Toh KC, Ye Y , Wang TC (2006) Semidefinite programming approaches for sensor network localization with noisy distance measurements. IEEE transactions on automation science and engineering 3(4):360–371

    work page 2006

  7. [7]

    Cambridge University Press

    Boyd S, Vandenberghe L (2004) Convex Optimization. Cambridge University Press

    work page 2004

  8. [8]

    Foundations and Trends R⃝ in Machine Learning 3(1):1–122

    Boyd S, Parikh N, Chu E, Peleato B, Eckstein J (2011) Distributed optimiza- tion and statistical learning via the alternating direction method of multipliers. Foundations and Trends R⃝ in Machine Learning 3(1):1–122

    work page 2011

  9. [9]

    IEEE Transactions on Signal Processing 64(12):3118–3130

    Chang TH, Hong M, Liao WC, Wang X (2016) Asynchronous distributed ADMM for large-scale optimization – part I: algorithm and convergence anal- ysis. IEEE Transactions on Signal Processing 64(12):3118–3130

    work page 2016

  10. [10]

    Proc IEEE International Conference on Acoustics, Speech and Signal Processing pp 6009–6013

    Chartrand R, Wohlberg B (2013) A nonconvex ADMM algorithm for group sparsity with sparse groups. Proc IEEE International Conference on Acoustics, Speech and Signal Processing pp 6009–6013

    work page 2013

  11. [11]

    Proc IEEE International Conference on Acoustics, Speech and Signal Processing pp 2849–2853

    Chaudhury K, Khoo Y , Singer A (2015) Large-scale sensor network localiza- tion via rigid subnetwork registration. Proc IEEE International Conference on Acoustics, Speech and Signal Processing pp 2849–2853

    work page 2015

  12. [12]

    SIAM Journal on Optimization 25(1):468–501

    Chaudhury KN, Khoo Y , Singer A (2015) Global registration of multiple point clouds using semidefinite programming. SIAM Journal on Optimization 25(1):468–501

    work page 2015

  13. [13]

    ACM Transactions on Sensor Networks (TOSN) 8(3):19

    Cucuringu M, Lipman Y , Singer A (2012) Sensor network localization by eigen- vector synchronization over the Euclidean group. ACM Transactions on Sensor Networks (TOSN) 8(3):19

    work page 2012

  14. [14]

    Information and Inference: A Journal of the IMA 1(1):21–67

    Cucuringu M, Singer A, Cowburn D (2012) Eigenvector synchronization, graph rigidity and the molecule problem. Information and Inference: A Journal of the IMA 1(1):21–67

    work page 2012

  15. [15]

    Optimization Methods and Software 33(1):165–193

    Diamond S, Takapoui R, Boyd S (2017) A general system for heuristic mini- mization of convex functions over non-convex sets. Optimization Methods and Software 33(1):165–193

    work page 2017

  16. [16]

    IEEE Transactions on Information Theory 57(10):6920–6941

    Donoho DL, Maleki A, Montanari A (2011) The noise-sensitivity phase transition in compressed sensing. IEEE Transactions on Information Theory 57(10):6920–6941

    work page 2011

  17. [17]

    Distance Geometry pp 351–376 28 Aditya V

    Fang X, Toh KC (2013) Using a distributed SDP approach to solve simulated protein molecular conformation problems. Distance Geometry pp 351–376 28 Aditya V . Singh, Kunal N. Chaudhury

    work page 2013

  18. [18]

    SIAM Journal on Optimization 26(1):337–364

    Hong M, Luo ZQ, Razaviyayn M (2016) Convergence analysis of alternating di- rection method of multipliers for a family of nonconvex problems. SIAM Journal on Optimization 26(1):337–364

    work page 2016

  19. [19]

    Proc Eurographics Symposium on Geometry Processing pp 187–196

    Krishnan S, Lee PY , Moore JB, Venkatasubramanian S (2005) Global registra- tion of multiple 3D point sets via optimization-on-a-manifold. Proc Eurographics Symposium on Geometry Processing pp 187–196

    work page 2005

  20. [20]

    Computer Networks 51(10):2529–2553

    Mao G, Fidan B, Anderson BDO (2007) Wireless sensor network localization techniques. Computer Networks 51(10):2529–2553

    work page 2007

  21. [21]

    Proc IEEE International Conference on Image Processing pp 987–991

    Miraj Ahmed S, Chaudhury KN (2017) Global multiview registration using non- convex ADMM. Proc IEEE International Conference on Image Processing pp 987–991

    work page 2017

  22. [22]

    Excursions in Harmonic Analysis pp 123–147

    Mixon DG (2015) Phase transitions in phase retrieval. Excursions in Harmonic Analysis pp 123–147

    work page 2015

  23. [23]

    IEEE Signal Processing Letters 24(10):1453– 1457

    Sanyal R, Ahmed SM, Jaiswal M, Chaudhury KN (2017) A scalable ADMM algorithm for rigid registration. IEEE Signal Processing Letters 24(10):1453– 1457

    work page 2017

  24. [24]

    IEEE Transactions on Signal Processing 65(20):5357–5367

    Sanyal R, Jaiswal M, Chaudhury KN (2017) On a registration-based ap- proach to sensor network localization. IEEE Transactions on Signal Processing 65(20):5357–5367

    work page 2017

  25. [25]

    IEEE Transactions on Parallel and Distributed Systems 15(11):961–974

    Shang Y , Rumi W, Zhang Y , Fromherz M (2004) Localization from connectiv- ity in sensor networks. IEEE Transactions on Parallel and Distributed Systems 15(11):961–974

    work page 2004

  26. [26]

    IEEE Transactions on Pattern Analysis and Machine Intelligence 26(8):1037–1050

    Sharp GC, Lee SW, Wehe DK (2004) Multiview registration of 3D scenes by minimizing error between coordinate frames. IEEE Transactions on Pattern Analysis and Machine Intelligence 26(8):1037–1050

    work page 2004

  27. [27]

    IEEE Transactions on Signal Processing 62(6):1424–1437

    Simonetto A, Leus G (2014) Distributed maximum likelihood sensor network localization. IEEE Transactions on Signal Processing 62(6):1424–1437

    work page 2014

  28. [28]

    IEEE Transactions on Signal Processing 63(17):4532–4543

    Soares C, Xavier J, Gomes J (2015) Simple and fast convex relaxation method for cooperative localization in sensor networks using range measurements. IEEE Transactions on Signal Processing 63(17):4532–4543

    work page 2015

  29. [29]

    Journal of Scientific Computing pp 1–35

    Wang Y , Yin W, Zeng J (2015) Global convergence of ADMM in nonconvex nonsmooth optimization. Journal of Scientific Computing pp 1–35

    work page 2015

  30. [30]

    SIAM Journal on Opti- mization 19(2):655–673

    Wang Z, Zheng S, Ye Y , Boyd S (2008) Further relaxations of the semidefinite programming approach to sensor network localization. SIAM Journal on Opti- mization 19(2):655–673

    work page 2008

  31. [31]

    ACM Transactions on Sensor Networks (TOSN) 6(4):35

    Zhang L, Liu L, Gotsman C, Gortler SJ (2010) An as-rigid-as-possible approach to sensor network localization. ACM Transactions on Sensor Networks (TOSN) 6(4):35

    work page 2010

  32. [32]

    SIAM Journal on Scientific Computing 26(1):313–338

    Zhang Z, Zha H (2004) Principal manifolds and nonlinear dimensionality re- duction via tangent space alignment. SIAM Journal on Scientific Computing 26(1):313–338

    work page 2004