- Rating
- 3
- Confidence
- 3(+1)
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper introduces Hierarchy-GBP (H-GBP) to accelerate Gaussian Belief Propagation (GBP) hierarchically. It eliminates global errors via coarse corrections built from local low-eigenvalue modes, and damps local errors using fine-level GBP. The authors derive the joint cycle operator with a conditional convergence analysis. Evaluations on linear systems, PGO, and BA show that H-GBP fundamentally speeds up standard GBP and outperforms state-of-the-art solvers on several large-scale problems.
Critical strengths
- Beyond introducing a multilevel perspective to GBP, this paper explicitly analyzes the inconsistency between variable beliefs and messages following coarse correction and derives the joint iteration operator, establishing a solid theoretical foundation for the convergence analysis of hierarchical GBP.
- The empirical evaluation benchmarks H-GBP not only against standard GBP, but also against mainstream solvers including g2o, Ceres, and RootBA. H-GBP demonstrates significant runtime advantages across multiple large-scale PGO and BA datasets, highlighting its practical value.
Critical weaknesses
None
Questions for authors
- In the BA experiments, the final objective costs vary across different methods. For example, on Dubrovnik356, H-GBP’s final cost is approximately 3.4% higher than that of Ceres. While the appendix provides runtime-vs-cost curves against PowerBA, a complete comparison with Ceres and RootBA is missing. Could the authors provide runtime comparisons under a unified accuracy threshold (i.e., time-to-accuracy)?
- While the hierarchical structure is claimed to be key to accelerating GBP convergence, Figure 6 only compares error reduction under equal numbers of GBP sweeps, without accounting for the coarse-solve overhead in the total runtime. Could the authors provide a direct comparison of the total wall-clock time required for standard GBP and H-GBP to achieve the same accuracy?
Reviewer kiY5 Question 5
5. Theory and Implementation
Q: Thm B.21 requires running H-GBP until the relative-residual rule (27) holds, but the PGO runs use fixed cycle and sweep budgets (L1609-1611). Is (27) met?
A: Yes, (27) is met. All 180 inner solves across nine PGO datasets numerically satisfy the residual inequality in Eq. (27) with a common tolerance ηˉ=0.88, evaluated before nonlinear line search.
Here ηt is the relative linear-system residual in the At−1 norm; γ⋆ measures the normalized difference between the true Hessian and the Gauss-Newton matrix at a stationary point.
The curvature estimates use the true Huber Hessian and the same gauge. Across all datasets, maxtηt=0.874848<0.88<0.883382, where the last value is the smallest estimated admissible threshold.
Q: The implementation freezes the precisions at a finite tolerance (App. D.1). By Lemma B.8's own algebra, this adds a forcing term Fa(Λˉ)−Λˉaxi⋆ to each sweep, so the limiting output can be biased. Is this checked or bounded?
A: Finite-tolerance freezing can introduce bias. For a frozen linear H-GBP cycle, let e collect the mean and message errors, T be the cycle matrix, and f be the forcing accumulated over one cycle. Then e+=Te+f. If ρ(T)<1, precision freezing introduces a bounded steady-state perturbation, e∞=(I−T)−1f. We checked this empirically: disabling freezing on all nine PGO datasets changed final costs by at most 1.64×10−8 relatively; tightening the BA precision tolerance to 10−12 with a 512-sweep cap changed final costs by at most 5.39×10−7 across ten datasets. These differences are negligible at the reported benchmark accuracy. Precision freezing is therefore a practical accuracy-efficiency trade-off, similar in purpose to choosing solver tolerances or floating-point precision: it reduces repeated precision computations while preserving the measured solution quality.
Q: Is the ϵ stabilization of the Schur denominators (Remark after Assumption B.2) consistent with the A,b used for the residual and the coarse solve?
Yes. PGO uses ϵ=10−7 for all SE2 and ϵ=10−10 for all SE3. All BA uses scale-aware stabilization, ϵ=10−12max(1,maxi∣Dii∣), to keep the perturbation small relative to the local Schur denominator while maintaining a floor.
Q: What is the nonlinear update for BA and for robust PGO (damping rule, robust reweighting)?
BA uses Levenberg–Marquardt damping adjusted by the actual-to-predicted cost reduction, with Armijo backtracking of the joint camera–point update and no robust loss. Robust PGO recomputes Huber weights wf=min(1,5/rf⊤Ωfrf) at each relinearization, using step-halving until the Huber objective does not increase.