Optimization on Manifolds

Pose estimation, hand-eye calibration, and pose-graph SLAM all reduce to the same problem: fit a rotation or a rigid transform to noisy measurements. The unknowns live in $SO(3)$ or $SE(3)$, which are curved manifolds, not vector spaces. A plain gradient step $x \leftarrow x - \alpha\,\nabla f$ adds a vector to a point on a curved set and lands off the set. Riemannian optimization fixes this with three moves: take the tangential part of the gradient, step, and retract back onto the manifold.

Why a plain step leaves the manifold

Take the smallest curved example, the unit circle $S^1 = \{x \in \mathbb{R}^2 : \lVert x\rVert = 1\}$, a stand-in for $SO(2)$. Suppose we want to align $x$ with a fixed unit target $t$ by minimizing

$$f(x) = -\,x^{\top} t, \qquad \nabla f(x) = -\,t .$$

The Euclidean update $x - \alpha\,\nabla f = x + \alpha t$ is a point whose norm is generally not $1$, so it is no longer a rotation. You could renormalize after every step, but the raw gradient still points partly off the manifold, and that radial component is wasted work that the projection just throws away.

Project, step, retract

At a point $x$ the manifold has a tangent space $T_x\mathcal{M}$, the flat space of allowed instantaneous motions. On the circle it is the line orthogonal to $x$. The Riemannian gradient is the tangential part of the Euclidean one, obtained with the orthogonal projector $P_x$:

$$\operatorname{grad} f(x) = P_x\,\nabla f(x), \qquad P_x = I - x x^{\top} \quad (\lVert x\rVert = 1).$$

We step in the tangent space and then retract back onto $\mathcal{M}$. On the circle the retraction is renormalization; on a Lie group such as $SO(3)$ it is the exponential map applied on the group,¹

$$x_{k+1} = \mathcal{R}_{x_k}\!\big(-\alpha\,\operatorname{grad} f(x_k)\big), \qquad \mathcal{R}_R(\xi) = R\,\exp\!\big([\xi]_\times\big).$$

The exponential map is exactly the same object that advances orientation in a physics engine: integrate the update in the flat Lie algebra, then map back onto the group so the constraint is never violated.²

A worked step on the circle

Start at $x_0 = (1,0)$ with target $t = (0,1)$ and step size $\alpha = 0.5$. The Euclidean gradient and its tangential projection are

$$\nabla f = -t = \begin{bmatrix} 0 \\ -1 \end{bmatrix}, \qquad P_{x_0} = I - x_0 x_0^{\top} = \begin{bmatrix} 0 & 0 \\ 0 & 1 \end{bmatrix}, \qquad \operatorname{grad} f = P_{x_0}\nabla f = \begin{bmatrix} 0 \\ -1 \end{bmatrix}.$$

Here $x_0$ is horizontal, so the gradient is already tangent and projection leaves it unchanged. The descent direction is $-\operatorname{grad} f = (0,1)$, which points straight at $t$. Stepping and then retracting:

$$\tilde x = x_0 - \alpha\,\operatorname{grad} f = \begin{bmatrix} 1 \\ 0.5 \end{bmatrix}, \quad \lVert \tilde x\rVert = \sqrt{1.25} = 1.1180, \quad x_1 = \frac{\tilde x}{\lVert \tilde x\rVert} = \begin{bmatrix} 0.8944 \\ 0.4472 \end{bmatrix}.$$

That is $x_1$ at $26.57^{\circ}$, and the objective drops from $f(x_0) = 0$ to $f(x_1) = -0.4472$: $x$ moved along the circle toward $t$ (at $90^{\circ}$). Iterating converges to $x = t$. The naive Euclidean step lands at the same $\tilde x = (1, 0.5)$ here but keeps it, sitting at norm $1.1180$, an off-manifold error of $0.1180$ until something projects it back. Away from this special point the two also disagree in direction: the radial part of $\nabla f$ survives in the naive step and is discarded by the retraction, so the naive update is a strictly worse use of the same $\alpha$.

Descent on S¹ · project, step, retractinteractive

α = 0.50

f(x) = -x·t-0.000

Riemann ‖x‖-10.000

naive ‖·‖-10.118

Riemannian step

naive Euclidean

target t (drag)

PlayStepReset

Pre-retract off-manifold error of the tangential step is 0.118; the retraction sends it back to 0.

Gauss-Newton on the manifold

Real estimation problems are least squares over many measurements, $\min_{x}\ \tfrac12\sum_i \lVert r_i(x)\rVert^2$, and the workhorse is Gauss-Newton done in the tangent space. Using the right-plus of micro Lie theory,¹ parametrize the update as a tangent increment $\delta \in \mathbb{R}^n$ around the current estimate,

$$x \boxplus \delta = x \circ \exp\!\big([\delta]_\times\big), \qquad J_i = \left.\frac{\partial\, r_i(x \boxplus \delta)}{\partial \delta}\right|_{\delta = 0}.$$

The Jacobians $J_i$ are taken with respect to the tangent coordinate $\delta$, so they are $n\times n$ for an $n$-dimensional group ($n=3$ for $SO(3)$, $6$ for $SE(3)$) with no redundant parameters and no constraint to enforce. Solve the normal equations for $\delta$ and retract:

$$\Big(\textstyle\sum_i J_i^{\top} J_i\Big)\,\delta = -\sum_i J_i^{\top} r_i, \qquad x \leftarrow x \boxplus \delta .$$

This is precisely the update inside a pose-graph SLAM back end or a camera or hand-eye calibration solver: linearize in the flat algebra, take one Gauss-Newton step, retract onto $SE(3)$, repeat. The manifold is respected at every iteration, so the estimate never drifts off the group and there is nothing to renormalize after the fact.

Footnotes

1. Sola, Deray, Atchuthan, A micro Lie theory for state estimation in robotics (2018). ↩ ↩²

2. Absil, Mahony, Sepulchre, Optimization Algorithms on Matrix Manifolds (2008). ↩