Nyström Approximation on Manifolds
This work provides a method to speed up computations on manifolds, which is relevant for optimization and data analysis in geometric settings, but the improvements are incremental.
The authors develop a Riemannian Nyström approximation for low-rank approximation of tangent operators on manifolds, reducing computational cost while maintaining accuracy. Experiments on SPD and Grassmann manifolds show comparable accuracy with reduced cost.
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.