pith. sign in

arxiv: 2605.14933 · v1 · pith:BMCTTX6Qnew · submitted 2026-05-14 · 🧮 math.NA · cs.NA· math.OC

Nystr\"om Approximation on Manifolds

Hantao Nie , Bin Gao , Andi Han , Pratik Jawanpuria , Bamdev Mishra , Zaiwen Wen This is my paper

Pith reviewed 2026-06-30 20:18 UTC · model grok-4.3

classification 🧮 math.NA cs.NAmath.OC
keywords Nyström approximationRiemannian optimizationmanifoldslow-rank approximationrandomized methodstangent spaceSPD manifoldGrassmann manifold
0
0 comments X

The pith

The Riemannian Nyström approximation constructs an intrinsic low-rank version of tangent operators on manifolds that preserves positive semidefiniteness and classical error bounds.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a Riemannian Nyström approximation that produces low-rank representations of operators defined on tangent spaces by projecting onto chosen subspaces. This construction uses a Haar-Grassmann sketching condition expressed in a coordinate-free way, ensuring the approximation stays consistent when vectors are transported isometrically between tangent spaces. The resulting operator inherits positive semidefiniteness and approximation guarantees from the Euclidean Nyström method. The authors further embed the approximation inside a randomized Newton-type algorithm for manifold optimization. Experiments on the SPD and Grassmann manifolds plus real-data geodesic analysis show that the approach lowers the cost of solving linear systems while keeping accuracy comparable to full operators.

Core claim

The Riemannian Nyström approximation is an intrinsically defined low-rank approximation of tangent operators obtained through subspace projections and Haar-Grassmann sketching; because the sketching condition is compatible under isometric vector transport, the approximation remains well-defined across tangent spaces and directly inherits positive semidefiniteness together with the approximation-error properties of the classical Nyström method.

What carries the argument

Riemannian Nyström approximation: low-rank tangent-operator approximation via subspace projections and Haar-Grassmann sketching that is invariant under isometric vector transport.

If this is right

  • The approximation supplies a cheaper positive-semidefinite surrogate for any tangent-space linear system that would otherwise require full inversion.
  • A randomized Newton method built on the approximation converges at a rate governed by the inherited Nyström error bounds rather than the dimension of the ambient tangent space.
  • Numerical tests on the SPD and Grassmann manifolds confirm that operator cost drops while solution accuracy remains comparable to the exact operator.
  • The same construction applies directly to principal geodesic analysis on real data sets.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The coordinate-free sketching may allow the same low-rank technique to be applied to other first-order or second-order operators on Riemannian manifolds beyond the Newton setting.
  • If the transport compatibility holds for a wider class of sketching matrices, the method could serve as a building block for kernel approximations on manifolds.
  • The approach suggests that many Euclidean randomized linear-algebra primitives can be lifted to manifolds provided a suitable invariance condition is identified.

Load-bearing premise

The Haar-Grassmann sketching condition must remain compatible when vectors are moved isometrically between different tangent spaces.

What would settle it

Construct the approximation on the sphere or another simple manifold, apply an isometric transport, and check whether the resulting low-rank operator loses positive semidefiniteness or exceeds the stated approximation error relative to the full tangent operator.

Figures

Figures reproduced from arXiv: 2605.14933 by Andi Han, Bamdev Mishra, Bin Gao, Hantao Nie, Pratik Jawanpuria, Zaiwen Wen.

Figure 1
Figure 1. Figure 1: Left: construction of the sketching operator and its adjoint. Right: flow view [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Performance of the RRNCN method on the geodesically convex optimization [PITH_FULL_IMAGE:figures/full_fig_p024_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Performance of the RRNCN method on the Grassmann manifold with [PITH_FULL_IMAGE:figures/full_fig_p025_3.png] view at source ↗
read the original 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\"om 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\"om 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\"om 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper develops the Riemannian Nyström approximation, a low-rank approximation of tangent operators on manifolds obtained through subspace projections onto the tangent space. The construction is claimed to be intrinsic to the manifold and to inherit positive semidefiniteness together with approximation-error bounds from the classical Euclidean Nyström method. A coordinate-free Haar–Grassmann sketching condition is introduced in place of Gaussian sketching; this condition is asserted to remain compatible under isometric vector transport across tangent spaces. The approximation is then used to build a randomized Newton-type method for manifold optimization. Numerical experiments on the SPD and Grassmann manifolds, together with principal geodesic analysis on real data, are reported to show reduced computational cost while preserving accuracy.

Significance. If the stated inheritance of algebraic properties and the compatibility of the sketching operator are rigorously established, the work would supply a practical tool for accelerating linear-algebra operations that arise repeatedly in manifold optimization and statistical analysis. The coordinate-free formulation of the sketching condition is a potentially useful technical contribution that respects the geometry of the tangent bundle. The numerical illustrations on standard manifolds and real data provide initial evidence of utility, but the overall significance hinges on the missing derivations.

major comments (2)
  1. [Abstract] Abstract: the central claim that the Riemannian Nyström approximation 'inherits desirable properties … e.g., positive semidefiniteness and approximation errors' is asserted without any derivation, error bound, or proof sketch. Because this inheritance is load-bearing for the entire contribution, the manuscript must supply the corresponding arguments (most likely in the sections that define the approximation and the sketching operator).
  2. The compatibility of the Haar–Grassmann sketching condition under isometric vector transport is stated as a key technical ingredient, yet no argument is visible showing that the low-rank projection remains well-defined and consistent across tangent spaces. This assumption directly affects whether the randomized Newton method is rigorously justified on the manifold.
minor comments (2)
  1. [Abstract] The abstract mentions 'approximation errors' but does not indicate the norm or the dependence on the sketch size; a single sentence clarifying the expected rate would improve readability.
  2. Ensure that all manifold-specific notation (e.g., the precise definition of the tangent-space projection and the vector-transport map) is introduced with consistent symbols before being used in the algorithmic description.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and constructive feedback on our manuscript. The comments highlight important points regarding the rigor of our claims on inheritance of properties and compatibility under transport. We address each major comment below and will revise the manuscript accordingly to strengthen the presentation.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim that the Riemannian Nyström approximation 'inherits desirable properties … e.g., positive semidefiniteness and approximation errors' is asserted without any derivation, error bound, or proof sketch. Because this inheritance is load-bearing for the entire contribution, the manuscript must supply the corresponding arguments (most likely in the sections that define the approximation and the sketching operator).

    Authors: We agree that the inheritance claims require explicit derivation to support the contribution. In the revised manuscript, we will add a new theorem (in the section defining the Riemannian Nyström approximation) that rigorously shows preservation of positive semidefiniteness via the intrinsic subspace projection onto the tangent space, together with error bounds obtained by reducing to the Euclidean Nyström case through the exponential map and parallel transport. A proof sketch will be included. revision: yes

  2. Referee: [—] The compatibility of the Haar–Grassmann sketching condition under isometric vector transport is stated as a key technical ingredient, yet no argument is visible showing that the low-rank projection remains well-defined and consistent across tangent spaces. This assumption directly affects whether the randomized Newton method is rigorously justified on the manifold.

    Authors: The coordinate-free definition of the Haar–Grassmann sketching is designed to ensure compatibility, but we acknowledge that an explicit argument for consistency of the low-rank projection is needed. In the revision, we will insert a proposition immediately following the definition of the sketching operator, proving that the sketched projection commutes with isometric vector transport (using the fact that the Grassmannian sketching is invariant under orthogonal transformations induced by the transport). This will also clarify the justification for the randomized Newton method. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation extends classical Nyström via new sketching condition

full rationale

The paper constructs the Riemannian Nyström approximation intrinsically on tangent spaces by subspace projection and introduces the Haar-Grassmann sketching condition as a coordinate-free replacement for Gaussian sketching. Positive semidefiniteness and error bounds are inherited from the external classical Nyström method rather than redefined or fitted within the paper. No load-bearing self-citations, uniqueness theorems from prior author work, or fitted inputs renamed as predictions appear in the provided text. The central claims rest on the new construction and compatibility under isometric transport, which are presented as independent developments without reducing to input definitions by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Review performed on abstract only; no explicit free parameters, axioms, or invented entities are stated. The method implicitly relies on standard Riemannian geometry structures.

axioms (1)
  • domain assumption Manifolds admit tangent spaces equipped with isometric vector transport
    Invoked to ensure the sketching condition is compatible across tangent spaces.

pith-pipeline@v0.9.1-grok · 5719 in / 1166 out tokens · 24555 ms · 2026-06-30T20:18:38.104447+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

40 extracted references · 30 canonical work pages · 4 internal anchors

  1. [1]

    Absil, C

    P.-A. Absil, C. G. Baker, and K. A. Galliv an,Trust-region methods on Riemannian manifolds, Foundations of Computational Mathematics, 7 (2007), pp. 303–330, https: //doi.org/10.1007/s10208-005-0179-9

    work page doi:10.1007/s10208-005-0179-9 2007

  2. [2]

    Absil, R

    P.-A. Absil, R. Mahony, and R. Sepulchre,Optimization Algorithms on Matrix Manifolds, Princeton University Press, 2008, https://doi.org/10.1515/9781400830244

    work page doi:10.1515/9781400830244 2008

  3. [3]

    Alaoui and M

    A. Alaoui and M. W. Mahoney,Fast randomized kernel ridge regression with statistical guarantees, in Advances in Neural Information Processing Systems (NeurIPS), vol. 28, Curran Associates, Inc., 2015, pp. 775–783

    2015

  4. [4]

    W. N. Anderson and G. E. Trapp,Shorted operators II, SIAM Journal on Applied Mathe- matics, 28 (1975), pp. 60–71, https://doi.org/10.1137/0128007

    work page doi:10.1137/0128007 1975

  5. [5]

    Ando,Generalized Schur complements, Linear Algebra and its Applications, 27 (1979), pp

    T. Ando,Generalized Schur complements, Linear Algebra and its Applications, 27 (1979), pp. 173–186, https://doi.org/10.1016/0024-3795(79)90040-5

    work page doi:10.1016/0024-3795(79)90040-5 1979

  6. [6]

    Bach,Sharp analysis of low-rank kernel matrix approximations, in Proceedings of the 26th Annual Conference on Learning Theory, vol

    F. Bach,Sharp analysis of low-rank kernel matrix approximations, in Proceedings of the 26th Annual Conference on Learning Theory, vol. 30 of Proceedings of Machine Learning Research, PMLR, 2013, pp. 185–209

    2013

  7. [7]

    Bendoka t, R

    T. Bendoka t, R. Zimmermann, and P.-A. Absil,A Grassmann manifold handbook: Basic geometry and computational aspects, Advances in Computational Mathematics, 50 (2024), p. 6, https://doi.org/10.1007/s10444-023-10090-8

    work page doi:10.1007/s10444-023-10090-8 2024

  8. [8]

    Bonito and J

    A. Bonito and J. E. Pasciak,Convergence analysis of variational and non-variational multigrid algorithms for the Laplace–Beltrami operator, Mathematics of Computation, 81 (2012), pp. 1263–1288, https://doi.org/10.1090/S0025-5718-2011-02551-2

    work page doi:10.1090/s0025-5718-2011-02551-2 2012

  9. [9]

    Boumal,An Introduction to Optimization on Smooth Manifolds, Cambridge University Press, 2023, https://doi.org/10.1017/9781009166164

    N. Boumal,An Introduction to Optimization on Smooth Manifolds, Cambridge University Press, 2023, https://doi.org/10.1017/9781009166164

    work page doi:10.1017/9781009166164 2023

  10. [10]

    Boumal, P.-A

    N. Boumal, P.-A. Absil, and C. Cartis,Global rates of convergence for nonconvex optimization on manifolds, IMA Journal of Numerical Analysis, 39 (2019), pp. 1–33, https://doi.org/10.1093/imanum/drx080

    work page doi:10.1093/imanum/drx080 2019

  11. [11]

    M. M. Bronstein, J. Bruna, T. Cohen, and P. Veličković,Geometric deep learning: Grids, groups, graphs, geodesics, and gauges, arXiv preprint arXiv:2104.13478, (2021), https://doi.org/10.48550/arXiv.2104.13478

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2104.13478 2021

  12. [12]

    Brooks, O

    D. Brooks, O. Schw ander, F. Barbaresco, J.-Y. Schneider, and M. Cord,Riemannian batch normalization for SPD neural networks, in Advances in Neural Information Processing Systems 32, H. M. Wallach, H. Larochelle, A. Beygelzimer, F. d’Alché Buc, E. A. Fox, and R. Garnett, eds., vol. 32, Curran Associates, Inc., 2019, https://proceedings.neurips.cc/pap er_f...

    2019

  13. [13]

    Bucci, Y

    A. Bucci, Y. Naka tsukasa, and T. P ark,Numerical stability of the Nyström method, arXiv preprint arXiv:2511.15583, (2025), https://doi.org/10.48550/arXiv.2511.15583

    work page doi:10.48550/arxiv.2511.15583 2025

  14. [14]

    Cartis, N

    C. Cartis, N. I. M. Gould, and P. L. Toint,Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical results, Mathematical Programming, 127 (2011), pp. 245–295, https://doi.org/10.1007/s10107-009 -0286-5

    work page doi:10.1007/s10107-009 2011

  15. [15]

    Chikuse,Statistics on Special Manifolds, Springer, 2003, https://doi.org/10.1007/978-0-387 -21540-2

    Y. Chikuse,Statistics on Special Manifolds, Springer, 2003, https://doi.org/10.1007/978-0-387 -21540-2

    work page doi:10.1007/978-0-387 2003

  16. [16]

    Chu, L.-R

    Y.-C. Chu, L.-R. Santos, and M. Udell,Randomized Nyström preconditioned interior point-proximal method of multipliers, SIAM Journal on Scientific Computing, 48 (2026), pp. A132–A159, https://doi.org/10.1137/24M1654968

    work page doi:10.1137/24m1654968 2026

  17. [17]

    Drineas and M

    P. Drineas and M. W. Mahoney,On the Nyström method for approximating a Gram matrix for improved kernel-based learning, Journal of Machine Learning Research, 6 (2005), pp. 2153–2175

    2005

  18. [18]

    P. T. Fletcher, C. Lu, and S. Joshi,Principal geodesic analysis for the study of nonlinear statistics of shape, IEEE Transactions on Medical Imaging, 23 (2004), pp. 995–1005, https://doi.org/10.1109/TMI.2004.831793

    work page doi:10.1109/tmi.2004.831793 2004

  19. [19]

    Frangella, J

    Z. Frangella, J. A. Tropp, and M. Udell,Randomized Nyström preconditioning, SIAM Journal on Matrix Analysis and Applications, 44 (2023), pp. 718–752, https://doi.org/10.1 137/21M1466244

    2023

  20. [20]

    The spectral norm error of the naive Nystrom extension

    A. Gittens,The spectral norm error of the naive Nyström extension, arXiv preprint arXiv:1110.5305, (2011), https://doi.org/10.48550/arXiv.1110.5305

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.1110.5305 2011

  21. [21]

    Gittens and M

    A. Gittens and M. W. Mahoney,Revisiting the Nyström method for improved large-scale machine learning, Journal of Machine Learning Research, 17 (2016), pp. 1–65

    2016

  22. [22]

    D. H. Gutman and N. Ho-Nguyen,Coordinate descent without coordinates: Tangent subspace descent on Riemannian manifolds, Mathematics of Operations Research, 48 (2023), NYSTRÖM APPROXIMATION ON MANIFOLDS35 pp. 127–159, https://doi.org/10.1287/moor.2022.1253

    work page doi:10.1287/moor.2022.1253 2023

  23. [23]

    Halko, P.-G

    N. Halko, P.-G. Martinsson, and J. A. Tropp,Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions, SIAM Review, 53 (2011), pp. 217–288, https://doi.org/10.1137/090771806

    work page doi:10.1137/090771806 2011

  24. [24]

    A. Han, P. Ja w anpuria, and B. Mishra,Riemannian coordinate descent algorithms on matrix manifolds, arXiv preprint arXiv:2406.02225, (2024), https://doi.org/10.48550/arXiv .2406.02225

    work page internal anchor Pith review doi:10.48550/arxiv 2024

  25. [25]

    Hanzel y, N

    F. Hanzel y, N. Doikov, Y. Nesterov, and P. Richt arik,Stochastic subspace cubic Newton method, in Proceedings of the 37th International Conference on Machine Learning, vol. 119 of Proceedings of Machine Learning Research, PMLR, 2020, pp. 4027–4038

    2020

  26. [26]

    N. J. Higham,Functions of Matrices: Theory and Computation, SIAM, 2008, https://doi.org/ 10.1137/1.9780898717778

    work page doi:10.1137/1.9780898717778 2008

  27. [27]

    The Generalization of Student’s Ratio , year =

    H. Hotelling,The generalization of Student’s ratio, The Annals of Mathematical Statistics, 2 (1931), pp. 360–378, https://doi.org/10.1214/aoms/1177732979

    work page doi:10.1214/aoms/1177732979 1931

  28. [28]

    Huang, P.-A

    W. Huang, P.-A. Absil, and K. A. Galliv an,A Riemannian BFGS method for nonconvex optimization problems, in Numerical Mathematics and Advanced Applications ENUMATH 2015, vol. 112 of Lecture Notes in Computational Science and Engineering, Springer, Cham, 2016, pp. 627–634, https://doi.org/10.1007/978-3-319-39929-4_60

    work page doi:10.1007/978-3-319-39929-4_60 2015

  29. [29]

    P. C. Mahalanobis,On the generalised distance in statistics, Proceedings of the National Institute of Sciences of India, 2 (1936), pp. 49–55

    1936

  30. [30]

    Mar tinsson and J

    P.-G. Mar tinsson and J. A. Tropp,Randomized numerical linear algebra: Foundations and algorithms, Acta Numerica, 29 (2020), pp. 403–572, https://doi.org/10.1017/S09624929200 00021

    work page doi:10.1017/s09624929200 2020

  31. [31]

    J. J. Moré and D. C. Sorensen,Computing a trust region step, SIAM Journal on Scientific and Statistical Computing, 4 (1983), pp. 553–572, https://doi.org/10.1137/0904038

    work page doi:10.1137/0904038 1983

  32. [32]

    Nesterov,Lectures on Convex Optimization, vol

    Y. Nesterov,Lectures on Convex Optimization, vol. 137 of Springer Optimization and Its Applications, Springer, 2018, https://doi.org/10.1007/978-3-319-91578-4

    work page doi:10.1007/978-3-319-91578-4 2018

  33. [33]

    Pennec, P

    X. Pennec, P. Fillard, and N. Ayache,A Riemannian framework for tensor computing, International Journal of Computer Vision, 66 (2006), pp. 41–66, https://doi.org/10.1007/s1 1263-005-3222-z

    work page doi:10.1007/s1 2006

  34. [34]

    Persson, N

    D. Persson, N. Boullé, and D. Kressner,Randomized Nyström approximation of non- negative self-adjoint operators, SIAM Journal on Mathematics of Data Science, 7 (2025), pp. 670–698, https://doi.org/10.1137/24M165082X

    work page doi:10.1137/24m165082x 2025

  35. [35]

    V allet and B

    B. V allet and B. Lévy,Spectral geometry processing with manifold harmonics, Computer Graphics Forum, 27 (2008), pp. 251–260, https://doi.org/10.1111/j.1467-8659.2008.01122.x

    work page doi:10.1111/j.1467-8659.2008.01122.x 2008

  36. [36]

    Vershynin,High-Dimensional Probability: An Introduction with Applications in Data Science, Cambridge University Press, Cambridge, UK, 2018, https://doi.org/10.1017/9781 108231596

    R. Vershynin,High-Dimensional Probability: An Introduction with Applications in Data Science, Cambridge University Press, Cambridge, UK, 2018, https://doi.org/10.1017/9781 108231596

    work page doi:10.1017/9781 2018

  37. [37]

    C. K. I. Williams and M. Seeger,Using the Nyström method to speed up kernel machines, in Advances in Neural Information Processing Systems 13, MIT Press, 2001, pp. 682–688

    2001

  38. [38]

    A Cubic Regularized Newton's Method over Riemannian Manifolds

    J. Zhang and S. Zhang,A cubic regularized Newton’s method over Riemannian manifolds, arXiv preprint arXiv:1805.05565, (2018), https://doi.org/10.48550/arXiv.1805.05565

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.1805.05565 2018

  39. [39]

    Zhang, I

    K. Zhang, I. W. Tsang, and J. T. Kwok,Improved Nyström low-rank approximation and error analysis, in Proceedings of the 25th International Conference on Machine Learning, ACM, 2008, pp. 1232–1239, https://doi.org/10.1145/1390156.1390311

    work page doi:10.1145/1390156.1390311 2008

  40. [40]

    B. Zhu, J. Z. Liu, S. F. Cauley, B. R. Rosen, and M. S. Rosen,Image reconstruction by domain-transform manifold learning, Nature, 555 (2018), pp. 487–492, https://doi.org/10.1 038/nature25988

    2018