Walking on the Sphere

In many computer vision and robotics problems, we need to optimize a function whose argument is a fixed-norm vector. A common example is the gravity direction expressed in the IMU frame. Another one appears in relative pose estimation: when the translation scale is unknown, its direction can be represented as a unit vector.

In both cases, the unknown does not live freely in ordinary Euclidean space. Rather, it has to stay on the unit sphere. So instead of optimizing over all \mathbb{R}^{n+1}, we want to solve a problem of the form

\min_x f\left(x\right),\quad x\in\mathcal{S}^ n

where:

\mathcal{S}^n=\{x\in\mathcal{R}^{n+1}:  \| x\|_2=1\}

One way to handle this constraint is to use Lagrange multipliers. That works, but it is not always the most pleasant route. The constraint

\|x\|_2=1

adds extra algebra, and the resulting equations can quickly become awkward.

A more geometric approach is to move directly on the manifold. We start from an initial guess x_0​, choose a small step in the tangent space at x_0, and then map that step back onto the sphere. This is the basic idea behind manifold optimization: instead of pretending that the constraint is an annoying side condition, we build the constraint into the way we move.

To do that, we need two ingredients.

First, we need a way to describe the tangent space at any point on the sphere. Since \mathcal{S}^n in an n-dimensional manifold embedded in \mathbb{R}^{n+1}, the tangent space at a point x_0 is also n-dimensional.

The vector from the origin to x_0 is just x_0 itself. On the unit sphere, this vector is normal to the surface at x_0. Therefore, any tangent vector at x_0 must be perpendicular to x_0.

So if can find n vectors

x_1,x_2,\ldots,x_n

that are all perpendicular to x_0, they form a basis for the tangent space. Then any tangent vectors can be written as a linear combination of these basis vectors. In other words, for a local parameter vector

t\in\mathbb{R}^n

we can construct the corresponding tangent vector in \mathbb{R}^{n+1} as

t \mapsto T_{x_0}=\begin{bmatrix}x_1 && x_2 && \ldots && x_n\end{bmatrix}\cdot t = U_{x_0}\cdot t

with U_{x_0} is the matrix whose columns are x_1, x_2,\ldots,x_n. This gives us a local, unconstained set of coordinates for moving around the sphere.

The next step is to define how a tangent-space step gets mapped back onto the sphere. This is not very hard – once we have the tangent T_{x_0} defined, we can consider the great circle spanned by it and x_0. Any point on that circle can be expressed as:

x\left(\theta\right)=\cos\left(\theta\right)x_0+\sin\left(\theta\right)\frac{T_{x_0}}{\|T_{x_0}\|}

In our case, a natural choice for \theta is

 \theta=\|t\|

because it means that for a zero tangent vector we don’t move away from x_0. Note, that since the columns of U_{x_0} are orthogonal unit vectors the following equation holds:

 \|T_{x_0}\|=\sqrt{T_{x_0}^TT_{x_0}}=\sqrt{t^TU^TUt}=\sqrt{t^Tt}=\|t\|

So we are now in the position to define the sphere retraction operator \oplus as:

x_0\oplus t = \cos\left(\|t\|\right)x_0+ \frac{\sin\left(\|t\|\right)}{\|t\|} U_{x_0}t