betaFeedback

WorksMathematics

Spectral Landmarks: Alignment of Landmark Kernel Translates with the Leading Eigenfunctions of a Kernel Operator

Abstract

We study the problem of choosing mm landmark points so that the span of the kernel translates is as close as possible to the leading ss-dimensional eigenspace of a positive-definite kernel. The natural measure is the Hilbert-Schmidt operator discrepancy between the reproducing-kernel-Hilbert-space (RKHS) projectors onto the two subspaces. We give a closed form spectral alignment function in terms of the truncated Mercer kernel and relate it to the classical integrated power function (Nyström trace error) through a two-sided sandwich bound. Minimizing the function by gradient descent on the landmark coordinates produces landmark sets that are evenly spaced. Theoretical results show that optimal configurations are those whose eigenfunction sampling matrix is a scaled isometry. On homogeneous spaces these are exactly the minimal equal-weight cubature rules for products of leading eigenfunctions, and for every m≥sm\ge s they are the configurations whose sampled eigenfunctions form a unit-norm tight frame. Experiments on S1\mathbb{S}^1 and S2\mathbb{S}^2 agree with the theory. On the circle, with s≤2ms\le2m and a moderate bandwidth, every random start converges to equispaced landmarks, and on the sphere the optimizer recovers the regular tetrahedron, octahedron, and icosahedron from random starts. Finally, we analyze the numerical conditioning of the problem.

Generative AI was used for copy editing and language polishing.

Introduction

Low-rank kernel approximations aim to circumvent the O(n2)O(n^2) memory and O(n3)O(n^3) factoring cost of large n×nn \times n Gram matrices by focusing on strategically chosen subsets of kernel entries. For symmetric positive definite kernels, this challenge manifests in identifying a subset that preserves spectral structure while minimizing approximation error.

The Nyström method exemplifies this approach by selecting m≪nm \ll n landmarks Z={z1,…,zm}Z = \{z_1, \ldots, z_m\} and replacing the kernel KK by its projection K^\hat{K} onto the span of the translates k(⋅,zj)k(\cdot, z_j) [1, 2, 3]. The goal is a low-rank surrogate of KK that is cheap to store and apply, yet close to KK in a norm that matters for the downstream task. The quality of the approximation hinges critically on the selection of the landmark points, a combinatorial optimization problem with no universally efficient solution.

A natural way forward is to measure the residual K−K^K - \hat{K} directly. Its diagonal is the squared power function PZ2P_Z^2 of scattered-data approximation, which is the squared RKHS distance from k(⋅,x)k(\cdot, x) to the span of the translates. Integrating PZ2P_Z^2 gives the trace error of the Nyström approximation, so minimizing ∫PZ2\int P_Z^2, or sup⁡PZ\sup P_Z, or running greedy selection are all residual-based criteria for landmarks which control the point-wise error of kernel interpolation [4, 5].

Many uses of a kernel depend on its leading ss-dimensional eigenspace VsV_s of the integral operator, which carries the principal components of the feature map and, after the appropriate degree normalization of the kernel, the leading diffusion-map coordinates [6]. However, a landmark set can have a small trace error and still span a subspace that is rotated away from VsV_s, in particular when the spectrum has no clear gap at ss. This paper therefore studies a different, explicitly spectral criterion. Rather than asking that the translates approximate KK well on average, we ask that their span align with VsV_s explicitly. The resulting spectral alignment objective is a Grassmannian distance between two subspaces of the RKHS. It is smooth in the landmark positions and inexpensive to evaluate. After a one-time computation of the top ss eigenpairs, each evaluation needs the m×Nm \times N cross-kernel matrix between landmarks and data and a small m×mm \times m Cholesky factorization. Its minimizers turn out to be evenly spaced, which we support with theory (§ 4) and with numerical experiments on the circle and the sphere (§ 7–§ 8).

We begin by deriving a closed form for the spectral subspace alignment in terms of the truncated and tail Mercer kernels, and we show that it equals the sum of squared sines of the principal angles between the span of the kernel translates and the leading eigenspace VsV_s (§ 3). This form has a useful dual reading as measuring both the mass of VsV_s that leaks out of the landmark space and the mass of the kernel tail that leaks into it. We then connect the alignment functional to the integrated power function through a two-sided sandwich bound (§ 3.2). Its lower side carries a Davis–Kahan-type dependence [7] on the spectral gap, which explains why a small Nyström trace error certifies subspace alignment only when the spectrum has a clear gap at ss.

The second group of results explains why the minimizers are evenly spread (§ 4), which we observed in every experiment we ran on S1\mathbb{S}^{1} and S2\mathbb{S}^{2}. For m=sm=s, we write FF through the tangents of the principal angles between the landmark space and VsV_s (Proposition 6, a direct application of [8]). This expresses FF through the aliasing of the tail eigenfunctions onto VsV_s and yields an upper bound that is minimized exactly by tight sampling sets, meaning configurations whose eigenfunction sampling matrix is a scaled isometry (Theorem 7). In a homogeneous setting, such sets are precisely the minimal equal-weight cubature rules for products of leading eigenfunctions (Theorem 8), a homogeneous form of the classical correspondence between minimal cubature and common zeros of orthogonal polynomials [9, 10]. Equivalently, the sampled eigenfunction vectors form a unit-norm tight frame, the configuration minimizes the frame potential, and for m=sm=s it is a set of Fekete points for VsV_s attaining the Hadamard bound (Proposition 11). The frame description also extends to every m≥sm \ge s. Tight sets are the equispaced points on S1\mathbb{S}^{1} and the regular tetrahedron on S2\mathbb{S}^{2} for s=4s=4 (Corollaries 9 and 10). For larger ss on S2\mathbb{S}^{2}, tightness with m=sm=s is impossible [11]. A complementary symmetry principle, a special case of Michel’s theorem on critical orbits [12], shows that any orbit of a finite isometry group whose stabilizers fix no tangent vector is a critical point of FF (Theorem 12). This accounts for the equispaced circle configurations and the Platonic solids. Criticality does not imply minimality, however, as the cube for s=4s=4 and the dodecahedron for s=9s=9 show, even though both are tight frames for those values of ss. We also give a closed-form aliasing formula on the circle, which gives the value of FF at equispaced landmarks for every m≥sm \ge s and decays super-exponentially in mm (Theorem 13).

Finally, we study the numerical behavior of the problem and test the theory experimentally. The Gaussian bandwidth must lie in a window proportional to the landmark spacing hh. Below roughly 0.15h0.15h the position-dependent part of FF becomes exponentially small and falls below the resolution of the optimizer. At the upper end two mechanisms intervene. Once the attainable minimum of FF drops below about 10−910^{-9}, it is poorly resolved by the subtraction s−tr⁡(⋅)s-\operatorname{tr}(\cdot) in double precision and absolute stopping tolerances trigger early. At larger bandwidths, beyond roughly 2.4h2.4h on the circle and somewhat less on the sphere, the landmark Gram matrix exceeds a condition number of 101210^{12}. The resulting window shrinks as landmarks are added (§ 6). Within this window, every random start on the circle converges to equispaced landmarks, and on the sphere the optimizer recovers the regular tetrahedron, octahedron, and icosahedron (§ 7–§ 8). The optimized sets also have markedly smaller mesh ratios than Fibonacci lattices, and the integrated power function at the optimized landmarks sits near the lower end of the sandwich bound.

Background and Related work

The Nyström method is named after Nyström’s quadrature treatment of integral equations [13, 14], and entered machine learning as a way to speed up kernel machines [1, 15, 16]. Many subsequent analyses bound the error of K−K^K-\widehat{K} in the trace, spectral or Frobenius norm and relate it to the choice of landmarks [2, 17, 18, 3]. Choosing the best mm landmarks is a combinatorial problem [19], and a range of strategies have been proposed. These include uniform sampling [1], leverage-score and ridge leverage-score sampling [2, 20, 21], kk-means centers [17, 19], determinantal sampling [22], regularized Christoffel functions [23], and greedy pivoted Cholesky [15, 16, 24]. The guarantees for these schemes are stated for the residual K−K^K-\widehat{K}, not for the alignment of span⁡{k(⋅,zj)}\operatorname{span}\{k(\cdot,z_j)\} with an eigenspace of KK.

The trace error is exactly ∫Pz2 dμ\int P^2_z\,d\mu (§ 3.1), which ties the Nyström literature to scattered-data approximation, where the power function controls the pointwise error of radial basis function (RBF) interpolation [4, 25, 5]. In that setting, point sets that are near-optimal for the power function are quasi-uniform [26], and P-greedy selection attains optimal convergence rates [27]. Fekete points, which maximize the determinant of a sampling matrix, offer a classical route to well-conditioned interpolation along similar lines [28]. Our objective differs from all of these in that it is a spectral subspace criterion rather than a residual norm. The sandwich bound (Theorem 2) makes the relation between the two quantitative, and Theorem 7 shows that spectral alignment rewards a property closely related to the Fekete idea, namely an isometric eigenfunction sampling matrix.

Because evenly spaced landmarks emerge from the optimization, our sphere experiments connect to the standard notions of uniformity on S2\mathbb{S}^{2}. Spherical designs [29, 11] and minimal-energy or best-packing configurations [30], the latter going back to the Tammes problem [31, 32, 33, 34], are the usual notions of evenly spaced points on S2\mathbb{S}^{2}. The Platonic solids are the canonical small examples, and our sphere experiments recover several of them.

Finally, the practical limits we identify for Gaussian kernels belong to a well-studied trade-off between accuracy and conditioning for flat RBFs, which Schaback’s uncertainty principle describes [4]. Stable evaluation schemes such as RBF-QR were developed to circumvent it [35, 36], and they form the background for Section 6.

Setting and conventions

Let Ω\Omega be a compact metric space, μ\mu a finite Borel measure on Ω\Omega, and KK a continuous, symmetric, strictly positive-definite kernel on Ω\Omega with reproducing kernel Hilbert space (RKHS) H\mathcal{H}. Write Kx=K(⋅,x)K_x = K(\cdot,x), so that ⟨f,Kx⟩H=f(x)\langle f,K_x\rangle_{\mathcal{H}} = f(x) for all f∈Hf \in\mathcal{H} (the reproducing property). The integral operator (TKf)(x)=∫K(x,y)f(y) dμ(y)(T_Kf)(x) = \int K(x,y)f(y)\,d\mu(y) is compact, self-adjoint and positive on L2(μ)L^2(\mu). We write its positive eigenvalues as λ1≥λ2≥⋯>0\lambda_1 \ge\lambda_2 \ge\cdots> 0, with L2(μ)L^2(\mu)-orthonormal eigenfunctions φi\varphi_i. There are infinitely many of them when μ\mu has infinite support, as for the uniform measures on the circle and the sphere, and at most NN of them when μ\mu is an empirical measure on NN points. Each φi\varphi_i has the continuous representative φi=λi−1TKφi\varphi_i = \lambda_i^{-1}T_K\varphi_i, which is defined on all of Ω\Omega, and Mercer’s theorem gives

K(x,y)=∑iλiφi(x)φi(y),x,y∈supp⁡μ.K(x,y) = \sum_i \lambda_i \varphi_i(x)\varphi_i(y), \qquad x,y \in\operatorname{supp}\mu.

The functions

ψi:=λi φi,⟨ψi,ψk⟩H=δik,\psi_i := \sqrt{\lambda_i}\,\varphi_i,\qquad\langle\psi_i,\psi_k\rangle_{\mathcal{H}} = \delta_{ik},

are orthonormal in H\mathcal{H}, and the reproducing property gives ⟨ψi,Kx⟩H=ψi(x)\langle\psi_i,K_x\rangle_{\mathcal{H}} = \psi_i(x) for every x∈Ωx \in\Omega.

The ψi\psi_i need not span H\mathcal{H}. Their closed span is the closure of the range of the covariance operator CC of § 3.1, and its orthogonal complement is

H0:={f∈H:f=0  μ-a.e.}=ker⁡C.\mathcal{H}_0 := \{f \in\mathcal{H}: f = 0\ \ \mu\text{-a.e.}\} = \ker C.

When supp⁡μ=Ω\operatorname{supp}\mu= \Omega, continuity forces H0={0}\mathcal{H}_0 = \{0\}, so {ψi}\{\psi_i\} is an orthonormal basis of H\mathcal{H}. For an empirical measure μN\mu_N, by contrast, H0\mathcal{H}_0 is infinite-dimensional, and the translate KzK_z of a point zz off the data has a nonzero component in it. To treat both cases at once we complete {ψi}\{\psi_i\} to an orthonormal basis of H\mathcal{H} by appending an orthonormal basis of H0\mathcal{H}_0, and we assign the eigenvalue λi=0\lambda_i = 0 to each appended element. These are placed after all positive eigenvalues, so the ordering λ1≥λ2≥⋯≥0\lambda_1 \ge\lambda_2 \ge\cdots\ge0 is preserved. With this convention {ψi}\{\psi_i\} is always an orthonormal basis of H\mathcal{H} that diagonalizes CC, the expansion

Kx=∑iψi(x) ψiK_x = \sum_i \psi_i(x)\,\psi_i

holds for every x∈Ωx \in\Omega, and every sum over ii below runs over the completed basis. Throughout we assume λs>0\lambda_s > 0, so that the leading eigenspace VsV_s defined below consists of genuine eigenfunctions of TKT_K.

For the landmarks Z={z1,…,zm}Z = \{z_1,\ldots,z_m\} with KZZ=[K(zj,zl)]K_{ZZ} = [K(z_j,z_l)] invertible, define the two subspaces:

  • UZ=span⁡{Kz1,…,Kzm}U_Z = \operatorname{span}\{K_{z_1},\ldots,K_{z_m}\}, with H\mathcal{H}-orthogonal projector ΠZ\Pi_Z.

  • Vs=span⁡{ψ1,…,ψs}=span⁡{φ1,…,φs}V_s = \operatorname{span}\{\psi_1,\ldots,\psi_s\} = \operatorname{span}\{\varphi_1,\ldots,\varphi_s\}, with H\mathcal{H}-orthogonal projector QsQ_s.

The Projector and the Power function

For landmarks Z={z1,…,zm}Z = \{z_1,\ldots,z_m\} with KZZK_{ZZ} invertible, the orthogonal projector onto the span of the kernel translates is the operator that interpolates a function at the landmarks using the translates KzjK_{z_j}, namely

ΠZf=∑j,l=1mKzj(KZZ−1)jlf(zl)=kZ(⋅)TKZZ−1f(Z),(1)\Pi_Z f = \sum_{j,l=1}^{m} K_{z_j}(K_{ZZ}^{-1})_{jl}f(z_l) = k_Z(\cdot)^\mathsf{T}K_{ZZ}^{-1}f(Z), \tag*{(1)}

References

  1. [1]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, pages 682–688, 2001.
  2. [2]P. Drineas and M. W. Mahoney. On the Nyström method for approximating a Gram matrix for improved kernel-based learning. J. Mach. Learn. Res., 6:2153–2175, 2005.
  3. [3]A. Gittens and M. W. Mahoney. Revisiting the Nyström method for improved large-scale machine learning. J. Mach. Learn. Res., 17(117):1–65, 2016.
  4. [4]R. Schaback. Error estimates and condition numbers for radial basis function interpolation. Adv. Comput. Math., 3:251–264, 1995.DOI
  5. [5]H. Wendland. Scattered Data Approximation. Cambridge University Press, 2005.DOI
  6. [6]R. R. Coifman and S. Lafon. Diffusion maps. Appl. Comput. Harmon. Anal., 21(1):5–30, 2006.DOI
  7. [7]C. Davis and W. M. Kahan. The rotation of eigenvectors by a perturbation. III. SIAM J. Numer. Anal., 7(1):1–46, 1970.DOI
  8. [8]Peizhen Zhu and Andrew V. Knyazev. Angles between subspaces and their tangents. Journal of Numerical Mathematics, 21(4):325–340, 2013.DOI
  9. [9]I. P. Mysovskikh. Interpolatory Cubature Formulas. Nauka, Moscow, 1981. In Russian.
  10. [10]Ronald Cools, I. P. Mysovskikh, and H. J. Schmid. Cubature formulae and orthogonal polynomials. Journal of Computational and Applied Mathematics, 127(1–2):121–152, 2001.
  11. [11]E. Bannai and R. M. Damerell. Tight spherical designs, I. J. Math. Soc. Japan, 31(1):199–207, 1979.DOI
  12. [12]Louis Michel. Points critiques des fonctions invariantes sur une G-variété. Comptes Rendus de l’Académie des Sciences de Paris, 272:433–436, 1971.
  13. [13]E. J. Nyström. Über die praktische auflösung von integralgleichungen mit anwendungen auf randwertaufgaben. Acta Math., 54:185–204, 1930.DOI
  14. [14]C. T. H. Baker. The Numerical Treatment of Integral Equations. Clarendon Press, 1977.
  15. [15]A. J. Smola and B. Schölkopf. Sparse greedy matrix approximation for machine learning. In Proc. ICML, pages 911–918, 2000.DOI
  16. [16]S. Fine and K. Scheinberg. Efficient SVM training using low-rank kernel representations. J. Mach. Learn. Res., 2:243–264, 2001.DOI
  17. [17]K. Zhang, I. W. Tsang, and J. T. Kwok. Improved Nyström low-rank approximation and error analysis. In Proc. ICML, 2008.DOI
  18. [18]S. Kumar, M. Mohri, and A. Talwalkar. Sampling methods for the Nyström method. J. Mach. Learn. Res., 13:981–1006, 2012.
  19. [19]D. Oglic and T. Gärtner. Nyström method with kernel K-means++ samples as landmarks. In Proc. ICML, volume 70 of PMLR, 2017.
  20. [20]A. El Alaoui and M. W. Mahoney. Fast randomized kernel ridge regression with statistical guarantees. In Advances in Neural Information Processing Systems 28, 2015.
  21. [21]C. Musco and C. Musco. Recursive sampling for the Nyström method. In Advances in Neural Information Processing Systems 30, 2017.arxiv.org/abs/1605.07583
  22. [22]M.-A. Belabbas and P. J. Wolfe. Spectral methods in machine learning and new strategies for very large datasets. Proc. Natl. Acad. Sci. USA, 106(2):369–374, 2009.DOI
  23. [23]M. Manuel, J. Schreurs, and J. A. K. Suykens. Nyström landmark sampling and regularized Christoffel functions. Mach. Learn., 111, 2022.
  24. [24]H. Harbrecht, M. Peters, and R. Schneider. On the low-rank approximation by the pivoted Cholesky decomposition. Appl. Numer. Math., 62(4):428–440, 2012.DOI
  25. [25]R. Schaback and H. Wendland. Kernel techniques: from machine learning to meshfree methods. Acta Numer., 15:543–639, 2006.DOI
  26. [26]S. De Marchi, R. Schaback, and H. Wendland. Near-optimal data-independent point locations for radial basis function interpolation. Adv. Comput. Math., 23:317–330, 2005.DOI
  27. [27]G. Santin and B. Haasdonk. Convergence rate of the data-independent P-greedy algorithm in kernel-based approximation. Dolomites Res. Notes Approx., 10:68–78, 2017.
  28. [28]L. Bos, S. De Marchi, A. Sommariva, and M. Vianello. Computing multivariate Fekete and Leja points by numerical linear algebra. SIAM J. Numer. Anal., 48(5):1984–1999, 2010.DOI
  29. [29]P. Delsarte, J. M. Goethals, and J. J. Seidel. Spherical codes and designs. Geometriae Dedicata, 6(3):363–388, 1977.
  30. [30]E. B. Saff and A. B. J. Kuijlaars. Distributing many points on a sphere. Math. Intelligencer, 19(1):5–11, 1997.DOI
  31. [31]P. M. L. Tammes. On the origin of number and arrangement of the places of exit on the surface of pollen-grains. Recueil des Travaux Botaniques Néerlandais, 27(1):1–84, 1930.
  32. [32]László Fejes Tóth. Über die Abschätzung des kürzesten Abstandes zweier Punkte eines auf einer Kugelfläche liegenden Punktsystems. Jahresbericht der Deutschen Mathematiker-Vereinigung, 53:66–68, 1943.
  33. [33]K. Schütte and B. L. van der Waerden. Auf welcher Kugel haben 5, 6, 7, 8 oder 9 Punkte mit Mindestabstand Eins Platz? Mathematische Annalen, 123:96–124, 1951.
  34. [34]Ludwig Danzer. Finite point-sets on S² with minimum distance as large as possible. Discrete Mathematics, 60:3–66, 1986. English translation of the author’s 1963 Habilitationsschrift, Universität Göttingen.DOI
  35. [35]B. Fornberg and C. Piret. A stable algorithm for flat radial basis functions on a sphere. SIAM J. Sci. Comput., 30(1):60–80, 2008.
  36. [36]B. Fornberg, E. Larsson, and N. Flyer. Stable computations with Gaussian radial basis functions. SIAM J. Sci. Comput., 33(2):869–892, 2011.
  37. [37]K. Fan. On a theorem of Weyl concerning eigenvalues of linear transformations I. Proc. Natl. Acad. Sci. USA, 35(11):652–655, 1949.pubmed.ncbi.nlm.nih.gov/16578320
  38. [38]A. Feragen, F. Lauze, and S. Hauberg. Geodesic exponential kernels: When curvature and linearity conflict. In Proc. IEEE Conf. Computer Vision and Pattern Recognition (CVPR), pages 3032–3042, 2015.arxiv.org/abs/1411.0296
  39. [39]N. Aronszajn. Theory of reproducing kernels. Transactions of the American Mathematical Society, 68(3):337–404, 1950.
  40. [40]Evarist Giné M. The addition formula for the eigenfunctions of the Laplacian. Advances in Mathematics, 18(1):102–107, 1975.
  41. [41]Eiichi Bannai and R. M. Damerell. Tight spherical designs, II. Journal of the London Mathematical Society (2), 21(1):13–30, 1980.DOI
  42. [42]John J. Benedetto and Matthew Fickus. Finite normalized tight frames. Advances in Computational Mathematics, 18:357–385, 2003.DOI
  43. [43]Ian H. Sloan and Robert S. Womersley. Extremal systems of points and numerical integration on the sphere. Advances in Computational Mathematics, 21:107–125, 2004.DOI
  44. [44]Felix Bartel, Lutz Kämmerer, Kateryna Pozharska, Martin Schäfer, and Tino Ullrich. Exact discretization, tight frames and recovery via D-optimal designs. The SMAI Journal of Computational Mathematics, 11:607–636, 2025.DOI
  45. [45]L. R. Welch. Lower bounds on the maximum cross correlation of signals. IEEE Transactions on Information Theory, 20(3):397–399, 1974.DOI
  46. [46]Louis Michel and Boris I. Zhilinskiĭ. Symmetry, invariants, topology. Basic tools. Physics Reports, 341:11–84, 2001.DOI
  47. [47]Henry Cohn, Noam D. Elkies, Abhinav Kumar, and Achill Schürmann. Point configurations that are asymmetric yet balanced. Proceedings of the American Mathematical Society, 138(8):2863–2872, 2010.DOI
  48. [48]John Leech. Equilibrium of sets of particles on a sphere. The Mathematical Gazette, 41(336):81–90, 1957.DOI
  49. [49]Philip J. Davis. Circulant Matrices. Wiley, New York, 1979.
  50. [50]Yoshua Bengio, Jean-François Paiement, Pascal Vincent, Olivier Delalleau, Nicolas Le Roux, and Marie Ouimet. Out-of-sample extensions for LLE, Isomap, MDS, eigenmaps, and spectral clustering. In Advances in Neural Information Processing Systems 16, pages 177–184, 2004.
  51. [51]F. W. J. Oliver, D. W. Lozier, R. F. Boisvert, and C. W. Clark, editors. NIST Handbook of Mathematical Functions. Cambridge University Press, 2010.
  52. [52]M Castro, P Jordao, and Peron A. Super-exponential decay rates for eigenvalues and singular values of integral operators on the sphere. J. Comput. Appl. Math., 2020.DOI
  53. [53]H. Q. Minh, P. Niyogi, and Y. Y. Yao. Mercer’s theorem, feature maps, and smoothing. In Learning Theory (COLT 2006), volume 4005 of Lecture Notes in Computer Science, pages 154–168. Springer, 2006.
  54. [54]L. Rosasco, M. Belkin, and E. De Vito. On learning with integral operators. J. Mach. Learn. Res., 11:905–934, 2010.DOI

Paper details

vlnc:W_3kdfads9
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Generative AI

View statement
Looking for related papers…
Contents