david-m-rosen
commented
3 years ago Hey Arman!
Thanks for the very kind words, and for your interest in the project(s) -- seeing folks engage this closely with the work is the best compliment there is :-)!
OK, on to the actual question :-). The issues you point out are exactly right, but among these, I would highlight the interaction between the choice of Hessian model and the specific optimization method used by each algorithm [in point (1)] and the choice of algorithm used to compute the minimum eigenpair in SE-Sync vs. Shonan [in point (2)]:
-
Just to recap, SE-Sync performs each (local) optimization in the Riemannian Staircase using a truncated-Newton trust-region method together with the exact Riemannian Hessian, while Shonan Averaging is based upon the Gauss-Newton method. The main computational advantage that the former method has is that it is possible to express the (exact) Riemannian Hessian as Hess = Proj [Euclidean Hessian + f(gradient)], where f(gradient) is a cheaply-computable function of the gradient, and the Euclidean Hessian is a constant matrix, since our objective is quadratic. [Check out Sec. 5.1.3 in the IJRR paper, esp. eqs. (41)--(44), if you want to see this more explicitly.] What this means from a practical standpoint is that SE-Sync never actually has to construct or factor any heavy-duty matrices while the main loop is running -- every matrix that needs to explicitly appear in the optimization can be constructed once, at the beginning of the algorithm, and then cached for subsequent use. In contrast, Shonan Averaging uses the Gauss-Newton implementation in GTSAM, which needs to recompute the Jacobian matrix at each iteration.
-
The implementation of the SE-Sync code differs slightly from the formal algorithm presented in the paper: the truncated-Newton trust-region method that we use in the SE-Sync library only directly enforces first-order optimality, so we do still need to perform the same minimum-eigenpair-based solution certification + (possible) saddle escape procedure that Shonan Averaging does. [Note that this doesn't invalidate any of the optimality guarantees, etc., from the paper, since we are still directly checking global optimality, and can make forward progress (descent) from any suboptimal critical point.] So again, the only difference between the two methods is how specifically this minimum-eigenpair computation is done. SE-Sync uses a spectrally-shifted Lanczos procedure to do this (check out Sec. III-C of this workshop paper for the details), while Shonan Averaging uses a simpler spectrally-shifted accelerated power method. Formally, these two methods have the same asymptotic convergence rates; however, as a practical matter, Lanczos is faster because it makes use of more information about the Krylov subspaces it generates than the accelerated power method does (at the cost of a more complex iteration scheme). Our recent paper on certifiably-correct distributed SLAM actually has an entire section (Sec. 6.1) devoted to comparing and contrasting these two approaches, if you'd like to see all the details :-).
Zooming out a bit: I should mention that the main idea behind Shonan Averaging's design was not necessarily to produce the fastest possible method. Rather, the goal was to show how one could take standard computational tools that are already used as the foundation of estimation pipelines in robotics and computer vision (i.e. Gauss-Newton-based optimization libraries like GTSAM or Ceres), and employ them to implement certifiably correct estimators that scale comparably with current state-of-the-art techniques. So Shonan Averaging stakes out a different position in the design space than SE-Sync does -- it trades off a bit of speed in favor of being super-easily deployable using already-common tools :-).
armandok
Dear David,
Thank you so much for this amazing work. I wasn't sure where to ask this question, so I'll ask it here.
It appears to me that SE-Sync is faster and more efficient than SRA given the following reasons:
I was wondering if you could provide some clarification on this. I'd appreciate it very much.