In machine learning and data recovery, we frequently encounter the need to find a high-dimensional matrix or tensor that is constrained to be low-rank. Whether we are completing a sparse user-item rating matrix for collaborative filtering, learning a low-dimensional distance metric, or compressing the weight layers of a massive neural network, the core challenge remains the same: how do we efficiently navigate the space of low-rank structures?
Traditionally, researchers have approached this problem in one of two ways: either by factorizing the matrix into two smaller, independent matrices ($W = AB^T$) and optimizing them via standard Euclidean gradient descent, or by applying a soft convex penalty like the nuclear norm to encourage low-rank solutions.
Both approaches suffer from fundamental flaws. Factorization introduces severe optimization instabilities and representation redundancies, while nuclear norm regularization requires computationally ruinous full-scale Singular Value Decompositions (SVD) at every iteration.
Riemannian manifold optimization offers a mathematically elegant and computationally superior alternative. Instead of treating low-rank matrices as elements of a flat, unconstrained Euclidean space, it treats the set of all fixed-rank matrices as a smooth, curved geometric surface—a Riemannian manifold. By optimizing directly along this surface, we can enforce rank constraints natively, eliminate optimization redundancies, and dramatically accelerate convergence.
The Pitfalls of Flat Optimization
To understand why geometric optimization works, we must first look at why standard Euclidean methods struggle.
Consider the factorization approach, where a matrix $W \in \mathbb{R}^{m \times n}$ of rank $r$ is represented as the product of two tall-and-skinny matrices, $A \in \mathbb{R}^{m \times r}$ and $B \in \mathbb{R}^{n \times r}$. When we train $A$ and $B$ independently using standard stochastic gradient descent, we encounter a severe conditioning problem. The factorization is inherently under-determined; for any invertible matrix $X$, the product remains unchanged: $W = A B^T = (AX)(BX^{-1})^T$.
This "gauge freedom" means that during optimization, the scales of $A$ and $B$ can decouple wildly—$A$ might blow up while $B$ vanishes—leading to ill-conditioned Jacobians and training stagnation. As Zhanfeng Mo et al. demonstrate in Parameter and Memory Efficient Pretraining via Low-rank Riemannian Optimization, this independent factorization causes severe instability when trying to pretrain large language models from scratch.
The alternative is to optimize the full matrix $W$ directly in Euclidean space while penalizing its rank using a trace or nuclear norm. However, as noted by Mingkui Tan et al. in Proximal Riemannian Pursuit for Large-Scale Trace-Norm Minimization, treating low-rank matrices as elements of a flat linear vector space fails to respect their underlying non-linear structure. To enforce the rank constraint after a flat gradient step, the algorithm must compute a full-scale SVD to project the matrix back into the low-rank subspace. For a matrix of size $d \times d$, this projection scales as $O(d^3)$, creating an insurmountable computational bottleneck for large-scale applications.
The Geometry of Fixed-Rank Spaces
Riemannian optimization bypasses these issues by redefining the search space. The set of all matrices with a strictly fixed rank $r$ forms a smooth embedded submanifold within the larger ambient space of all matrices.
Euclidean Space (Flat)
┌─────────────────────────┐
│ ▲ │
│ │ Standard Step │
│ ┌──┴──────────────┐ │
│ │Tangent Space │ │
│ └──┬──────────────┘ │
│ │ │
│ ───▼─────────────── │
│ ( Manifold (Curved) )│
│ ─────────────────── │
└─────────────────────────┘
Instead of updating $A$ and $B$ independently, or updating $W$ and then forcing it to be low-rank via an expensive full SVD, we treat the matrix $W$ as a single point moving along this curved surface. Because every point on this surface is, by definition, a matrix of rank $r$, the structural constraint is satisfied automatically at every step of the optimization process. As single-author researcher Li Cheng shows in Riemannian Similarity Learning, maintaining this hard geometric constraint throughout training yields significantly more stable and efficient convergence than relying on soft convex penalties.
Moving Along the Surface: Tangent Spaces and Retractions
How do we compute a gradient step on a curved surface? We cannot simply add a gradient vector to our current matrix, as a straight-line step would immediately lift us off the manifold, breaking the low-rank constraint. Riemannian optimization solves this using a two-step mechanism: projection and retraction.
1. Projection onto the Tangent Space
At any given point $W$ on the manifold, we can approximate the local neighborhood using a flat hyperplane known as the tangent space. To compute a valid update direction, we first calculate the standard Euclidean gradient of our loss function and then mathematically project it onto this tangent space.
The magic of this step lies in its computational efficiency. Because the tangent space of a fixed-rank matrix manifold has a highly restricted, low-rank structure, projecting the gradient does not require a full SVD. Instead, as Henrik Eisenmann et al. demonstrate in Riemannian thresholding methods for row-sparse and low-rank matrix recovery, the projection can be computed using "thin" SVDs or QR decompositions that operate only on tall-and-skinny matrices. This drops the computational complexity from cubic to linear or quadratic relative to the matrix dimensions.
2. Retraction back to the Manifold
Once we have a projected gradient vector in the tangent space, we take a step along this flat hyperplane. This step lands us slightly outside the curved manifold. To fix this, we apply a operator called a retraction, which maps the point from the tangent space back down onto the manifold.
Tangent Step
W ───────────────► W_tangent
/ │
/ │ Retraction
/ ▼
───────W──────────────────────W_next─────── (Manifold Surface)
The retraction acts as a localized, highly efficient projection. Rather than performing a global $O(d^3)$ SVD over the entire space, the retraction leverages the fact that the tangent vector is already low-rank. In A new retraction for accelerating the Riemannian three-factor low-rank matrix completion algorithm, Zhizhong Li et al. introduce specialized retractions with minimizing properties that allow line searches to find exact optimal step sizes along the manifold curve without incurring extra computational overhead.
Eliminating Redundancy via Quotient Manifolds
While the embedded submanifold approach protects us from breaking the rank constraint, it does not automatically solve the "gauge freedom" redundancy ($W = AB^T = (AX)(BX^{-1})^T$). If multiple distinct pairs of $(A, B)$ map to the exact same matrix $W$, the optimization landscape will still contain flat, uninformative valleys.
To eliminate this redundancy, researchers frame the optimization on a quotient manifold. In this framework, all equivalent factorizations that yield the same underlying matrix are mathematically collapsed into a single point.
Factorization Space Quotient Manifold
┌───────────────────┐ ┌───────────────────┐
│ (A, B) │ │ │
│ │ │ │ │
│ ▼ Equivalent │ Collapse │ │
│ (AX, BX⁻¹) ├────────────►│ [W] │
│ ▲ │ │ (Single Point) │
│ │ │ │ │
│ (AY, BY⁻¹) │ │ │
└───────────────────┘ └───────────────────┘
By treating the entire equivalence class as a single geometric entity, the optimization landscape is effectively "smoothed out." In Linear Regression under Fixed-Rank Constraints: A Riemannian Approach, Gilles Meyer et al. show that optimizing over a quotient manifold completely removes representation redundancies. This prevents the gradient from wasting computational energy exploring directions that do not change the actual product matrix, resulting in significantly faster and more stable convergence than standard Euclidean factorization methods.
Scaling Beyond Matrices to Tensors
The intuition of matrix manifold optimization extends naturally to higher-dimensional data arrays, or tensors. Just as matrices can be constrained to a fixed rank, tensors can be constrained to fixed low-rank formats such as the Tucker decomposition or the Tensor Train (TT) format to beat the curse of dimensionality (Andrzej Cichocki et al. in Tensor Networks for Dimensionality Reduction and Large-scale Optimization: Part 2 Applications and Future Perspectives).
When optimizing these complex tensor networks, the geometric approach becomes even more vital. For instance, Ivan Peshekhonov et al. prove in Training a Tucker Model With Shared Factors: a Riemannian Optimization Approach that tensor decompositions enforcing shared factor matrices across multiple modes still maintain a smooth Riemannian manifold structure.
To make these methods practical, researchers have developed specialized toolkits. In Automatic Differentiation for Riemannian Optimization on Low-Rank Matrix and Tensor-Train Manifolds, Alexander Novikov et al. introduce an automatic differentiation framework that maps standard Euclidean derivatives to their Riemannian counterparts on both matrix and tensor-train manifolds. This allows practitioners to train highly compressed models—such as Exponential Machines (Alexander Novikov et al. in Exponential Machines)—with up to $2^{160}$ implicit parameters using standard backpropagation workflows, achieving convergence speeds up to twenty times faster than flat stochastic gradient descent.
By shifting our perspective from flat vector spaces to curved manifolds, we stop fighting the underlying geometry of low-rank constraints and instead use it to our advantage. Riemannian optimization transforms a constrained, ill-conditioned problem into an unconstrained, well-behaved journey along a smooth geometric surface.