Applications, Geodesic Convexity, and Why Non-Convex Can Still Be Solvable

The application that drove much of this field's development is recovering a matrix from a small fraction of its entries, under the assumption that it has low rank.

The recommender-system framing is standard: rows are users, columns are items, observed entries are ratings, and the low-rank assumption encodes that preferences are driven by a small number of latent factors.

There are two classical approaches, and both have a specific weakness.

Nuclear norm relaxation replaces the rank constraint with a convex surrogate. It comes with strong recovery guarantees and is genuinely elegant. Its problem is scale: the natural algorithms require an SVD of the full matrix per iteration, which is prohibitive for large problems.

Unconstrained factorisation writes the matrix as a product of two thin factors and optimises both. This scales well and abandons the constraint set's structure, introducing an invariance, since scaling one factor and inversely scaling the other leaves the product unchanged, which creates flat directions.

The Riemannian approach optimises directly over the manifold of fixed-rank matrices, keeping the exact rank constraint while working in the true dimension.

The efficiency argument is worth following, because it explains why this is not merely a reformulation.

An n-by-m matrix of rank r has roughly $r(n + m - r)$ degrees of freedom, vastly fewer than its $nm$ entries. For a million-by-million matrix of rank 10, that is tens of millions of parameters rather than a trillion.

The Riemannian method never forms the full matrix. Points are stored in factored form. Tangent vectors decompose into a part changing the column space, a part changing the row space, and a part changing the core, and each piece is small. Retraction requires a truncated SVD, but of a small matrix built from those factors, not of the ambient one.

So every operation costs on the order of the true dimension rather than the ambient one.

The comparison against unconstrained factorisation is the more interesting one. Both scale. The manifold version additionally quotients out the scaling invariance, removing flat directions that slow convergence, and it keeps the rank exactly rather than approximately, which matters when downstream code depends on it.

A second family has a shared structure and appears across many fields.

You have many objects, each with an unknown orientation or phase. You observe noisy measurements of relative orientations between pairs. Recover the individual orientations.

The instances look unrelated until you see the pattern. In structure from motion, cameras have unknown poses and image pairs give relative poses. In cryo-electron microscopy, each particle image is a projection from an unknown orientation, and the reconstruction requires recovering them. In sensor networks, relative angle measurements between nodes must be assembled into a global layout. In clock synchronization, relative offsets must produce absolute times.

The formulation is naturally Riemannian: unknowns live on the rotation group, or on the sphere for phase synchronization, and the objective compares predicted against observed relative measurements.

One structural feature is unavoidable. Rotating every orientation by the same amount leaves all relative measurements unchanged, so the solution is only ever determined up to a global transformation. That is not a defect of the method; the data genuinely does not contain the information, and it is a case where recognising a symmetry is part of stating the problem correctly.

Here is the result that most changes how you should think about non-convexity, and it is a genuine surprise.

Many hard combinatorial problems have semidefinite programming relaxations. SDPs are convex, so they are solvable to global optimality in principle. In practice they are expensive: the variable is an n-by-n matrix constrained to be positive semidefinite, and standard solvers scale badly.

The Burer-Monteiro approach factors that matrix as $X = YY^\top$ with Y having only p columns, then optimises over Y. Positive semidefiniteness is automatic, and the variable count drops from order n squared to order np.

The cost is that the reformulated problem is non-convex, which ordinarily means you would expect spurious local minima.

The striking result is that for many such problems, once p is large enough relative to the number of constraints, the non-convex problem has no spurious local minima. Every second-order critical point is a global optimum of the original SDP.

Boumal has contributed to this line of theory. The lesson generalises beyond the specific setting: non-convex does not imply hard, and understanding the geometry can convert an intractable convex problem into a tractable non-convex one that is solved globally anyway.

Ordinary non-convex optimisation offers only local guarantees. Manifold problems frequently do better, by one of three distinct mechanisms, which is why practitioners in this area routinely trust their solutions more than non-convexity alone would justify.

The first of those routes deserves its own treatment, because it is the cleanest.

A function is geodesically convex if it is convex along every geodesic of the manifold. This is the exact analogue of ordinary convexity, with straight lines replaced by the manifold's straightest curves.

The payoff is identical to the Euclidean case: every local minimum is a global minimum, and the usual convex machinery applies with geodesic replacements.

What makes the concept valuable is that a function can be geodesically convex while being non-convex as a function on the ambient space. The curvature is doing real work, since convexity depends on which curves count as straight.

The richest source of examples is the manifold of symmetric positive definite matrices under the affine-invariant metric. Several quantities that are awkward in flat coordinates, including certain matrix means and log-determinant expressions, are geodesically convex there. Problems in metric learning, diffusion tensor processing, and Gaussian covariance estimation exploit this.

Boumal's book covers geodesic convexity for exactly this reason: it is where the theory delivers guarantees rather than just a well-posed formulation.

Principal component analysis is the example that ties the path together, because it can be posed on three different manifolds and the choice reveals what each one is for.

Finding the top principal component means maximising variance over unit-norm directions, which is optimisation on the sphere. Its critical points are the eigenvectors, as the second lesson derived.

Finding the top k components as an orthonormal basis is optimisation on the Stiefel manifold.

But if the objective is the projection error onto the subspace, then any orthonormal basis of the same subspace gives the same value. The Stiefel formulation therefore has a continuum of equivalent optima differing only by rotation of the basis. The correct formulation is on the Grassmann manifold, whose points are subspaces.

For plain PCA nobody needs this, because the SVD solves it directly. The formulation matters when you modify the problem: add sparsity, robustness to outliers, missing entries, or non-Euclidean losses, and no closed form survives, while the manifold structure does.

That is the general pattern. Manifold optimisation is what you reach for when the classical closed form breaks but the geometry remains.

Four claims, and the practical rule that follows.

Curved parameter spaces are common and worth recognising. Rotations, subspaces, fixed-rank matrices, and covariances all form manifolds, and treating them as constrained flat spaces discards structure.

The machinery is smaller than it appears. Projection converts an ambient gradient into a Riemannian one, retraction replaces addition, and vector transport enables methods that combine directions across iterations. Standard algorithms then port with their guarantees largely intact.

The benefits are concrete. Exact feasibility with no penalty parameter, work proportional to the true dimension, and removal of symmetries that create flat directions.

Non-convex does not imply hard. Geodesic convexity, provably benign landscapes as in Burer-Monteiro, and spectral initialisation each supply global guarantees that generic non-convex optimisation cannot.

The rule for practice: when your parameters satisfy smooth equality constraints, ask whether they form a known manifold. If they do, the tooling exists, Manopt implements the standard cases, and you are likely to get a better-conditioned problem in fewer variables with exact feasibility for the cost of one projection and one retraction.