Nyström Approximation on Manifolds

Hantao Nie, Bin Gao, Andi Han, Pratik Jawanpuria, Bamdev Mishra, Zaiwen WenarXiv 2026 · arXiv

TL;DR

This paper introduces the Riemannian Nyström approximation, a novel method for creating low-rank approximations of large-scale operators on manifolds. By developing a coordinate-free "Haar–Grassmann" sketching condition, the authors enable efficient computation and optimization on curved geometries, reducing memory and time costs by over 90% in some cases while maintaining high accuracy.

What Problem Does This Paper Address?

Many modern problems in machine learning (like medical imaging analysis) and signal processing are naturally constrained by the geometry of the data, which is often modeled as a Riemannian manifold. While this geometry provides a faithful representation of the data, it introduces a massive computational bottleneck: the tangent-space operator.

Whether you are performing Principal Geodesic Analysis (PGA) to find the main directions of variance in data or using a Newton-type method to optimize a function, you frequently need to construct and invert these operators (like the Riemannian Hessian). In high-dimensional spaces, the $O(d^3)$ cost of inverting a $d \times d$ operator becomes prohibitive.

Standard techniques like the Nyström approximation work well for matrices in flat Euclidean space, but they rely on coordinate systems that don't exist globally on manifolds. Furthermore, iterative algorithms move between different tangent spaces, and standard sketching methods don't "transport" well across these spaces.

Methods

The authors bridge this gap by extending Nyström theory to the manifold setting through three key innovations:

  1. Riemannian Nyström Approximation: They define a coordinate-free version of the Nyström approximation. Instead of sketching a matrix, they sketch a tangent-space operator $H_x$ by projecting it onto a low-dimensional subspace of the tangent space.
  2. Haar–Grassmann Sketching: Standard Gaussian sketching relies on coordinate bases. The authors introduce the Haar–Grassmann condition, which uses a polar decomposition approach ($F = UR$) where the isometry $U$ is Haar-uniform on the Grassmannian. This makes the sketching intrinsically geometric and coordinate-free.
  3. Transport-Compatible Sketching: A major advantage of their approach is compatibility with vector transport. In iterative optimization, you can "transport" the sketching operator from one point on the manifold to the next. This allows for a "lazy refresh" strategy, where the expensive sketching process is only performed every few iterations, significantly speeding up the algorithm.
The construction of the sketching operator (left) and the flow of the Riemannian Nyström approximation (right).

The authors also propose the Randomized Riemannian Nyström Cubic Newton (RRNCN) method, which uses this approximation to solve the Newton system in a reduced-size subspace, combined with cubic regularization for global convergence.

Datasets

The paper evaluates the proposed methods on:

  • HDM05 Dataset: A motion capture dataset containing 2,086 Symmetric Positive Definite (SPD) matrices representing human motion. This is used to test the approximation's performance in Principal Geodesic Analysis (PGA).
  • Synthetic Manifold Data: Used for controlled optimization experiments on both SPD manifolds and Grassmann manifolds (the space of all $p$-dimensional subspaces of $\mathbb{R}^n$).

Key Insights and Ideas

  • Intrinsic Geometry Matters: By avoiding coordinate-dependent representations, the method stays true to the manifold's structure, ensuring that properties like positive semidefiniteness are preserved.
  • The Power of Subspaces: The "aha moment" is that even in very high-dimensional manifold problems, the dominant spectral information of the Hessian or covariance operator often lies in a much smaller subspace. Capturing this subspace via Nyström is enough for high-quality optimization and analysis.
  • Efficiency through Transport: The realization that a sketch at point $x$ is still "mostly valid" at a nearby point $x'$ after vector transport is a significant practical win for iterative solvers.

Key Results

  • Memory Efficiency: In PGA experiments on the HDM05 dataset, the Nyström approximation used only 4.30% to 9.64% of the memory required by the exact method, yet achieved nearly identical classification accuracy (within ~1%).
  • Optimization Speedup: For geodesically convex optimization on SPD manifolds, the RRNCN method reached the optimal value significantly faster than standard cubic Newton methods. Intermediate sketch sizes (e.g., $\ell=80$ for a $d=4371$ problem) provided the best balance between per-iteration cost and convergence speed.
  • Transport Success: On the Grassmann manifold, refreshing the sketch only every 3 iterations (using transported sketching in between) resulted in nearly identical iteration counts to refreshing every time, but with a noticeable reduction in total wall-clock time.

Limitations and Future Work

While the paper provides strong theoretical and empirical foundations, the authors note a few areas for further exploration:

  • Parameter Tuning: Currently, the sketch size $\ell$ and regularization parameters $\nu$ are chosen manually. Developing adaptive rules for these would make the method more robust.
  • Basis Selection: The choice of the best basis for constructing the approximation remains an open question.
  • Non-convexity: While the method shows promise, more work is needed to fully understand its behavior on highly non-convex manifold optimization landscapes.

Summary updated

Abstract

Computations on a manifold often involve constructing an operator on the tangent space and computing its inverse, which can be time-consuming in many applications. In order to reduce the computational costs and preserve the benign properties of tangent operators, we develop the Riemannian Nyström approximation on manifolds, a low-rank approximation of tangent operators through subspace projections onto the tangent space. The developed approximation is intrinsically constructed and inherits desirable properties from the classical Nyström approximation, e.g., positive semidefiniteness and approximation errors. Instead of the Gaussian sketching, we introduce the Haar--Grassmann sketching condition with a coordinate-free representation, which remains compatible under isometric vector transport across tangent spaces. Moreover, we propose a randomized Newton-type method for optimization on manifolds in which the linear system is constructed via the Riemannian Nyström approximation. Numerical experiments on the SPD and Grassmann manifolds, together with principal geodesic analysis on real data, illustrate that the proposed approximation reduces the computational cost of operators while maintaining comparable accuracy.
BibTeX
@misc{nie2026nystrom,
  author = {Hantao Nie and Bin Gao and Andi Han and Pratik Jawanpuria and Bamdev Mishra and Zaiwen Wen},
  title = {{Nyström Approximation on Manifolds}},
  year = {2026},
  eprint = {2605.14933},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2605.14933},
}

Loading related content...

Figure