PaperlayerView exact revision on arXiv

Source-linked AI summary

Decentralization and Acceleration Enables Large-Scale Bundle Adjustment

Taosha Fan, Joseph Ortiz, Ming Hsiao, Maurizio Monge, Jing Dong, Todd Murphey, Mustafa Mukadam

arXiv:2305.07026v3cs.CVcs.ROmath.OC

TL;DR

Large-scale bundle adjustment must distribute data and computation, while centralized approaches face computation and communication bottlenecks. DABA decouples optimization variables through a reformulated reprojection error and surrogate, then uses acceleration and adaptive restart. On public benchmarks, it outperforms decentralized baselines and reports more accurate solutions with speedups up to 953.7x over Ceres.

  • Problem

    Centralized bundle-adjustment methods face time, memory, and communication limits, motivating methods that can scale across devices.

    Source: §I · pp. 1–2

  • Method

    DABA reformulates reprojection error and uses a surrogate to decouple device variables into independent subproblems, with Nesterov’s acceleration and adaptive restart.

    Source: §I · p. 2, §IV · p. 3, §V · pp. 4–5

  • Results

    Across public benchmarks, DABA converges much faster than decentralized baselines with similar memory and communication load and is more accurate than centralized baselines, with speedups up to 953.7x over Ceres.

    Source: §I · p. 2, §VIII · p. 8

  • Takeaways & Limitations

    DABA provides convergence guarantees to first-order critical points while operating through decentralized communication.

    Source: §VIII · p. 8

Abstract

from arXiv · show

Scaling to arbitrarily large bundle adjustment problems requires data and compute to be distributed across multiple devices. Centralized methods in prior works are only able to solve small or medium size problems due to overhead in computation and communication. In this paper, we present a fully decentralized method that alleviates computation and communication bottlenecks to solve arbitrarily large bundle adjustment problems. We achieve this by reformulating the reprojection error and deriving a novel surrogate function that decouples optimization variables from different devices. This function makes it possible to use majorization minimization techniques and reduces bundle adjustment to independent optimization subproblems that can be solved in parallel. We further apply Nesterov's acceleration and adaptive restart to improve convergence while maintaining its theoretical guarantees. Despite limited peer-to-peer communication, our method has provable convergence to first-order critical points under mild conditions. On extensive benchmarks with public datasets, our method converges much faster than decentralized baselines with similar memory usage and communication load. Compared to centralized baselines using a single device, our method, while being decentralized, yields more accurate solutions with significant speedups of up to 953.7x over Ceres and 174.6x over DeepLM. Code: https://joeaortiz.github.io/daba.

I. INTRODUCTION AND RELATED WORK

Large-scale bundle adjustment increasingly needs multiple devices, but centralized approaches face compute, memory, and communication bottlenecks. DABA addresses these limits with a decentralized method that decouples device variables and reports faster convergence and more accurate solutions.

I. INTRODUCTION AND RELATED WORK

  • Single-device solvers exploit bundle-adjustment structure but cannot use distributed parallelism and face time and memory limits on large problems.The paper motivates multi-device approaches as image datasets grow while single-device computing power reaches saturation.Source: §I · p. 1
  • Most existing multi-device methods still rely on a central device to maintain consistency, creating communication bottlenecks that limit their scale.The paper names parallel clustering, preconditioned conjugate-gradient, stochastic decomposition, and GPU-based solvers among these approaches.Source: §I · pp. 1–2
  • Prior decentralized methods use peer-to-peer communication but are reported to be slower, less accurate, and more sensitive to parameter tuning than centralized methods.The paper also notes that their convergence guarantees may be absent or depend on strict assumptions.Source: §I · p. 2
  • DABA reports more accurate solutions than single-device centralized baselines, with speedups of up to 953.7x over Ceres and 174.6x over DeepLM.On public-dataset benchmarks, it also converges much faster than decentralized baselines with similar memory usage and communication load.Source: §I · p. 2
  • DABA reformulates reprojection error and derives a surrogate that decouples variables across devices, reducing the problem to independent subproblems.It applies Nesterov’s acceleration and adaptive restart to improve convergence while retaining theoretical guarantees.Source: §I · p. 2

II. BACKGROUND

Bundle adjustment jointly estimates camera parameters and scene points from images, and large-scale problems distribute data across devices. This section frames the objective as minimizing reprojection penalties over camera-point pairs, with a stated class of robust losses.

II. BACKGROUND

  • Bundle adjustment jointly estimates camera extrinsics and intrinsics and point positions representing scene geometry from images showing points across views.The paper focuses on decentralized operation using peer-to-peer communication without a central device.Source: §II · p. 2
  • When communication latency and bandwidth are more expensive than computation, decentralized bundle adjustment is a relevant setting.The paper gives large-scale bundle adjustment as an example.Source: §II · p. 2
  • The optimization minimizes the sum of penalties over camera-point reprojection pairs, with variables partitioned across multiple devices.The robust loss is assumed differentiable, concave, and nondecreasing; Huber and Welsch losses are cited as examples.Source: §II · p. 2

III. A NOVEL REPROJECTION ERROR

The section introduces a reprojection error intended to separate camera and point variables, which ordinary reprojection errors leave inseparable. The resulting formulation supports a later surrogate that yields independent optimization subproblems across devices.

III. A NOVEL REPROJECTION ERROR

  • The proposed reprojection error addresses the difficulty of decentralized optimization by separating camera extrinsics and intrinsics from point positions.The paper says existing reprojection errors leave cameras and points inseparable.Source: §III · p. 2
  • The undistorted reprojection ray is modeled as the point position in the camera frame up to a scalar factor for each reprojection pair.The passage identifies the observed distorted image point, focal length, radial undistortion coefficients, camera extrinsics, and point position in this formulation.Source: §III · p. 2
  • The reprojection error is zero if and only if the stated relation in Eq. (5) holds, and geometrically results from projecting the ray onto a normal plane.The cited passage locates this geometric construction in Fig. 2.Source: §III · p. 3
  • The reformulated error is used to decouple variables across devices and reduce decentralized bundle adjustment to independent optimization subproblems on a single device.This is the bridge to the following section’s surrogate-function formulation.Source: §III · p. 3

IV. DECOUPLE VARIABLES, REDUCE TO SUBPROBLEMS

A surrogate upper-bounds the objective while matching it at the current iterate, and is constructed to decouple variables across devices. Majorization minimization then reduces bundle adjustment to independent, parallelizable subproblems with peer-to-peer communication.

IV. DECOUPLE VARIABLES, REDUCE TO SUBPROBLEMS

  • The surrogate upper-bounds F(x) and equals it at x(k), allowing majorization minimization to reduce the objective through independent device-level subproblems.The resulting updates satisfy F(x(k+1)) ≤ F(x(k)).Source: §IV · pp. 3–4
  • Majorization minimization requires a surrogate that both majorizes the objective and decouples variables across devices; finding such a function is nontrivial.The section presents its derivation as the main contribution.Source: §IV · p. 3
  • For inter-device reprojection pairs, the surrogate decouples camera and point variables so each device can optimize its own variables independently.The construction requires ∥lj − ti∥ ≠ 0 and uses a positive ξ close to zero for convergence analysis.Source: §IV · pp. 3–4
  • Only neighboring devices sharing inter-device reprojection pairs communicate, exchanging camera or point variables only when such pairs exist.Once each device’s surrogate is constructed, its subproblem can be solved in parallel without inter-device communication.Source: §IV · pp. 3–4

V. SPEEDUP AND GUARANTEE CONVERGENCE

The method adds Nesterov acceleration and a decentralized adaptive restart scheme to speed convergence while retaining guarantees. Local per-device metrics enable restart without a central device evaluating the global objective.

V. SPEEDUP AND GUARANTEE CONVERGENCE

  • Nesterov acceleration targets the slow convergence of the underlying first-order majorization-minimization method, while adaptive restart extends guarantees to this nonconvex setting.The paper notes that acceleration alone has no provable convergence for nonconvex bundle adjustment.Source: §V · pp. 4–5
  • The extrapolated momentum update requires no inter-device communication, so Nesterov acceleration remains decentralized.The momentum uses the difference between successive iterates, with the extrapolation ratio updated by the method.Source: §V · p. 4
  • A local adaptive restart uses per-device metrics because the global objective cannot be evaluated without a central device, and it guarantees convergence to first-order critical points.Each device solves the accelerated subproblem and falls back to the majorization-minimization update when its local restart condition is met.Source: §V · p. 5
  • Applying acceleration and adaptive restart yields empirical speedup while maintaining decentralization and theoretical guarantees.The paper evaluates these improvements in its experiments.Source: §V · p. 5

VI. DABA: PUTTING IT ALL TOGETHER

DABA combines decentralized parallel subproblems with Nesterov acceleration and adaptive restart, requiring limited peer-to-peer communication. It has a first-order convergence guarantee under stated conditions and performs well with approximate subproblem solutions.

VI. DABA: PUTTING IT ALL TOGETHER

  • DABA combines independent optimization subproblems, Nesterov’s acceleration, and adaptive restart in a fully decentralized method with limited peer-to-peer communication.The method is guaranteed to converge to first-order critical points under mild conditions.Source: §VI · p. 5
  • Under ξ > 0, 0 < η ≤ 1, and Assumptions 1 to 4, DABA’s iterates converge to first-order critical points.The proof is in Appendix C.3.Source: §VI · p. 5
  • DABA performs well with approximate subproblem solutions and converges faster to more accurate solutions than consensus methods,.Approximate solutions consume fewer computational resources.Source: §VI · pp. 5–6

VII. EVALUATION

The evaluation benchmarks DABA against centralized and decentralized methods on BAL and 1DSfM datasets. It assesses accuracy, efficiency, memory use, and communication load.

VII. EVALUATION

  • The benchmarks compare DABA with centralized Ceres and DeepLM and decentralized DR and ADMM on BAL and 1DSfM.The datasets include partitions for multi-device methods.Source: §VII · p. 6
  • For decentralized methods, measurements are evenly distributed when a dataset has more than 700 cameras; otherwise, partitioning follows cameras per device.DR, ADMM, and DABA use CUDA; Ceres uses C++, and DeepLM uses CUDA and Python.Source: §VII · p. 6
  • Experiments use CPU cores and 8 Nvidia V100 GPUs, with OpenMPI for inter-device communication, and compare all methods on accuracy, efficiency, memory usage, and communication load.Source: §VII · p. 6

A. Accuracy

DABA achieves the lowest reprojection errors among decentralized methods across the evaluated datasets, losses, and device counts, and often outperforms centralized methods. Its accuracy advantage persists with fewer inner LM steps for subproblems.

A. Accuracy

  • DABA has the lowest reprojection errors among decentralized methods on all 20 datasets, both losses, and all device counts, and beats centralized methods on most datasets.Table III summarizes the number of datasets where DABA is more accurate than Ceres and DeepLM.Source: A. Accuracy · pp. 6–7, Table III · p. 7
  • As device count increases, decentralized methods become less accurate, but larger problems are less affected by that increase.The authors conclude decentralized methods such as DABA are suitable for large-scale bundle adjustment.Source: A. Accuracy · p. 7
  • DABA achieves better accuracy with one successful inner LM step across setups, while DR and ADMM need up to 20 steps for acceptable accuracy.The authors interpret this as greater robustness to approximate subproblem solutions and improved time efficiency.Source: A. Accuracy · p. 7

B. Efficiency

DABA is faster than centralized baselines across the reported large-dataset setups, even under a stricter convergence criterion. Its acceleration and adaptive restart also improve iteration efficiency over the unaccelerated variant.

B. Efficiency

  • The speedup compares DABA’s time to reach Fref with a baseline’s time to reach FΔ, where FΔ > Fref.The evaluation uses the same time measure for computation and communication.Source: B. Efficiency · p. 7
  • Under a stricter convergence criterion requiring DABA to attain Fref < F∆(p), DABA was 23.9–588.3x faster than Ceres and 2.6–174.6x faster than DeepLM for trivial loss, and 69.7–953.7x faster than Ceres for Huber loss.Source: B. Efficiency · p. 7
  • DABA solves more problems in fewer iterations and is much faster than DUBA, indicating improved performance with Nesterov’s acceleration and adaptive restart.Performance profiles measure the percentage of problems reaching a target objective at each iteration.Source: B. Efficiency · p. 7

C. Memory & Communication

Across four large datasets, DABA uses similar per-device memory to other decentralized methods while its memory per device falls as the device count increases. Its communication load generally rises with device count and exceeds ADMM’s because DABA exchanges both points and cameras.

C. Memory & Communication

  • DABA uses almost the same per-device memory as other decentralized methods, while its communication load exceeds ADMM’s because it exchanges points as well as cameras.The comparison covers Venice and Final in BAL, and Piccadilly and Trafalgar in 1DSfM.Source: C. Memory & Communication · p. 7, Figure 4 · p. 8
  • Per-device maximum memory decreases as the number of devices increases, while total communication load generally increases.Fig. 4 compares these measures across 1, 2, 4, 8, 16, and 32 devices on the four largest datasets.Source: C. Memory & Communication · p. 7, Figure 4 · p. 8
  • Fig. 3 compares iteration-based performance profiles for DABA and other decentralized methods across 20 BAL and 1DSfM datasets under trivial and Huber losses.The profiles use Ceres reference objectives and a suboptimality tolerance of 1 × 10^-4.Source: Figure 3 · p. 8

VIII. CONCLUSION

DABA combines decentralized optimization, majorization minimization, and acceleration, with convergence guarantees to first-order critical points. The conclusion reports better accuracy and efficiency than decentralized baselines, while the appendices describe benchmark evaluations, assumptions, and proof steps.

VIII. CONCLUSION

  • DABA decouples device-specific optimization variables into independent subproblems using majorization minimization, Nesterov’s acceleration, and adaptive restart.The method has provable convergence to first-order critical points and, compared with decentralized baselines –, less strict assumptions and no need for specific parameter tuning.Source: §VIII · p. 8
  • 953.7x over Ceres and 174.6x over DeepLM are the reported speedups for DABA on large-scale datasets.The conclusion also reports greater accuracy and efficiency than decentralized baselines,, with similar communication overhead.Source: §VIII · p. 8

A.2. Efficiency

  • The efficiency evaluation measures optimization time on datasets with more than 700 cameras, including both computation and communication time.DABA is compared with Ceres and DeepLM for reaching reference and target mean reprojection errors using four or eight devices.Source: §A.2 · p. 10, Table VII · p. 12, Table VIII · p. 12

APPENDIX B ASSUMPTIONS

  • The convergence analysis assumes a robust loss from a broad class including Huber and Welsch, noncoincident cameras and points, and bounded camera intrinsics.Two additional assumptions are described as common in optimization convergence analysis;, use similar but stricter assumptions.Source: Appendix B · p. 10

A.1. Accuracy

  • DABA achieves the lowest reprojection error among decentralized methods and mostly outperforms centralized methods across 20 BAL and 1DSfM datasets.Table VI covers trivial and Huber losses; DeepLM does not support Huber loss.Source: Table VI · p. 11

C.1. Proof of Proposition 1

  • The Proposition 1 proof upper-bounds squared reprojection error while decoupling camera extrinsics and intrinsics from point positions.The argument invokes differentiability, concavity, and monotonicity of the robust loss, and the stated camera-point separation assumption.Source: Appendix B · p. 10, §C.1 · pp. 13–14

C.2. Proof of Proposition 2

  • The Proposition 2 proof follows directly from Proposition 1 and Eq. (21).The supplied conclusion states the proof relationship without further elaborating its steps.Source: §C.2 · p. 14

C.3. Proof of Proposition 3

These proofs establish convergence to first-order critical points through objective convergence, vanishing successive-iterate differences and Riemannian gradient, and the relation between device-local and global objectives. They also establish inequalities and boundedness or Lipschitz properties for objective components and surrogate gradients.

C.3. Proof of Proposition 3

  • The proof shows the auxiliary objective is nonincreasing, including when adaptive restart is triggered, which yields convergence of the objective values.At restart, the updated iterate is a local minimum of the surrogate under Assumption 4.Source: §C.3 · p. 15
  • Under Assumptions 1–3, the objective has bounded, Lipschitz-continuous Euclidean gradients, and the surrogate gradients are bounded and satisfy a Lipschitz bound.These gradient properties support the proof that the Riemannian gradient vanishes.Source: §C.3 · pp. 17–18
  • DABA’s objective converges, successive-iterate differences vanish, and the Riemannian gradient tends to zero, establishing convergence to first-order critical points.The proof proceeds through these three results in sequence.Source: §C.3 · pp. 14, 15, 16, 18

D.1. Proof of Lemma 4

  • The proof of Lemma 4(c) uses Fij ≤ 0 to conclude that Fα(k) ≤ Eα(k).Source: §D.1 · p. 20

D.2. Proof of Lemma 5

  • The proof of Lemma 5 uses Lipschitz continuity and boundedness of G and H to establish the needed bound for their product.It bounds the product difference by separating changes in G and H and applying the triangle inequality.Source: §D.2 · p. 20

D.3. Proof of Lemma 6

  • The proof of Lemma 6 follows Lemma 5’s proofs after replacing x and x′ with x(k) and x(k+1).Source: §D.3 · p. 20

D.4. Proof of Lemma 7

  • The proof concludes that F(x) has bounded and Lipschitz continuous Euclidean gradients, reducing verification to boundedness and Lipschitz continuity of the functions in its gradient expressions.Source: §D.4 · p. 21

D.5. Proof of Lemma 8

  • The proof of Lemma 8 establishes bounded surrogate gradients at successive iterates and verifies Eqs. (C.51) and (C.52).It uses boundedness of the residuals under Assumptions 2 and 3 and the fact that successive iterates approach one another.Source: §D.5 · p. 23
Loading 2305.07026v3…