Manifold Random Features

Referee: [Theoretical Analysis] The load-bearing step is the assertion that discretizing an arbitrary manifold into a graph, applying GRFs, and lifting back produces continuous fields whose induced random features remain positive and bounded while converging to the target kernel. No explicit theorem, lemma, or derivation is supplied showing that positivity and boundedness survive the discretization limit for general manifolds (as opposed to special cases such as the sphere or torus) without additional regularity assumptions on the manifold or graph Laplacian. This directly underpins the low-variance approximation guarantee.

Authors: We thank the referee for highlighting this important point. The positivity and boundedness of the features are preserved because the Graph Random Features construction on the discretized graph inherently produces non-negative and bounded random features (as established in the GRF framework), and the lifting operation to the continuous manifold is performed via a positive linear interpolation scheme that maintains these properties. Convergence to the target kernel follows from the asymptotic equivalence between the graph Laplacian and the manifold Laplacian as the discretization becomes finer. However, we acknowledge that an explicit statement of this preservation in the form of a dedicated lemma for general manifolds was not included. We will add a new Lemma in the theoretical analysis section that rigorously proves the preservation of positivity and boundedness under the discretization and lifting steps, under the standard assumption that the graph is a consistent discretization of the manifold (e.g., as the number of points increases and the graph approximates the manifold geometry). This will not require additional regularity assumptions beyond those typically used in spectral graph theory for manifold approximation. revision: yes

Referee: [Abstract] The abstract states that continuous approximation mechanisms cannot otherwise be derived analytically in general scenarios, yet the manuscript supplies no concrete comparison, counter-example, or proof establishing that the MRF construction succeeds where prior continuous methods fail.

Authors: We agree that the abstract claim would benefit from more concrete support. The motivation is that for arbitrary manifolds, there is generally no closed-form expression for the eigenfunctions or Fourier basis needed for traditional random feature constructions like random Fourier features. We will revise the abstract slightly for precision and add a paragraph in the introduction with specific examples, such as a kernel defined on a manifold with no known analytical spectral decomposition (e.g., a perturbed sphere or an irregular surface), where continuous methods fail to provide explicit feature maps, while our discretization-based approach succeeds by leveraging graph-based computations. This will include a brief comparison to prior work on manifold kernels. revision: yes