Retractions and Riemannian Algorithms

You have a point on the manifold and a tangent direction. Now you must actually move.

In flat space this is trivial: add the step to the point. On a manifold it fails immediately, because the tangent space is a linear approximation and adding a tangent vector to a point lands off the surface. Take a point on a sphere, add a tangent vector, and the result has norm greater than one.

The geometrically exact answer is the exponential map. It follows the geodesic, the manifold's straightest possible curve, starting at your point in your chosen direction, for the specified distance. This is what a straight line becomes on a curved space, and on a sphere geodesics are great circles.

The exponential map is the right notion, and it has a practical problem: computing it requires solving a differential equation. For some manifolds there is a closed form. For others there is not, and evaluating it every iteration would dominate the cost of the algorithm.

So optimisation uses something weaker and cheaper.

A retraction is any map that takes a point and a tangent vector to a new point on the manifold, subject to two conditions.

A zero step must leave you where you are. And to first order, moving by a small tangent vector must move you in that direction at that speed.

That is the entire requirement. A retraction agrees with the exponential map to first order and may diverge beyond it.

The reason this suffices is the key insight of the field. Optimisation convergence theory rests on first-order behaviour: a descent direction with a small enough step decreases the objective. Any retraction preserves that, so first-order convergence guarantees survive, and second-order methods retain their rates under mild additional conditions.

The practical consequences are large. For the sphere, retraction is just normalisation: add the tangent vector and divide by the norm. For the Stiefel manifold, take the Q factor of a QR decomposition, or the orthogonal polar factor. For fixed-rank matrices, truncate an SVD to rank r.

Each is a standard numerical linear algebra routine, and each replaces a differential equation solve.

With projection and retraction in hand, the algorithm writes itself.

def riemannian_gradient_descent(M, cost, egrad, x0, iters=1000):
    x = x0
    for k in range(iters):
        g = M.proj(x, egrad(x))          # Riemannian gradient
        if M.norm(x, g) < 1e-8:
            break
        t = line_search(M, cost, x, -g)  # step size
        x = M.retract(x, -t * g)         # move along the manifold
    return x

Compare it to Euclidean gradient descent and the differences are exactly two lines. The gradient is projected. The update uses retraction instead of addition.

Everything else, the stopping criterion, the line search logic, the overall structure, is unchanged. That is why the Riemannian versions of standard algorithms exist at all: the algorithms were never really about flat space, only about having a notion of direction and a way to move.

The convergence theory follows the same pattern. Under standard smoothness assumptions, Riemannian gradient descent converges to a critical point, with rates analogous to the Euclidean case. Boumal's book develops this including worst-case complexity.

Gradient descent needs nothing more. Better algorithms hit a new obstacle immediately.

Conjugate gradients builds a search direction combining the current gradient with the previous search direction. Quasi-Newton methods compare gradients at successive iterates to estimate curvature. Momentum accumulates past steps.

All of these add or compare vectors from different iterations. On a manifold, those vectors live in different tangent spaces, and tangent spaces at different points are different vector spaces. Adding a vector from the tangent space at the previous point to one at the current point is not merely inadvisable, it is undefined.

Vector transport solves this: a map carrying a tangent vector at one point to a tangent vector at another, so that comparison and combination become meaningful.

The exact version is parallel transport, which moves a vector along a geodesic keeping it as constant as curvature permits. As with the exponential map, it is expensive, so practice uses cheaper transporters that agree to the needed order.

Often the simplest choice works: transport by moving the vector to the new point and projecting onto the new tangent space.

Every Riemannian algorithm follows the same translation. Three Euclidean operations have curved-space replacements, and everything else carries over unchanged, which is why the whole standard toolkit was ported rather than reinvented.

For serious problems the method of choice is usually the Riemannian trust-region algorithm, and understanding why illuminates what curvature costs.

A trust-region method builds a quadratic model of the objective around the current point, valid within a region of trusted radius, minimises the model within that region, and then adjusts the radius based on how well the model predicted the actual decrease.

On a manifold the model is built on the tangent space, which is flat, so the subproblem is an ordinary Euclidean trust-region problem. The manifold enters only when the computed step is retracted back.

This is why the method suits curved spaces well. Line search methods must repeatedly retract to evaluate candidate step sizes, and each retraction costs a decomposition. A trust-region method does its work in the flat tangent space and retracts once per accepted step.

The convergence properties are strong: global convergence to critical points, with superlinear local convergence when the Hessian is used. Note the Hessian here must include the curvature correction from the connection, which is the point at which the geometry stops being optional bookkeeping.

Choosing a manifold representation is partly an exercise in comparing the cost of its primitives.

Two practical points follow.

For fixed-rank manifolds the retraction is not a full SVD of a large matrix, which would defeat the purpose. Efficient implementations exploit the factored representation of tangent vectors so the decomposition happens on small matrices, and this is why low-rank Riemannian methods scale.

And for positive definite matrices, the exact exponential map costs a matrix exponential per step. Cheaper retractions exist and are usually preferred, which is precisely the trade the retraction concept was invented to permit: exactness where it is free, first-order agreement where it is not.

Four problems account for most difficulties when these methods misbehave, and each has a recognisable signature.

Double projection. You project the gradient yourself, then hand it to a library that projects again. The result is still a descent direction, so the algorithm appears to work while converging slowly. Supply the ambient gradient and let the library project.

Missing Hessian correction. Using the projected Euclidean Hessian without the connection term. Newton and trust-region methods lose their superlinear rate but still descend, so the symptom is disappointing convergence rather than an error.

Wrong manifold for the symmetry. Using Stiefel where the objective only depends on the span. The optimum becomes a continuum rather than a point, iterates drift within it, and convergence tests behave badly. Use Grassmann.

Numerical drift. Repeated retractions accumulate floating-point error, so orthogonality degrades over many thousands of iterations. Periodic re-orthogonalisation fixes it cheaply.

The unifying diagnostic: these methods usually fail by converging slowly rather than crashing, because the projections and retractions keep everything feasible and roughly correct even when a detail is wrong.