Generative AI was used for copy editing and language polishing.
Introduction
Low-rank kernel approximations aim to circumvent the O ( n 2 ) O(n^2) O ( n 2 ) memory and O ( n 3 ) O(n^3) O ( n 3 ) factoring cost of large n × n n \times n n × 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 ≪ n m \ll n m ≪ n landmarks Z = { z 1 , … , z m } Z = \{z_1, \ldots, z_m\} Z = { z 1 , … , z m } and replacing the kernel K K K by its projection K ^ \hat{K} K ^ onto the span of the translates k ( ⋅ , z j ) k(\cdot, z_j) k ( ⋅ , z j ) [1 , 2 , 3 ] . The goal is a low-rank surrogate of K K K that is cheap to store and apply, yet close to K K K 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} K − K ^ directly. Its diagonal is the squared power function P Z 2 P_Z^2 P Z 2 of scattered-data approximation, which is the squared RKHS distance from k ( ⋅ , x ) k(\cdot, x) k ( ⋅ , x ) to the span of the translates. Integrating P Z 2 P_Z^2 P Z 2 gives the trace error of the Nyström approximation, so minimizing ∫ P Z 2 \int P_Z^2 ∫ P Z 2 , or sup P Z \sup P_Z 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 s s s -dimensional eigenspace V s V_s V 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 V s V_s V s , in particular when the spectrum has no clear gap at s s s . This paper therefore studies a different, explicitly spectral criterion. Rather than asking that the translates approximate K K K well on average , we ask that their span align with V s V_s V 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 s s s eigenpairs, each evaluation needs the m × N m \times N m × N cross-kernel matrix between landmarks and data and a small m × m m \times m m × 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 V s V_s V s (§ 3 ). This form has a useful dual reading as measuring both the mass of V s V_s V 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 s s s .
The second group of results explains why the minimizers are evenly spread (§ 4 ), which we observed in every experiment we ran on S 1 \mathbb{S}^{1} S 1 and S 2 \mathbb{S}^{2} S 2 . For m = s m=s m = s , we write F F F through the tangents of the principal angles between the landmark space and V s V_s V s (Proposition 6 , a direct application of [8 ] ). This expresses F F F through the aliasing of the tail eigenfunctions onto V s V_s V 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 = s m=s m = s it is a set of Fekete points for V s V_s V s attaining the Hadamard bound (Proposition 11 ). The frame description also extends to every m ≥ s m \ge s m ≥ s . Tight sets are the equispaced points on S 1 \mathbb{S}^{1} S 1 and the regular tetrahedron on S 2 \mathbb{S}^{2} S 2 for s = 4 s=4 s = 4 (Corollaries 9 and 10). For larger s s s on S 2 \mathbb{S}^{2} S 2 , tightness with m = s m=s m = 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 F F F (Theorem 12 ). This accounts for the equispaced circle configurations and the Platonic solids. Criticality does not imply minimality, however, as the cube for s = 4 s=4 s = 4 and the dodecahedron for s = 9 s=9 s = 9 show, even though both are tight frames for those values of s s s . We also give a closed-form aliasing formula on the circle, which gives the value of F F F at equispaced landmarks for every m ≥ s m \ge s m ≥ s and decays super-exponentially in m m m (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 h h h . Below roughly 0.15 h 0.15h 0.15 h the position-dependent part of F F F becomes exponentially small and falls below the resolution of the optimizer. At the upper end two mechanisms intervene. Once the attainable minimum of F F F drops below about 10 − 9 10^{-9} 1 0 − 9 , it is poorly resolved by the subtraction s − tr ( ⋅ ) s-\operatorname{tr}(\cdot) s − tr ( ⋅ ) in double precision and absolute stopping tolerances trigger early. At larger bandwidths, beyond roughly 2.4 h 2.4h 2.4 h on the circle and somewhat less on the sphere, the landmark Gram matrix exceeds a condition number of 10 12 10^{12} 1 0 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} K − K in the trace, spectral or Frobenius norm and relate it to the choice of landmarks [2 , 17 , 18 , 3 ] . Choosing the best m m m 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 ] , k k k -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} K − K , not for the alignment of span { k ( ⋅ , z j ) } \operatorname{span}\{k(\cdot,z_j)\} span { k ( ⋅ , z j )} with an eigenspace of K K K .
The trace error is exactly ∫ P z 2 d μ \int P^2_z\,d\mu ∫ P z 2 d μ (§ 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 S 2 \mathbb{S}^{2} 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 S 2 \mathbb{S}^{2} 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 K K K a continuous, symmetric, strictly positive-definite kernel on Ω \Omega Ω with reproducing kernel Hilbert space (RKHS) H \mathcal{H} H . Write K x = K ( ⋅ , x ) K_x = K(\cdot,x) K x = K ( ⋅ , x ) , so that ⟨ f , K x ⟩ H = f ( x ) \langle f,K_x\rangle_{\mathcal{H}} = f(x) ⟨ f , K x ⟩ H = f ( x ) for all f ∈ H f \in\mathcal{H} f ∈ H (the reproducing property). The integral operator ( T K f ) ( x ) = ∫ K ( x , y ) f ( y ) d μ ( y ) (T_Kf)(x) = \int K(x,y)f(y)\,d\mu(y) ( T K f ) ( x ) = ∫ K ( x , y ) f ( y ) d μ ( y ) is compact, self-adjoint and positive on L 2 ( μ ) L^2(\mu) L 2 ( μ ) . We write its positive eigenvalues as λ 1 ≥ λ 2 ≥ ⋯ > 0 \lambda_1 \ge\lambda_2 \ge\cdots> 0 λ 1 ≥ λ 2 ≥ ⋯ > 0 , with L 2 ( μ ) L^2(\mu) L 2 ( μ ) -orthonormal eigenfunctions φ i \varphi_i φ 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 N N N of them when μ \mu μ is an empirical measure on N N N points. Each φ i \varphi_i φ i has the continuous representative φ i = λ i − 1 T K φ i \varphi_i = \lambda_i^{-1}T_K\varphi_i φ i = λ i − 1 T K φ 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. K ( x , y ) = i ∑ λ i φ i ( x ) φ i ( y ) , x , y ∈ supp μ .
The functions
ψ i : = λ i φ i , ⟨ ψ i , ψ k ⟩ H = δ i k , \psi_i := \sqrt{\lambda_i}\,\varphi_i,\qquad\langle\psi_i,\psi_k\rangle_{\mathcal{H}} = \delta_{ik}, ψ i := λ i φ i , ⟨ ψ i , ψ k ⟩ H = δ ik ,
are orthonormal in H \mathcal{H} H , and the reproducing property gives ⟨ ψ i , K x ⟩ H = ψ i ( x ) \langle\psi_i,K_x\rangle_{\mathcal{H}} = \psi_i(x) ⟨ ψ i , K x ⟩ H = ψ i ( x ) for every x ∈ Ω x \in\Omega x ∈ Ω .
The ψ i \psi_i ψ i need not span H \mathcal{H} H . Their closed span is the closure of the range of the covariance operator C C C of § 3.1 , and its orthogonal complement is
H 0 : = { f ∈ H : f = 0 μ -a.e. } = ker C . \mathcal{H}_0 := \{f \in\mathcal{H}: f = 0\ \ \mu\text{-a.e.}\} = \ker C. H 0 := { f ∈ H : f = 0 μ -a.e. } = ker C .
When supp μ = Ω \operatorname{supp}\mu= \Omega supp μ = Ω , continuity forces H 0 = { 0 } \mathcal{H}_0 = \{0\} H 0 = { 0 } , so { ψ i } \{\psi_i\} { ψ i } is an orthonormal basis of H \mathcal{H} H . For an empirical measure μ N \mu_N μ N , by contrast, H 0 \mathcal{H}_0 H 0 is infinite-dimensional, and the translate K z K_z K z of a point z z z off the data has a nonzero component in it. To treat both cases at once we complete { ψ i } \{\psi_i\} { ψ i } to an orthonormal basis of H \mathcal{H} H by appending an orthonormal basis of H 0 \mathcal{H}_0 H 0 , and we assign the eigenvalue λ i = 0 \lambda_i = 0 λ 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 λ 1 ≥ λ 2 ≥ ⋯ ≥ 0 is preserved. With this convention { ψ i } \{\psi_i\} { ψ i } is always an orthonormal basis of H \mathcal{H} H that diagonalizes C C C , the expansion
K x = ∑ i ψ i ( x ) ψ i K_x = \sum_i \psi_i(x)\,\psi_i K x = i ∑ ψ i ( x ) ψ i
holds for every x ∈ Ω x \in\Omega x ∈ Ω , and every sum over i i i below runs over the completed basis. Throughout we assume λ s > 0 \lambda_s > 0 λ s > 0 , so that the leading eigenspace V s V_s V s defined below consists of genuine eigenfunctions of T K T_K T K .
For the landmarks Z = { z 1 , … , z m } Z = \{z_1,\ldots,z_m\} Z = { z 1 , … , z m } with K Z Z = [ K ( z j , z l ) ] K_{ZZ} = [K(z_j,z_l)] K Z Z = [ K ( z j , z l )] invertible, define the two subspaces:
U Z = span { K z 1 , … , K z m } U_Z = \operatorname{span}\{K_{z_1},\ldots,K_{z_m}\} U Z = span { K z 1 , … , K z m } , with H \mathcal{H} H -orthogonal projector Π Z \Pi_Z Π Z .
V s = span { ψ 1 , … , ψ s } = span { φ 1 , … , φ s } V_s = \operatorname{span}\{\psi_1,\ldots,\psi_s\} = \operatorname{span}\{\varphi_1,\ldots,\varphi_s\} V s = span { ψ 1 , … , ψ s } = span { φ 1 , … , φ s } , with H \mathcal{H} H -orthogonal projector Q s Q_s Q s .
The Projector and the Power function
For landmarks Z = { z 1 , … , z m } Z = \{z_1,\ldots,z_m\} Z = { z 1 , … , z m } with K Z Z K_{ZZ} K Z Z invertible, the orthogonal projector onto the span of the kernel translates is the operator that interpolates a function at the landmarks using the translates K z j K_{z_j} K z j , namely
Π Z f = ∑ j , l = 1 m K z j ( K Z Z − 1 ) j l f ( z l ) = k Z ( ⋅ ) T K Z Z − 1 f ( 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)} Π Z f = j , l = 1 ∑ m K z j ( K Z Z − 1 ) j l f ( z l ) = k Z ( ⋅ ) T K Z Z − 1 f ( Z ) , (1)
where k Z ( ⋅ ) = ( K ( ⋅ , z j ) ) j = 1 m k_Z(\cdot) = (K(\cdot,z_j))_{j=1}^{m} k Z ( ⋅ ) = ( K ( ⋅ , z j ) ) j = 1 m and f ( Z ) = ( f ( z 1 ) , … , f ( z m ) ) T f(Z) = (f(z_1),\ldots,f(z_m))^\mathsf{T} f ( Z ) = ( f ( z 1 ) , … , f ( z m ) ) T . To see that this is the orthogonal projector onto U Z = span { K z 1 , … , K z m } U_Z = \operatorname{span}\{K_{z_1},\ldots,K_{z_m}\} U Z = span { K z 1 , … , K z m } , we check three properties. Its range lies in U Z U_Z U Z by construction. It fixes U Z U_Z U Z , because applying it to f = K z k f = K_{z_k} f = K z k gives f ( z l ) = K ( z l , z k ) = ( K Z Z ) l k f(z_l) = K(z_l,z_k) = (K_{ZZ})_{lk} f ( z l ) = K ( z l , z k ) = ( K Z Z ) l k and the coefficient sum collapses to ∑ j K z j ( K Z Z − 1 ) j l ( K Z Z ) l k = K z k \sum_j K_{z_j}(K_{ZZ}^{-1})_{jl}(K_{ZZ})_{lk} = K_{z_k} ∑ j K z j ( K Z Z − 1 ) j l ( K Z Z ) l k = K z k . And it is self-adjoint, since the reproducing property gives ⟨ g , Π Z f ⟩ H = g ( Z ) T K Z Z − 1 f ( Z ) \langle g,\Pi_Z f\rangle_{\mathcal{H}} = g(Z)^{\mathsf{T}}K_{ZZ}^{-1}f(Z) ⟨ g , Π Z f ⟩ H = g ( Z ) T K Z Z − 1 f ( Z ) , which is symmetric in f f f and g g g .
The same computation yields a useful formula for the size of a projected function. Because Π Z \Pi_Z Π Z is idempotent and self-adjoint, ∥ Π Z f ∥ H 2 = ⟨ f , Π Z f ⟩ H \|\Pi_Zf\|_{\mathcal{H}}^2 = \langle f,\Pi_Zf\rangle_{\mathcal{H}} ∥ Π Z f ∥ H 2 = ⟨ f , Π Z f ⟩ H , and applying ⟨ f , K z j ⟩ H = f ( z j ) \langle f,K_{z_j}\rangle_{\mathcal{H}} = f(z_j) ⟨ f , K z j ⟩ H = f ( z j ) to (1) turns this into
∥ Π Z f ∥ H 2 = f ( Z ) T K Z Z − 1 f ( Z ) . (2) \|\Pi_Zf\|_{\mathcal{H}}^2 = f(Z)^{\mathsf{T}}K_{ZZ}^{-1}f(Z). \tag*{(2)} ∥ Π Z f ∥ H 2 = f ( Z ) T K Z Z − 1 f ( Z ) . (2)
In other words, the portion of f f f captured by the landmark space depends only on the values of f f f at the landmarks, weighted by the inverse Gram matrix. This identity does most of the work in what follows, because it lets us express every projected norm through finite-dimensional matrices.
The power function arises when we apply this to the feature vectors themselves. We define P Z ( x ) 2 : = ∥ K x − Π Z K x ∥ H 2 P_Z(x)^2 := \|K_x-\Pi_ZK_x\|_{\mathcal{H}}^2 P Z ( x ) 2 := ∥ K x − Π Z K x ∥ H 2 , which measures how far the translate at x x x lies from the landmark space. Pythagoras gives ∥ u − Π u ∥ 2 = ∥ u ∥ 2 − ∥ Π u ∥ 2 \|u-\Pi u\|^2 = \|u\|^2-\|\Pi u\|^2 ∥ u − Π u ∥ 2 = ∥ u ∥ 2 − ∥Π u ∥ 2 , and combining this with ∥ K x ∥ H 2 = K ( x , x ) \|K_x\|_{\mathcal{H}}^2 = K(x,x) ∥ K x ∥ H 2 = K ( x , x ) and (2) applied to f = K x f=K_x f = K x (for which f ( Z ) = k Z ( x ) f(Z)=k_Z(x) f ( Z ) = k Z ( x ) ) produces
P Z ( x ) 2 = K ( x , x ) − k Z ( x ) T K Z Z − 1 k Z ( x ) . (3) P_Z(x)^2 = K(x,x)-k_Z(x)^{\mathsf{T}}K_{ZZ}^{-1}k_Z(x). \tag*{(3)} P Z ( x ) 2 = K ( x , x ) − k Z ( x ) T K Z Z − 1 k Z ( x ) . (3)
This is the classical power function formula [5 ] . It is also the diagonal of the Nyström residual K − K ^ K-\widehat{K} K − K , where K ^ ( x , y ) = k Z ( x ) T K Z Z − 1 k Z ( y ) \widehat{K}(x,y)=k_Z(x)^{\mathsf{T}}K_{ZZ}^{-1}k_Z(y) K ( x , y ) = k Z ( x ) T K Z Z − 1 k Z ( y ) , so the same object serves as the pointwise error of kernel interpolation and as the pointwise error of the Nyström approximation. The remainder of the paper compares two ways of summarizing the quality of Z Z Z . One integrates P Z 2 P_Z^2 P Z 2 over the domain (§ 3.1 ), and the other measures the alignment of U Z U_Z U Z with V s V_s V s directly through the spectral alignment F ( Z ) F(Z) F ( Z ) (§ 3 ).
The Spectral Alignment functional
Our goal is to choose landmarks so that U Z U_Z U Z contains V s V_s V s as closely as possible, so we first need a measure of how far V s V_s V s lies from the landmark space. When m = s m=s m = s the two subspaces have the same dimension and the Hilbert–Schmidt distance between their projectors is a natural choice. When m > s m>s m > s that distance can never vanish, because the subspaces differ in dimension, so we measure instead how much of V s V_s V s is missing from U Z U_Z U Z . Expanding the square and using Π Z 2 = Π Z \Pi_Z^2=\Pi_Z Π Z 2 = Π Z , Q s 2 = Q s Q_s^2=Q_s Q s 2 = Q s , and cyclicity of the trace gives
∥ Π Z − Q s ∥ H S 2 = tr ( ( Π Z − Q s ) 2 ) = tr Π Z + tr Q s − 2 tr ( Π Z Q s ) = m + s − 2 tr ( Π Z Q s ) , \|\Pi_Z-Q_s\|_{HS}^2 = \operatorname{tr}\left((\Pi_Z-Q_s)^2\right) = \operatorname{tr}\Pi_Z+\operatorname{tr}Q_s-2\operatorname{tr}(\Pi_ZQ_s) = m+s-2\operatorname{tr}(\Pi_ZQ_s), ∥ Π Z − Q s ∥ H S 2 = tr ( ( Π Z − Q s ) 2 ) = tr Π Z + tr Q s − 2 tr ( Π Z Q s ) = m + s − 2 tr ( Π Z Q s ) ,
since tr Π Z = m \operatorname{tr}\Pi_Z=m tr Π Z = m and tr Q s = s \operatorname{tr}Q_s=s tr Q s = s . We define the spectral alignment functional to be
F ( Z ) : = s − tr ( Π Z Q s ) . F(Z):=s-\operatorname{tr}(\Pi_ZQ_s). F ( Z ) := s − tr ( Π Z Q s ) .
When m > s m>s m > s this quantity is related to the projector distance by 1 2 ∥ Π Z − Q s ∥ H S 2 = F ( Z ) + m − s 2 \frac{1}{2}\|\Pi_Z-Q_s\|_{HS}^2=F(Z)+\frac{m-s}{2} 2 1 ∥ Π Z − Q s ∥ H S 2 = F ( Z ) + 2 m − s . The two coincide when m = s m=s m = s , and for m > s m>s m > s the alignment F F F removes the constant offset that the dimension mismatch forces on the Hilbert–Schmidt distance.
The geometric meaning follows from the principal angles. The operator Q s Π Z Q s Q_s\Pi_ZQ_s Q s Π Z Q s restricted to V s V_s V s has eigenvalues cos 2 θ j \cos^2\theta_j cos 2 θ j for j = 1 , … , s j=1,\ldots,s j = 1 , … , s , where θ 1 , … , θ s \theta_1,\ldots,\theta_s θ 1 , … , θ s are the principal angles between V s V_s V s and U Z U_Z U Z . Hence tr ( Π Z Q s ) = ∑ j cos 2 θ j \operatorname{tr}(\Pi_ZQ_s)=\sum_j\cos^2\theta_j tr ( Π Z Q s ) = ∑ j cos 2 θ j and
F ( Z ) = ∑ j = 1 s sin 2 θ j ∈ [ 0 , s ] . F(Z)=\sum_{j=1}^{s}\sin^2\theta_j\in[0,s]. F ( Z ) = j = 1 ∑ s sin 2 θ j ∈ [ 0 , s ] .
This is the standard chordal Grassmannian distance, squared, between V s V_s V s and the subspace of U Z U_Z U Z closest to it. It vanishes exactly when V s ⊆ U Z V_s\subseteq U_Z V s ⊆ U Z , which for m = s m=s m = s means U Z = V s U_Z=V_s U Z = V s .
To understand where the spectral alignment comes from, it helps to track how much of each eigenvector lies inside the landmark space. We define the overlap coefficients a i : = ∥ Π Z ψ i ∥ H 2 ∈ [ 0 , 1 ] a_i:=\|\Pi_Z\psi_i\|_{\mathcal{H}}^2\in[0,1] a i := ∥ Π Z ψ i ∥ H 2 ∈ [ 0 , 1 ] . Applying (2) with f = ψ i f=\psi_i f = ψ i and using ψ i = λ i φ i \psi_i=\sqrt{\lambda_i}\varphi_i ψ i = λ i φ i gives
a i = ψ i ( Z ) T K Z Z − 1 ψ i ( Z ) = tr ( K Z Z − 1 λ i φ i ( Z ) φ i ( Z ) T ) . (4) a_i=\psi_i(Z)^{\mathsf{T}}K_{ZZ}^{-1}\psi_i(Z)=\operatorname{tr}\left(K_{ZZ}^{-1}\lambda_i\varphi_i(Z)\varphi_i(Z)^{\mathsf{T}}\right). \tag*{(4)} a i = ψ i ( Z ) T K Z Z − 1 ψ i ( Z ) = tr ( K Z Z − 1 λ i φ i ( Z ) φ i ( Z ) T ) . (4)
We can think of V s V_s V s as the target subspace and U Z U_Z U Z as the one we are able to build from landmarks. Each ψ i \psi_i ψ i with i ≤ s i\le s i ≤ s should lie entirely inside U Z U_Z U Z , and the amount by which it fails is 1 − a i 1-a_i 1 − a i . Computing tr ( Π Z Q s ) \operatorname{tr}(\Pi_ZQ_s) tr ( Π Z Q s ) in the orthonormal basis { ψ i } \{\psi_i\} { ψ i } , and noting that Q s ψ i = ψ i Q_s\psi_i=\psi_i Q s ψ i = ψ i for i ≤ s i\le s i ≤ s and Q s ψ i = 0 Q_s\psi_i=0 Q s ψ i = 0 otherwise, we find tr ( Π Z Q s ) = ∑ i ≥ 1 ⟨ ψ i , Π Z Q s ψ i ⟩ = ∑ i ≤ s ⟨ ψ i , Π Z ψ i ⟩ = ∑ i ≤ s a i \operatorname{tr}(\Pi_ZQ_s)=\sum_{i\ge1}\langle\psi_i,\Pi_ZQ_s\psi_i\rangle=\sum_{i\le s}\langle\psi_i,\Pi_Z\psi_i\rangle=\sum_{i\le s}a_i tr ( Π Z Q s ) = ∑ i ≥ 1 ⟨ ψ i , Π Z Q s ψ i ⟩ = ∑ i ≤ s ⟨ ψ i , Π Z ψ i ⟩ = ∑ i ≤ s a i . The spectral alignment is therefore the total leakage from V s V_s V s ,
F ( Z ) = s − ∑ i ≤ s a i = ∑ i ≤ s ( 1 − a i ) . F(Z)=s-\sum_{i\le s}a_i=\sum_{i\le s}(1-a_i). F ( Z ) = s − i ≤ s ∑ a i = i ≤ s ∑ ( 1 − a i ) .
The same coefficients also reveal a second interpretation. Taking the trace of Π Z \Pi_Z Π Z in the basis { ψ i } \{\psi_i\} { ψ i } gives ∑ i ≥ 1 a i = tr Π Z = m \sum_{i\ge1}a_i=\operatorname{tr}\Pi_Z=m ∑ i ≥ 1 a i = tr Π Z = m , and subtracting the first leaves
∑ i > s a i = m − s + F ( Z ) . (5) \sum_{i>s}a_i=m-s+F(Z). \tag*{(5)} i > s ∑ a i = m − s + F ( Z ) . (5)
The tail V s ⊥ V_s^\perp V s ⊥ therefore receives at least m − s m-s m − s units of mass, since the landmark space has m m m dimensions and only s s s of them are needed to cover V s V_s V s . The alignment F ( Z ) F(Z) F ( Z ) is exactly the amount by which the tail mass exceeds this unavoidable minimum, and it is simultaneously the mass of V s V_s V s that leaks out of U Z U_Z U Z . When m = s m=s m = s the minimum is zero and the two views coincide, so F ( Z ) = ∑ i > s a i F(Z)=\sum_{i>s}a_i F ( Z ) = ∑ i > s a i , that is, the mass that V s V_s V s loses is exactly the mass that the tail gains. The first view asks whether the landmarks can reproduce the leading eigenfunctions, while the second asks how much tail mass the landmark space holds beyond the unavoidable m − s m-s m − s .
The overlap coefficients can be summed in closed form without computing any eigenfunctions explicitly. We split the kernel into its truncated and tail parts,
K ( s ) = ∑ i ≤ s λ i ϕ i ⊗ ϕ i , T ( s ) = K − K ( s ) = ∑ i > s λ i ϕ i ⊗ ϕ i . K^{(s)}=\sum_{i\le s}\lambda_i\phi_i\otimes\phi_i,\qquad T^{(s)}=K-K^{(s)}=\sum_{i>s}\lambda_i\phi_i\otimes\phi_i. K ( s ) = i ≤ s ∑ λ i ϕ i ⊗ ϕ i , T ( s ) = K − K ( s ) = i > s ∑ λ i ϕ i ⊗ ϕ i .
and write K Z Z ( s ) K^{(s)}_{ZZ} K Z Z ( s ) and T Z Z ( s ) T^{(s)}_{ZZ} T Z Z ( s ) for their m × m m\times m m × m landmark matrices, so that K Z Z = K Z Z ( s ) + T Z Z ( s ) K_{ZZ}=K^{(s)}_{ZZ}+T^{(s)}_{ZZ} K Z Z = K Z Z ( s ) + T Z Z ( s ) . Equivalently, K ( s ) = ∑ i ≤ s ψ i ⊗ ψ i K^{(s)}=\sum_{i\le s}\psi_i\otimes\psi_i K ( s ) = ∑ i ≤ s ψ i ⊗ ψ i and T ( s ) = ∑ i > s ψ i ⊗ ψ i T^{(s)}=\sum_{i>s}\psi_i\otimes\psi_i T ( s ) = ∑ i > s ψ i ⊗ ψ i are the reproducing kernels of V s V_s V s and of V s ⊥ V_s^\perp V s ⊥ in H \mathcal{H} H , so both are positive semidefinite. Summing (4) over i ≤ s i\le s i ≤ s gives ∑ i ≤ s a i = tr ( K Z Z − 1 K Z Z ( s ) ) \sum_{i\le s}a_i=\operatorname{tr}(K_{ZZ}^{-1}K^{(s)}_{ZZ}) ∑ i ≤ s a i = tr ( K Z Z − 1 K Z Z ( s ) ) , and therefore
F ( Z ) = s − tr ( K Z Z − 1 K Z Z ( s ) ) . (6) F(Z)=s-\operatorname{tr}\left(K_{ZZ}^{-1}K^{(s)}_{ZZ}\right). \tag*{(6)} F ( Z ) = s − tr ( K Z Z − 1 K Z Z ( s ) ) . (6)
Since tr ( K Z Z − 1 K Z Z ) = m \operatorname{tr}(K_{ZZ}^{-1}K_{ZZ})=m tr ( K Z Z − 1 K Z Z ) = m , the same quantity can be written in terms of the tail kernel as
F ( Z ) = tr ( K Z Z − 1 T Z Z ( s ) ) − ( m − s ) . (7) F(Z)=\operatorname{tr}\left(K_{ZZ}^{-1}T^{(s)}_{ZZ}\right)-(m-s). \tag*{(7)} F ( Z ) = tr ( K Z Z − 1 T Z Z ( s ) ) − ( m − s ) . (7)
When m = s m=s m = s the correction vanishes and F ( Z ) = tr ( K Z Z − 1 T Z Z ( s ) ) F(Z)=\operatorname{tr}(K_{ZZ}^{-1}T^{(s)}_{ZZ}) F ( Z ) = tr ( K Z Z − 1 T Z Z ( s ) ) , whose nonnegativity is immediate because K Z Z − 1 ≻ 0 K_{ZZ}^{-1}\succ0 K Z Z − 1 ≻ 0 and T Z Z ( s ) ⪰ 0 T^{(s)}_{ZZ}\succeq0 T Z Z ( s ) ⪰ 0 . A quick sanity check at s = m = 1 s=m=1 s = m = 1 confirms the formulas. For a single landmark z z z we have cos 2 θ = ⟨ ψ 1 , K z ⟩ H 2 / ∥ K z ∥ H 2 = λ 1 ϕ 1 ( z ) 2 / K ( z , z ) \cos^2\theta=\langle\psi_1,K_z\rangle_{\mathcal{H}}^2/\lVert K_z\rVert_{\mathcal{H}}^2=\lambda_1\phi_1(z)^2/K(z,z) cos 2 θ = ⟨ ψ 1 , K z ⟩ H 2 / ∥ K z ∥ H 2 = λ 1 ϕ 1 ( z ) 2 / K ( z , z ) , so F = 1 − λ 1 ϕ 1 ( z ) 2 / K ( z , z ) = T ( 1 ) ( z , z ) / K ( z , z ) F=1-\lambda_1\phi_1(z)^2/K(z,z)=T^{(1)}(z,z)/K(z,z) F = 1 − λ 1 ϕ 1 ( z ) 2 / K ( z , z ) = T ( 1 ) ( z , z ) / K ( z , z ) , which is exactly what (7) gives when K Z Z = K ( z , z ) K_{ZZ}=K(z,z) K Z Z = K ( z , z ) .
Remark 1 (Basis invariance). Only K Z Z ( s ) = Ψ Ψ T K^{(s)}_{ZZ}=\Psi\Psi^{\mathsf{T}} K Z Z ( s ) = Ψ Ψ T enters (6) , where Ψ j i = ψ i ( z j ) \Psi_{ji}=\psi_i(z_j) Ψ j i = ψ i ( z j ) . Hence F F F does not depend on which orthonormal basis of V s V_s V s is used. This matters in two places. Inside a degenerate eigenspace any rotation of the basis is allowed, and on the circle and the sphere (Appendix § 9 .§ 1 ) the kernel K ( s ) K^{(s)} K ( s ) can be written down without ever forming a basis.
The formulas also tell us when the alignment can vanish. For m = s m=s m = s we have F ( Z ) = 0 F(Z)=0 F ( Z ) = 0 if and only if T Z Z ( s ) = 0 T^{(s)}_{ZZ}=0 T Z Z ( s ) = 0 , and since T Z Z ( s ) T^{(s)}_{ZZ} T Z Z ( s ) is positive semidefinite this forces its diagonal to vanish. That requires ψ i ( z j ) = 0 \psi_i(z_j)=0 ψ i ( z j ) = 0 for every i > s i>s i > s and every j j j , so the landmarks would have to be common zeros of all the tail eigenfunctions. For a kernel with an infinite spectrum this common-zero condition is not expected to hold in general, so min Z F ( Z ) > 0 \min_Z F(Z)>0 min Z F ( Z ) > 0 generically and the problem is one of minimization rather than exact solution. For m > s m>s m > s the condition for F ( Z ) = 0 F(Z)=0 F ( Z ) = 0 is instead V s ⊂ U Z V_s\subset U_Z V s ⊂ U Z , which requires every leading eigenfunction to be an exact combination of m m m kernel translates. This is also generically impossible for an infinite spectrum, but unlike the case m = s m=s m = s it can be approached closely. The aliasing formula of Theorem 13 shows that on the circle F F F decays super-exponentially in m m m at equispaced landmarks.
The closed form is also practical for data. Let μ \mu μ be the empirical measure on N N N points, with kernel matrix K N K_N K N and rank-s s s truncation K N ( s ) = U s Σ s U s T K_N^{(s)} = U_s\Sigma_sU_s^{\mathsf{T}} K N ( s ) = U s Σ s U s T . For landmark set Z Z Z with ∣ Z ∣ = m ≥ s |Z| = m \ge s ∣ Z ∣ = m ≥ s , the spectral alignment is F ( Z ) = s − tr ( ( K N ) Z Z ( K N ( s ) ) Z Z ) F(Z) = s - \operatorname{tr}\left((K_N)_{ZZ}(K_N^{(s)})_{ZZ}\right) F ( Z ) = s − tr ( ( K N ) Z Z ( K N ( s ) ) Z Z ) . The N − 1 N^{-1} N − 1 normalizations of λ i \lambda_i λ i and φ i \varphi_i φ i cancel in this expression, so no rescaling is needed. Evaluating it requires only the top s s s eigenpairs of K N K_N K N and the two m × m m \times m m × m submatrices for each candidate set. This form assumes that the landmarks are data points. Landmarks off the data are handled in § 5 through the Nyström extension, and there the completed basis of § 2.1 is essential, because the translates K z j K_{z_j} K z j then have components in H 0 \mathcal{H}_0 H 0 .
The integrated power function as a weighted distance
The power function (3) is a pointwise quantity, and to compare it with the alignment functional we need a single number that summarizes it over the domain. The natural choice is its integral against μ \mu μ , which equals the Nyström trace error. To express this integral in the same Hilbert space language as the previous section, we introduce the covariance operator C : H → H C:\mathcal{H}\to\mathcal{H} C : H → H ,
C f = ∫ f ( x ) K x d μ ( x ) = ∫ ⟨ f , K x ⟩ H K x d μ ( x ) , that is, C = ∫ K x ⊗ K x d μ ( x ) . Cf = \int f(x)K_x\,d\mu(x) = \int\langle f,K_x\rangle_{\mathcal{H}}K_x\,d\mu(x), \qquad\text{that is,}\qquad C = \int K_x\otimes K_x\,d\mu(x). C f = ∫ f ( x ) K x d μ ( x ) = ∫ ⟨ f , K x ⟩ H K x d μ ( x ) , that is, C = ∫ K x ⊗ K x d μ ( x ) .
Each integrand K x ⊗ K x K_x\otimes K_x K x ⊗ K x is a rank-one operator, so C C C is the average of these operators and plays the role of the second-moment operator of the feature vectors K x ∈ H K_x\in\mathcal{H} K x ∈ H . Its role is the same as that of 1 N ∑ n x n x n T \frac{1}{N}\sum_n x_nx_n^{\mathsf{T}} N 1 ∑ n x n x n T for vectors in R d \mathbb{R}^d R d . The integral is a Bochner integral in H \mathcal{H} H , and it exists because ∥ K x ∥ H 2 = K ( x , x ) \lVert K_x\rVert_{\mathcal{H}}^2 = K(x,x) ∥ K x ∥ H 2 = K ( x , x ) is bounded for a continuous kernel on a compact space and μ \mu μ is finite.
Evaluating C f Cf C f at a point y y y gives ( C f ) ( y ) = ∫ K ( y , x ) f ( x ) d μ ( x ) (Cf)(y) = \int K(y,x)f(x)\,d\mu(x) ( C f ) ( y ) = ∫ K ( y , x ) f ( x ) d μ ( x ) , which is the integral operator T K T_K T K whose eigenpairs define the Mercer expansion, so C C C is simply T K T_K T K viewed as an operator on H \mathcal{H} H . Its matrix in the completed orthonormal basis { ψ i } \{\psi_i\} { ψ i } is diagonal, since
⟨ ψ i , C ψ k ⟩ H = ∫ ψ i ( x ) ψ k ( x ) d μ ( x ) = λ i λ k δ i k = λ i δ i k . \langle\psi_i,C\psi_k\rangle_{\mathcal{H}} = \int\psi_i(x)\psi_k(x)\,d\mu(x) = \sqrt{\lambda_i\lambda_k}\,\delta_{ik} = \lambda_i\delta_{ik}. ⟨ ψ i , C ψ k ⟩ H = ∫ ψ i ( x ) ψ k ( x ) d μ ( x ) = λ i λ k δ ik = λ i δ ik .
Therefore C = ∑ i λ i ψ i ⊗ ψ i C = \sum_i \lambda_i\,\psi_i\otimes\psi_i C = ∑ i λ i ψ i ⊗ ψ i and tr C = ∑ i λ i = ∫ K ( x , x ) d μ ( x ) \operatorname{tr} C = \sum_i\lambda_i = \int K(x,x)\,d\mu(x) tr C = ∑ i λ i = ∫ K ( x , x ) d μ ( x ) .
With C C C in hand, the integrated power function becomes a trace. Writing P Z ( x ) 2 = ⟨ K x , ( I − Π Z ) K x ⟩ H = tr ( ( I − Π Z ) K x ⊗ K x ) P_Z(x)^2 = \langle K_x,(I-\Pi_Z)K_x\rangle_{\mathcal{H}} = \operatorname{tr}\left((I-\Pi_Z)K_x\otimes K_x\right) P Z ( x ) 2 = ⟨ K x , ( I − Π Z ) K x ⟩ H = tr ( ( I − Π Z ) K x ⊗ K x ) and integrating over x x x , we obtain
∫ P Z 2 d μ = tr ( ( I − Π Z ) C ) = ∥ ( I − Π Z ) C 1 / 2 ∥ H S 2 . \int P_Z^2\,d\mu= \operatorname{tr}\left((I-\Pi_Z)C\right) = \left\lVert(I-\Pi_Z)C^{1/2}\right\rVert_{\mathrm{HS}}^2. ∫ P Z 2 d μ = tr ( ( I − Π Z ) C ) = ( I − Π Z ) C 1/2 HS 2 .
This identity shows that the integrated power function is a Hilbert–Schmidt distance, but between the operator C 1 / 2 C^{1/2} C 1/2 and its projection onto U Z U_Z U Z . Since C 1 / 2 C^{1/2} C 1/2 is not a projector (it has full rank and weights each eigen-direction by λ i \sqrt{\lambda_i} λ i ), this is not a distance between U Z U_Z U Z and any fixed s s s -dimensional subspace. Our spectral alignment F ( Z ) = ∥ ( I − Π Z ) Q s ∥ H S 2 F(Z)=\left\lVert(I-\Pi_Z)Q_s\right\rVert_{\mathrm{HS}}^2 F ( Z ) = ∥ ( I − Π Z ) Q s ∥ HS 2 has the same form, but with the spectral projector Q s Q_s Q s in place of C 1 / 2 C^{1/2} C 1/2 . The difference becomes explicit when we evaluate the trace in the eigenbasis. Since ⟨ ψ i , ( I − Π Z ) ψ i ⟩ H = 1 − a i \langle\psi_i,(I-\Pi_Z)\psi_i\rangle_{\mathcal{H}}=1-a_i ⟨ ψ i , ( I − Π Z ) ψ i ⟩ H = 1 − a i , we find
∫ P Z 2 d μ = ∑ i ≥ 1 λ i ( 1 − a i ) . (8) \int P_Z^2\,d\mu= \sum_{i\ge1}\lambda_i(1-a_i). \tag*{(8)} ∫ P Z 2 d μ = i ≥ 1 ∑ λ i ( 1 − a i ) . (8)
The integrated power function thus weights the unexplained mass of each eigenvector by its eigenvalue, whereas the alignment counts every leading eigenvector equally.
Equation (8) also gives a lower bound that no choice of landmarks can beat. The coefficients satisfy 0 ≤ a i ≤ 1 0\le a_i\le1 0 ≤ a i ≤ 1 and ∑ i a i = m \sum_i a_i=m ∑ i a i = m , so maximizing ∑ i λ i a i \sum_i\lambda_i a_i ∑ i λ i a i under these constraints places a i = 1 a_i=1 a i = 1 on the m m m largest eigenvalues, which gives ∑ i ≤ m λ i \sum_{i\le m}\lambda_i ∑ i ≤ m λ i by the Ky Fan maximum principle [37 ] . Consequently
∫ P Z 2 d μ ≥ ∑ i > m λ i . (9) \int P_Z^2\,d\mu\ge\sum_{i>m}\lambda_i. \tag*{(9)} ∫ P Z 2 d μ ≥ i > m ∑ λ i . (9)
with equality if and only if U Z = span { ψ 1 , … , ψ m } U_Z=\operatorname{span}\{\psi_1,\ldots,\psi_m\} U Z = span { ψ 1 , … , ψ m } , provided λ m > λ m + 1 \lambda_m>\lambda_{m+1} λ m > λ m + 1 . The right-hand side is the error of the best rank-m m m approximation, so (9) says that m m m landmarks cannot do better than the truncated Mercer expansion of the same rank.
Because our target is the rank-s s s eigenspace, it is natural to measure the quality of a landmark set against the rank-s s s benchmark and define the excess E ( Z ) : = ∫ P Z 2 d μ − ∑ i > s λ i E(Z) := \int P_Z^2\,\mathrm{d}\mu- \sum_{i>s}\lambda_i E ( Z ) := ∫ P Z 2 d μ − ∑ i > s λ i . When m = s m=s m = s the bound (9) makes E ( Z ) ≥ 0 E(Z) \ge0 E ( Z ) ≥ 0 . When m > s m>s m > s the excess can be negative, since extra landmarks can capture part of the tail, but (9) still gives E ( Z ) ≥ − ∑ s < i ≤ m λ i E(Z) \ge-\sum_{s<i\le m}\lambda_i E ( Z ) ≥ − ∑ s < i ≤ m λ i . Splitting (8) at index s s s gives, for every m ≥ s m \ge s m ≥ s ,
E ( Z ) = ∑ i ≤ s λ i ( 1 − a i ) − ∑ i > s λ i a i = tr ( ( Q s − Π Z ) C ) . (10) E(Z) = \sum_{i\le s}\lambda_i(1-a_i)-\sum_{i>s}\lambda_i a_i=\operatorname{tr}\left((Q_s-\Pi_Z)C\right). \tag*{(10)} E ( Z ) = i ≤ s ∑ λ i ( 1 − a i ) − i > s ∑ λ i a i = tr ( ( Q s − Π Z ) C ) . (10)
Comparing this with the alignment functional shows that the same leakage numbers appear in both quantities. The spectral alignment is F ( Z ) = ∑ i ≤ s ( 1 − a i ) F(Z)=\sum_{i\le s}(1-a_i) F ( Z ) = ∑ i ≤ s ( 1 − a i ) , and the tail coefficients satisfy ∑ i > s a i = m − s + F ( Z ) \sum_{i>s}a_i=m-s+F(Z) ∑ i > s a i = m − s + F ( Z ) by (5) . The excess, however, weights these numbers by the eigenvalues and gives the two groups opposite signs. Leakage out of the leading eigenspace is penalized in proportion to the large eigenvalues λ i \lambda_i λ i with i ≤ s i\le s i ≤ s , while mass of the tail captured by U Z U_Z U Z offsets it in proportion to the small eigenvalues with i > s i>s i > s . This opposition is what prevents a small excess from forcing a small alignment when the spectrum has no gap, and the extra tail mass m − s m-s m − s that the landmark space must hold when m > s m>s m > s enters the bound of the next section.
The Sandwich Bound
The spectral alignment F F F and the excess E E E are built from the same leakage numbers, so it is natural to ask how tightly they constrain one another. To compare them, write b i = 1 − a i ≥ 0 b_i=1-a_i\ge0 b i = 1 − a i ≥ 0 for i ≤ s i\le s i ≤ s . The definition of F F F gives ∑ i ≤ s b i = F ( Z ) \sum_{i\le s}b_i=F(Z) ∑ i ≤ s b i = F ( Z ) , and (5) gives ∑ i > s a i = m − s + F ( Z ) \sum_{i>s}a_i=m-s+F(Z) ∑ i > s a i = m − s + F ( Z ) . In this notation (10) reads
E = ∑ i ≤ s λ i b i − ∑ i > s λ i a i . E=\sum_{i\le s}\lambda_i b_i-\sum_{i>s}\lambda_i a_i. E = i ≤ s ∑ λ i b i − i > s ∑ λ i a i .
The eigenvalues are ordered, so λ i ≥ λ s \lambda_i\ge\lambda_s λ i ≥ λ s for i ≤ s i\le s i ≤ s , and the first sum is at least λ s F \lambda_sF λ s F . For the second sum we also use a i ≤ 1 a_i\le1 a i ≤ 1 . The tail mass ∑ i > s a i = m − s + F \sum_{i>s}a_i=m-s+F ∑ i > s a i = m − s + F splits into the part on the indices s < i ≤ m s<i\le m s < i ≤ m and the part on i > m i>m i > m , where every eigenvalue is at most λ m + 1 \lambda_{m+1} λ m + 1 . Hence
∑ i > s λ i a i ≤ ∑ s < i ≤ m ( λ i − λ m + 1 ) a i + λ m + 1 ( m − s + F ) ≤ ∑ s < i ≤ m λ i + λ m + 1 F . \sum_{i>s}\lambda_i a_i\le\sum_{s<i\le m}(\lambda_i-\lambda_{m+1})a_i+\lambda_{m+1}(m-s+F)\le\sum_{s<i\le m}\lambda_i+\lambda_{m+1}F. i > s ∑ λ i a i ≤ s < i ≤ m ∑ ( λ i − λ m + 1 ) a i + λ m + 1 ( m − s + F ) ≤ s < i ≤ m ∑ λ i + λ m + 1 F .
where the last step uses a i ≤ 1 a_i\le1 a i ≤ 1 and λ i ≥ λ m + 1 \lambda_i\ge\lambda_{m+1} λ i ≥ λ m + 1 for i ≤ m i\le m i ≤ m . The extremal case fills the directions ψ s + 1 , … , ψ m \psi_{s+1},\ldots,\psi_m ψ s + 1 , … , ψ m completely and places the leaked mass F F F on ψ m + 1 \psi_{m+1} ψ m + 1 . Combining the two sums yields the lower estimate
E ≥ λ s F − ∑ s < i ≤ m λ i − λ m + 1 F = ( λ s − λ m + 1 ) F − ∑ s < i ≤ m λ i . E\ge\lambda_sF-\sum_{s<i\le m}\lambda_i-\lambda_{m+1}F=(\lambda_s-\lambda_{m+1})F-\sum_{s<i\le m}\lambda_i. E ≥ λ s F − s < i ≤ m ∑ λ i − λ m + 1 F = ( λ s − λ m + 1 ) F − s < i ≤ m ∑ λ i .
For the upper estimate, we may discard the nonpositive second sum and use λ i ≤ λ 1 \lambda_i\le\lambda_1 λ i ≤ λ 1 in the first, which gives E ≤ ∑ i ≤ s λ i b i ≤ λ 1 F E\le\sum_{i\le s}\lambda_i b_i\le\lambda_1F E ≤ ∑ i ≤ s λ i b i ≤ λ 1 F . Together these two estimates constitute the following result.
Theorem 2 (Sandwich bound). For m ≥ s m\ge s m ≥ s landmarks with K Z Z K_{ZZ} K Z Z invertible,
( λ s − λ m + 1 ) F ( Z ) − ∑ s < i ≤ m λ i ≤ ∫ P Z 2 d μ − ∑ i > s λ i ≤ λ 1 F ( Z ) . (\lambda_s-\lambda_{m+1})F(Z)-\sum_{s<i\le m}\lambda_i\le\int P_Z^2\,\mathrm{d}\mu-\sum_{i>s}\lambda_i\le\lambda_1F(Z). ( λ s − λ m + 1 ) F ( Z ) − s < i ≤ m ∑ λ i ≤ ∫ P Z 2 d μ − i > s ∑ λ i ≤ λ 1 F ( Z ) . In particular, for m = s m=s m = s the bound reads ( λ s − λ s + 1 ) F ( Z ) ≤ E ( Z ) ≤ λ 1 F ( Z ) (\lambda_s-\lambda_{s+1})F(Z)\le E(Z)\le\lambda_1F(Z) ( λ s − λ s + 1 ) F ( Z ) ≤ E ( Z ) ≤ λ 1 F ( Z ) . Since ∑ s < i ≤ m λ i ≤ ( m − s ) λ s + 1 \sum_{s<i\le m}\lambda_i\le(m-s)\lambda_{s+1} ∑ s < i ≤ m λ i ≤ ( m − s ) λ s + 1 and λ m + 1 ≤ λ s + 1 \lambda_{m+1}\le\lambda_{s+1} λ m + 1 ≤ λ s + 1 , the lower bound also implies the simpler estimate E ( Z ) ≥ ( λ s − λ s + 1 ) F ( Z ) − λ s + 1 ( m − s ) E(Z)\ge(\lambda_s-\lambda_{s+1})F(Z)-\lambda_{s+1}(m-s) E ( Z ) ≥ ( λ s − λ s + 1 ) F ( Z ) − λ s + 1 ( m − s ) .
The upper inequality says that driving F F F to zero always keeps the trace error within λ 1 F \lambda_1F λ 1 F of the best rank-s s s approximation, which is the sense in which small leakage implies a near-optimal Nyström approximation. The lower inequality runs in the opposite direction and is informative only when the spectrum has a gap. For m = s m=s m = s , a small Nyström trace excess implies F ≤ E / ( λ s − λ s + 1 ) F\le E/(\lambda_s-\lambda_{s+1}) F ≤ E / ( λ s − λ s + 1 ) , so alignment follows from near-optimal trace error only if λ s − λ s + 1 \lambda_s-\lambda_{s+1} λ s − λ s + 1 is not small. In a gap, U Z U_Z U Z is not far from V s V_s V s , while ∫ P Z 2 d μ \int P_Z^2\,\mathrm{d}\mu ∫ P Z 2 d μ is nearly optimal. This is the Davis–Kahan phenomenon [7 ] , in which the stability of an eigenspace under perturbation scales inversely with the gap to the next eigenvalue.
For m > s m>s m > s the lower bound carries the additional correction ∑ s < i ≤ m λ i \sum_{s<i\le m}\lambda_i ∑ s < i ≤ m λ i . It arises because the landmark space has m − s m-s m − s dimensions beyond those needed to cover V s V_s V s , and these can absorb the eigen-directions
ψ s + 1 , … , ψ m \psi_{s+1},\ldots,\psi_m ψ s + 1 , … , ψ m , each of which offsets the excess by λ i \lambda_i λ i . At F = 0 F=0 F = 0 the bound reduces to E ≥ − ∑ s < i ≤ m λ i E\ge-\sum_{s<i\le m}\lambda_i E ≥ − ∑ s < i ≤ m λ i , which is exactly the Ky Fan bound (9) .
A concrete case shows that, for m = s m=s m = s , the constant λ s − λ s + 1 \lambda_s-\lambda_{s+1} λ s − λ s + 1 in the lower bound cannot be improved by any bound that holds for all s s s -dimensional subspaces of H \mathcal{H} H . Suppose U Z U_Z U Z differs from V s V_s V s by a single rotation through an angle θ \theta θ in the plane spanned by ψ s \psi_s ψ s and ψ s + 1 \psi_{s+1} ψ s + 1 , so that U Z U_Z U Z contains cos θ ψ s + sin θ ψ s + 1 \cos\theta\,\psi_s+\sin\theta\,\psi_{s+1} cos θ ψ s + sin θ ψ s + 1 in place of ψ s \psi_s ψ s and the rest of V s V_s V s is unchanged. The overlap coefficients then satisfy a s = cos 2 θ a_s=\cos^2\theta a s = cos 2 θ and a s + 1 = sin 2 θ a_{s+1}=\sin^2\theta a s + 1 = sin 2 θ , with all other a i a_i a i unchanged. It follows that F = 1 − a s = sin 2 θ F=1-a_s=\sin^2\theta F = 1 − a s = sin 2 θ and E = λ s sin 2 θ − λ s + 1 sin 2 θ = ( λ s − λ s + 1 ) sin 2 θ E=\lambda_s\sin^2\theta-\lambda_{s+1}\sin^2\theta=(\lambda_s-\lambda_{s+1})\sin^2\theta E = λ s sin 2 θ − λ s + 1 sin 2 θ = ( λ s − λ s + 1 ) sin 2 θ , so E = ( λ s − λ s + 1 ) F E=(\lambda_s-\lambda_{s+1})F E = ( λ s − λ s + 1 ) F holds with equality. At θ = 90 ∘ \theta=90^\circ θ = 9 0 ∘ the subspace U Z U_Z U Z has swapped ψ s \psi_s ψ s for ψ s + 1 \psi_{s+1} ψ s + 1 and F = 1 F=1 F = 1 , as large as it can be for a one-direction swap. If the gap λ s − λ s + 1 = ε \lambda_s-\lambda_{s+1}=\varepsilon λ s − λ s + 1 = ε is tiny, however, the excess is only E = ε E=\varepsilon E = ε . The trace error is then almost optimal even though the subspace has lost an entire leading direction, so near-optimality of ∫ P Z 2 d μ \int P_Z^2\,d\mu ∫ P Z 2 d μ says almost nothing about alignment with V s V_s V s .
It is worth separating this near-degenerate situation from the exactly degenerate one. If λ s = λ s + 1 \lambda_s=\lambda_{s+1} λ s = λ s + 1 , the subspace V s V_s V s is not uniquely defined and F F F depends on an arbitrary choice. The swapped subspace in the example above is then an equally valid top-s s s eigenspace, and E = 0 E=0 E = 0 correctly reports that it is optimal. The difficulty lies in the near-degenerate case, where V s V_s V s is well defined but any rotation within the cluster costs only ε sin 2 θ \varepsilon\sin^2\theta ε sin 2 θ in excess. The practical conclusion is that small F F F always forces a small E E E , but a small E E E forces a small F F F only when there is a gap between λ s \lambda_s λ s and λ s + 1 \lambda_{s+1} λ s + 1 . For landmark determination this means that minimizing ∫ P Z 2 d μ \int P_Z^2\,d\mu ∫ P Z 2 d μ is a legitimate proxy for subspace alignment only when the spectrum has a clear gap at s s s .
The same leakage numbers also give direct estimates for the integrated power function itself, which are useful when comparing with the rank-s s s benchmark. They follow from (8) directly rather than from Theorem 2 .
Corollary 3 (Bounds for m ≥ s m\ge s m ≥ s ). For m ≥ s m\ge s m ≥ s landmarks with K Z Z K_{ZZ} K Z Z invertible,
λ s F ( Z ) ≤ ∫ P Z 2 d μ ≤ ∑ i > s λ i + λ 1 F ( Z ) , ∫ P Z 2 d μ ≥ ∑ i > m λ i . \lambda_s F(Z)\le\int P_Z^2\,d\mu\le\sum_{i>s}\lambda_i+\lambda_1F(Z),\qquad\int P_Z^2\,d\mu\ge\sum_{i>m}\lambda_i. λ s F ( Z ) ≤ ∫ P Z 2 d μ ≤ i > s ∑ λ i + λ 1 F ( Z ) , ∫ P Z 2 d μ ≥ i > m ∑ λ i .
Evenly Spaced Minimizers
In every experiment we ran on S 1 \mathbb{S}^1 S 1 and S 2 \mathbb{S}^2 S 2 the minimizers of F F F turned out to be evenly spread, even though nothing in the objective asks for this. This section explains the phenomenon by connecting F F F to three classical families of evenly spread point sets: minimal positive cubature rules and tight spherical designs, unit-norm tight frames, and Fekete points. Most of the ingredients are known, and we cite them as such. What is new is the link between these objects and the spectral alignment, together with the quantitative bound of Theorem 7 and the closed form of Theorem 13 .
The argument has three steps, all valid on any compact homogeneous space with an invariant kernel. First, for m = s m=s m = s , we write F F F through the tangents of the principal angles between U Z U_Z U Z and V s V_s V s . This yields an upper bound controlled by the conditioning of the eigenfunction sampling matrix, and the bound is minimized exactly by tight sampling sets . Second, we identify tight sampling sets with minimal equal-weight cubature rules, with unit-norm tight frames, and with Fekete points. The tight-frame description extends to every m ≥ s m\ge s m ≥ s . Third, we recall that sufficiently symmetric configurations are critical points of every invariant objective, and hence of F F F . Facts specific to the circle and the sphere are collected in Appendix § 9 .
The Homogeneous Setting
We say that ( Ω , μ , K , G ) (\Omega,\mu,K,G) ( Ω , μ , K , G ) is a homogeneous setting if Ω \Omega Ω is a compact Hausdorff space (for instance a compact Riemannian manifold), G G G is a group of homeomorphisms of Ω \Omega Ω that acts transitively, μ \mu μ is a G G G -invariant Borel probability measure, and K K K is a continuous, symmetric, strictly positive-definite kernel with K ( g x , g y ) = K ( x , y ) K(gx,gy)=K(x,y) K ( g x , g y ) = K ( x , y ) for all g ∈ G g\in G g ∈ G and x , y ∈ Ω x,y\in\Omega x , y ∈ Ω .
Examples include S d \mathbb{S}^d S d and R P d \mathbb{R}\mathbb{P}^d R P d with G G G the orthogonal group, flat tori with G G G the translations, compact Lie groups acting on themselves by left translation, and Grassmann and Stiefel manifolds. Two families of kernels satisfy the hypotheses on every such space. The first is the heat kernel of an invariant Riemannian metric, and the second is the ambient Gaussian K ( x , y ) = exp ( − ∥ x − y ∥ 2 / 2 ℓ 2 ) K(x,y)=\exp(-\lVert x-y\rVert^2/2\ell^2) K ( x , y ) = exp ( − ∥ x − y ∥ 2 /2 ℓ 2 ) restricted to an orbit Ω = G ⋅ x 0 ⊂ R n \Omega=G\cdot x_0\subset\mathbb{R}^n Ω = G ⋅ x 0 ⊂ R n . of an orthogonal representation of a compact group. The latter is invariant because G G G acts by orthogonal maps, and it is strictly positive definite because the Euclidean Gaussian is. The Gaussian kernels on S 1 S^1 S 1 and S 2 S^2 S 2 used in our experiments are of the second type, and their exact Mercer expansions are recorded in Appendix § 9 .§ 1 . By contrast, the Gaussian of the geodesic distance is positive definite for all bandwidths only when the manifold is isometric to a Euclidean space [38 ] . This excludes not only curved spaces but also the circle and flat tori, which are flat but compact, so the geodesic Gaussian should not be used on any of the compact homogeneous spaces considered here.
For g ∈ G g \in G g ∈ G define ( π g f ) ( x ) = f ( g − 1 x ) (\pi_g f)(x) = f(g^{-1}x) ( π g f ) ( x ) = f ( g − 1 x ) . Invariance of μ \mu μ makes π g \pi_g π g an orthogonal operator on L 2 ( μ ) L^2(\mu) L 2 ( μ ) , and invariance of K K K makes it commute with the integral operator T K T_K T K . Hence every eigenspace E λ E_\lambda E λ of T K T_K T K is π g \pi_g π g -invariant. Eigenfunctions with λ > 0 \lambda> 0 λ > 0 are continuous, because φ = λ − 1 T K φ \varphi= \lambda^{-1}T_K\varphi φ = λ − 1 T K φ . By transitivity, supp μ = Ω \operatorname{supp}\mu= \Omega supp μ = Ω , so continuous functions that agree μ \mu μ -almost everywhere agree everywhere. We write k s ( x , y ) = ∑ i ≤ s φ i ( x ) φ i ( y ) k_s(x,y) = \sum_{i\le s}\varphi_i(x)\varphi_i(y) k s ( x , y ) = ∑ i ≤ s φ i ( x ) φ i ( y ) for the reproducing kernel of V s V_s V s in L 2 ( μ ) L^2(\mu) L 2 ( μ ) . Like every reproducing kernel of a finite-dimensional space, it does not depend on the choice of orthonormal basis [39 ] . We call V s V_s V s G G G -invariant if π g V s = V s \pi_gV_s = V_s π g V s = V s for all g g g . This holds automatically when λ s > λ s + 1 \lambda_s > \lambda_{s+1} λ s > λ s + 1 , because V s V_s V s is then a direct sum of full eigenspaces.
The main consequence of homogeneity used below is that the diagonals of the relevant kernels are constant. For Laplace eigenspaces on compact homogeneous Riemannian manifolds this is the addition formula of Ginè [40 ] . Two further uses are more elementary. Theorem 8 uses that μ \mu μ has full support, which follows from transitivity, and Theorem 12 uses the group action directly.
Lemma 4 (Constant diagonal; cf. [40 ] ). In a homogeneous setting, suppose V s V_s V s is G G G -invariant. Then for every x ∈ Ω x \in\Omega x ∈ Ω
k s ( x , x ) = s , K ( x , x ) = ∑ i ≥ 1 λ i , K ( s ) ( x , x ) = ∑ i ≤ s λ i , T ( s ) ( x , x ) = τ s : = ∑ i > s λ i . k_s(x,x)=s,\qquad K(x,x)=\sum_{i\ge1}\lambda_i,\qquad K^{(s)}(x,x)=\sum_{i\le s}\lambda_i,\qquad T^{(s)}(x,x)=\tau_s:=\sum_{i>s}\lambda_i. k s ( x , x ) = s , K ( x , x ) = i ≥ 1 ∑ λ i , K ( s ) ( x , x ) = i ≤ s ∑ λ i , T ( s ) ( x , x ) = τ s := i > s ∑ λ i . Proof. Let W W W be a finite-dimensional π g \pi_g π g -invariant subspace of continuous functions with L 2 ( μ ) L^2(\mu) L 2 ( μ ) -orthonormal basis w = ( w 1 , … , w d ) w=(w_1,\ldots,w_d) w = ( w 1 , … , w d ) and reproducing kernel k W ( x , y ) = ∑ r w r ( x ) w r ( y ) k_W(x,y)=\sum_r w_r(x)w_r(y) k W ( x , y ) = ∑ r w r ( x ) w r ( y ) . Since μ \mu μ is G G G -invariant, π g w \pi_gw π g w is again an orthonormal basis of W W W , and basis independence of the reproducing kernel gives k W ( g − 1 x , g − 1 y ) = k W ( x , y ) k_W(g^{-1}x,g^{-1}y)=k_W(x,y) k W ( g − 1 x , g − 1 y ) = k W ( x , y ) for μ ⊗ μ \mu\otimes\mu μ ⊗ μ -almost every ( x , y ) (x,y) ( x , y ) . Both sides are continuous and μ \mu μ has full support, so the identity holds for all x , y ∈ Ω x,y\in\Omega x , y ∈ Ω . Apply this to W = V s W=V_s W = V s for invariance of k s k_s k s . For K ( s ) K^{(s)} K ( s ) , note that V s V_s V s is spanned by eigenfunctions, so V s = ⨁ λ ( V s ∩ E λ ) V_s=\bigoplus_\lambda(V_s\cap E_\lambda) V s = ⨁ λ ( V s ∩ E λ ) , and each summand is π g \pi_g π g -invariant as an intersection of invariant subspaces. Choosing the basis of V s V_s V s adapted to this decomposition, which is allowed by Remark 1, gives K ( s ) = ∑ λ λ k V s ∩ E λ K^{(s)}=\sum_\lambda\lambda k_{V_s\cap E_\lambda} K ( s ) = ∑ λ λ k V s ∩ E λ , a sum of invariant kernels. K K K is invariant by hypothesis, and T ( s ) = K − K ( s ) T^{(s)}=K-K^{(s)} T ( s ) = K − K ( s ) . An invariant kernel k k k has constant diagonal, since k ( g x , g x ) = k ( x , x ) k(gx,gx)=k(x,x) k ( g x , g x ) = k ( x , x ) and G G G acts transitively. The constants follow by integrating against μ \mu μ , i.e. we have ∫ k s ( x , x ) d μ ( x ) = ∑ i ≤ s ∥ φ i ∥ 2 2 = s \int k_s(x,x)\,d\mu(x)=\sum_{i\le s}\|\varphi_i\|_2^2=s ∫ k s ( x , x ) d μ ( x ) = ∑ i ≤ s ∥ φ i ∥ 2 2 = s and ∫ K ( s ) ( x , x ) d μ ( x ) = ∑ i ≤ s λ i \int K^{(s)}(x,x)\,d\mu(x)=\sum_{i\le s}\lambda_i ∫ K ( s ) ( x , x ) d μ ( x ) = ∑ i ≤ s λ i , while ∫ K ( x , x ) d μ ( x ) = ∑ i λ i \int K(x,x)\,d\mu(x)=\sum_i\lambda_i ∫ K ( x , x ) d μ ( x ) = ∑ i λ i by Mercer’s theorem. □ \square □
Remark 5. For the Gaussian kernels on S 1 S^1 S 1 and S 2 S^2 S 2 we have K ( x , x ) = 1 K(x,x)=1 K ( x , x ) = 1 , so τ s = 1 − ∑ i ≤ s λ i \tau_s=1-\sum_{i\le s}\lambda_i τ s = 1 − ∑ i ≤ s λ i , in agreement with Propositions 15 and 16 .
Tight Sampling Sets
Let Φ ∈ R m × s \Phi\in\mathbb{R}^{m\times s} Φ ∈ R m × s be the eigenfunction sampling matrix with entries Φ j i = φ i ( z j ) \Phi_{ji}=\varphi_i(z_j) Φ j i = φ i ( z j ) for i ≤ s i\le s i ≤ s , and let Λ = diag ( λ 1 , … , λ s ) \Lambda=\operatorname{diag}(\lambda_1,\ldots,\lambda_s) Λ = diag ( λ 1 , … , λ s ) , so that K Z Z ( s ) = Φ Λ Φ T K^{(s)}_{ZZ}=\Phi\Lambda\Phi^\mathsf{T} K Z Z ( s ) = ΦΛ Φ T . We first take m = s m=s m = s , so that Φ \Phi Φ is square.
In the orthonormal basis { ψ i } \{\psi_i\} { ψ i } of H \mathcal{H} H , the translate K z j K_{z_j} K z j has leading coordinates λ i φ i ( z j ) \sqrt{\lambda_i}\varphi_i(z_j) λ i φ i ( z j ) for i ≤ s i\le s i ≤ s , which form the j j j -th column of D : = Λ 1 / 2 Φ T D:=\Lambda^{1/2}\Phi^\mathsf{T} D := Λ 1/2 Φ T . Its tail coordinates, taken in the completed basis of § 2.1 , form the j j j -th column of an operator D ⊥ : R m → V s ⊥ D_\perp:\mathbb{R}^m\to V_s^\perp D ⊥ : R m → V s ⊥ with D ⊥ ∗ D ⊥ = T Z Z ( s ) D_\perp^*D_\perp=T^{(s)}_{ZZ} D ⊥ ∗ D ⊥ = T Z Z ( s ) . Hence K Z Z = D T D + D ⊥ ∗ D ⊥ K_{ZZ}=D^\mathsf{T}D+D_\perp^*D_\perp K Z Z = D T D + D ⊥ ∗ D ⊥ . When D D D is invertible, the tangents of the principal angles between U Z = range [ D ; D ⊥ ] U_Z=\operatorname{range}[D;D_\perp] U Z = range [ D ; D ⊥ ] and V s V_s V s are the singular values of D ⊥ D − 1 D_\perp D^{-1} D ⊥ D − 1 [8 Thm. 3.1] . Invertibility of D D D means that no principal angle equals π / 2 \pi/2 π /2 . Squaring these tangents gives the following reformulation of the closed form (7) .
Proposition 6 (Tangent form of the alignment). Let m = s m=s m = s , suppose Φ \Phi Φ is invertible, and set
R Z : = ( D ⊥ D − 1 ) ∗ ( D ⊥ D − 1 ) = Λ − 1 / 2 Φ − 1 T Z Z ( s ) Φ − T Λ − 1 / 2 ⪰ 0. R_Z:=(D_\perp D^{-1})^*(D_\perp D^{-1})=\Lambda^{-1/2}\Phi^{-1}T^{(s)}_{ZZ}\Phi^{-\mathsf{T}}\Lambda^{-1/2}\succeq0. R Z := ( D ⊥ D − 1 ) ∗ ( D ⊥ D − 1 ) = Λ − 1/2 Φ − 1 T Z Z ( s ) Φ − T Λ − 1/2 ⪰ 0.
The eigenvalues of R Z R_Z R Z are tan 2 θ 1 , … , tan 2 θ s \tan^2\theta_1,\ldots,\tan^2\theta_s tan 2 θ 1 , … , tan 2 θ s , where θ j \theta_j θ j are the principal angles between U Z U_Z U Z and V s V_s V s . Consequently
F ( Z ) = ∑ j = 1 s sin 2 θ j = tr ( ( I + R Z ) − 1 R Z ) , tr R Z 1 + ∥ R Z ∥ ≤ F ( Z ) ≤ tr R Z . F(Z)=\sum_{j=1}^{s}\sin^2\theta_j=\operatorname{tr}\left((I+R_Z)^{-1}R_Z\right),\qquad\frac{\operatorname{tr}R_Z}{1+\lVert R_Z\rVert}\leq F(Z)\leq\operatorname{tr}R_Z. F ( Z ) = j = 1 ∑ s sin 2 θ j = tr ( ( I + R Z ) − 1 R Z ) , 1 + ∥ R Z ∥ tr R Z ≤ F ( Z ) ≤ tr R Z .
Moreover
tr R Z = ∑ j tan 2 θ j = ∑ i > s λ i ∥ Λ − 1 / 2 c i ∥ 2 2 , c i : = Φ − 1 φ i ( Z ) , \operatorname{tr}R_Z=\sum_j\tan^2\theta_j=\sum_{i>s}\lambda_i\left\lVert\Lambda^{-1/2}c_i\right\rVert_2^2,\qquad c_i:=\Phi^{-1}\varphi_i(Z), tr R Z = j ∑ tan 2 θ j = i > s ∑ λ i Λ − 1/2 c i 2 2 , c i := Φ − 1 φ i ( Z ) ,
where c i c_i c i is the coefficient vector of the interpolant in V s V_s V s of the tail eigenfunction φ i \varphi_i φ i from its values at Z Z Z . We call c i c_i c i the aliasing coefficients of φ i \varphi_i φ i onto V s V_s V s .
Proof. The spectral statement is [8 Thm. 3.1] applied to the bases above, and sin 2 = tan 2 / ( 1 + tan 2 ) \sin^2=\tan^2/(1+\tan^2) sin 2 = tan 2 / ( 1 + tan 2 ) gives the formula for F F F , consistent with § 3 . Alternatively, K Z Z = D T ( I + R Z ) D K_{ZZ}=D^\mathsf{T}(I+R_Z)D K Z Z = D T ( I + R Z ) D and (7) give F = tr ( K Z Z − 1 T Z Z ( s ) ) = tr ( ( I + R Z ) − 1 R Z ) F=\operatorname{tr}(K_{ZZ}^{-1}T_{ZZ}^{(s)})=\operatorname{tr}((I+R_Z)^{-1}R_Z) F = tr ( K Z Z − 1 T Z Z ( s ) ) = tr (( I + R Z ) − 1 R Z ) directly. The bounds follow from t / ( 1 + ∥ R Z ∥ ) ≤ t / ( 1 + t ) ≤ t t/(1+\lVert R_Z\rVert)\leq t/(1+t)\leq t t / ( 1 + ∥ R Z ∥) ≤ t / ( 1 + t ) ≤ t for t t t an eigenvalue of R Z R_Z R Z . The trace identity follows from expanding T Z Z ( s ) = ∑ i > s λ i φ i ( Z ) φ i ( Z ) T T_{ZZ}^{(s)}=\sum_{i>s}\lambda_i\varphi_i(Z)\varphi_i(Z)^\mathsf{T} T Z Z ( s ) = ∑ i > s λ i φ i ( Z ) φ i ( Z ) T .
The spectral alignment is therefore squeezed between two saturating functions of the weighted aliasing energy tr R Z = ∥ tan Θ ∥ F 2 \operatorname{tr}R_Z=\lVert\tan\Theta\rVert_F^2 tr R Z = ∥ tan Θ ∥ F 2 , and it is close to tr R Z \operatorname{tr}R_Z tr R Z whenever all principal angles are small. The contribution that is specific to landmark selection is the last identity. Landmarks are good when the tail eigenfunctions, as seen through their samples at Z Z Z , look like low-energy elements of V s V_s V s . The next result turns this into a statement about which sampling matrices are best. The key is that ∥ Φ ∥ F 2 \lVert\Phi\rVert_F^2 ∥ Φ ∥ F 2 is fixed by Lemma 4 .
Theorem 7 (Tight sampling sets minimize the bound). In a homogeneous setting with V s V_s V s G G G -invariant and m = s m=s m = s , let Φ ∈ R s × s \Phi\in\mathbb{R}^{s\times s} Φ ∈ R s × s , Φ j i = φ i ( z j ) \Phi_{ji}=\varphi_i(z_j) Φ j i = φ i ( z j ) , let σ min ( Φ ) \sigma_{\min}(\Phi) σ m i n ( Φ ) be its smallest singular value, and set τ s : = ∑ i > s λ i \tau_s:=\sum_{i>s}\lambda_i τ s := ∑ i > s λ i . Then
F ( Z ) ≤ tr R Z ≤ s τ s λ s σ min ( Φ ) 2 , and σ min ( Φ ) 2 ≤ s . F(Z)\leq\operatorname{tr}R_Z\leq\frac{s\tau_s}{\lambda_s\sigma_{\min}(\Phi)^2},\qquad\text{and}\qquad\sigma_{\min}(\Phi)^2\leq s. F ( Z ) ≤ tr R Z ≤ λ s σ m i n ( Φ ) 2 s τ s , and σ m i n ( Φ ) 2 ≤ s . Hence the bound is at least τ s / λ s \tau_s/\lambda_s τ s / λ s , with equality if and only if Φ T Φ = s I \Phi^\mathsf{T}\Phi=sI Φ T Φ = s I . We call such Z Z Z a tight sampling set.
Proof. If Φ \Phi Φ is singular then σ min = 0 \sigma_{\min}=0 σ m i n = 0 and there is nothing to prove. Otherwise D = Λ 1 / 2 Φ T D=\Lambda^{1/2}\Phi^\mathsf{T} D = Λ 1/2 Φ T is invertible, so Proposition 6 applies and we have
tr R Z = ∑ i > s λ i ∥ Λ − 1 / 2 Φ − 1 φ i ( Z ) ∥ 2 2 . \operatorname{tr}R_Z=\sum_{i>s}\lambda_i\left\lVert\Lambda^{-1/2}\Phi^{-1}\varphi_i(Z)\right\rVert_2^2. tr R Z = i > s ∑ λ i Λ − 1/2 Φ − 1 φ i ( Z ) 2 2 .
The matrix Λ − 1 / 2 \Lambda^{-1/2} Λ − 1/2 is diagonal with entries λ k − 1 / 2 ≤ λ s − 1 / 2 \lambda_k^{-1/2}\leq\lambda_s^{-1/2} λ k − 1/2 ≤ λ s − 1/2 for k ≤ s k\leq s k ≤ s , because the eigenvalues are ordered. Also ∥ Φ − 1 v ∥ 2 ≤ ∥ v ∥ 2 / σ min ( Φ ) \lVert\Phi^{-1}v\rVert_2\leq\lVert v\rVert_2/\sigma_{\min}(\Phi) ∥ Φ − 1 v ∥ 2 ≤ ∥ v ∥ 2 / σ m i n ( Φ ) . Therefore
∥ Λ − 1 / 2 Φ − 1 φ i ( Z ) ∥ 2 2 ≤ ∥ φ i ( Z ) ∥ 2 2 λ s σ min ( Φ ) 2 , \left\lVert\Lambda^{-1/2}\Phi^{-1}\varphi_i(Z)\right\rVert_2^2\leq\frac{\lVert\varphi_i(Z)\rVert_2^2}{\lambda_s\sigma_{\min}(\Phi)^2}, Λ − 1/2 Φ − 1 φ i ( Z ) 2 2 ≤ λ s σ m i n ( Φ ) 2 ∥ φ i ( Z ) ∥ 2 2 ,
and summing,
tr R Z ≤ 1 λ s σ min ( Φ ) 2 ∑ i > s λ i ∥ φ i ( Z ) ∥ 2 2 = tr T Z Z ( s ) λ s σ min ( Φ ) 2 . \operatorname{tr}R_Z\leq\frac{1}{\lambda_s\sigma_{\min}(\Phi)^2}\sum_{i>s}\lambda_i\lVert\varphi_i(Z)\rVert_2^2=\frac{\operatorname{tr}T_{ZZ}^{(s)}}{\lambda_s\sigma_{\min}(\Phi)^2}. tr R Z ≤ λ s σ m i n ( Φ ) 2 1 i > s ∑ λ i ∥ φ i ( Z ) ∥ 2 2 = λ s σ m i n ( Φ ) 2 tr T Z Z ( s ) .
By Lemma 4 , T ( s ) ( z j , z j ) = τ s T^{(s)}(z_j,z_j)=\tau_s T ( s ) ( z j , z j ) = τ s for every j j j , so tr T Z Z ( s ) = s τ s \operatorname{tr}T_{ZZ}^{(s)}=s\tau_s tr T Z Z ( s ) = s τ s and thus
tr R Z ≤ s τ s λ s σ min ( Φ ) 2 . \operatorname{tr}R_Z\leq\frac{s\tau_s}{\lambda_s\sigma_{\min}(\Phi)^2}. tr R Z ≤ λ s σ m i n ( Φ ) 2 s τ s .
Let σ 1 , … , σ s \sigma_1,\ldots,\sigma_s σ 1 , … , σ s be the singular values of Φ \Phi Φ . Then ∥ Φ ∥ F 2 = ∑ k = 1 s σ k 2 \lVert\Phi\rVert_F^2=\sum_{k=1}^{s}\sigma_k^2 ∥ Φ ∥ F 2 = ∑ k = 1 s σ k 2 . Computing the same quantity entrywise and applying Lemma 4 to k s k_s k s ,
∥ Φ ∥ F 2 = ∑ j = 1 s ∑ i ≤ s φ i ( z j ) 2 = ∑ j = 1 s k s ( z j , z j ) = s ⋅ s = s 2 . \lVert\Phi\rVert_F^2=\sum_{j=1}^{s}\sum_{i\leq s}\varphi_i(z_j)^2=\sum_{j=1}^{s}k_s(z_j,z_j)=s\cdot s=s^2. ∥ Φ ∥ F 2 = j = 1 ∑ s i ≤ s ∑ φ i ( z j ) 2 = j = 1 ∑ s k s ( z j , z j ) = s ⋅ s = s 2 .
The smallest of s s s nonnegative numbers is at most their mean, so
σ min ( Φ ) 2 ≤ 1 s ∑ k = 1 s σ k 2 = s 2 s = s . \sigma_{\min}(\Phi)^2 \le\frac{1}{s}\sum_{k=1}^{s}\sigma_k^2 = \frac{s^2}{s}=s. σ m i n ( Φ ) 2 ≤ s 1 k = 1 ∑ s σ k 2 = s s 2 = s .
Equality holds if and only if σ k 2 = s \sigma_k^2=s σ k 2 = s for all k k k , that is, if and only if Φ T Φ = s I \Phi^{\mathsf T}\Phi=sI Φ T Φ = s I .
The word “tight” is chosen deliberately. Below we show that tight sampling sets are tight spherical designs on S 2 \mathbb{S}^2 S 2 and unit-norm tight frames in R s \mathbb{R}^s R s . Their first intrinsic description comes from cubature. Write V s ⋅ V s = span { f g : f , g ∈ V s } V_s\cdot V_s=\operatorname{span}\{fg:f,g\in V_s\} V s ⋅ V s = span { f g : f , g ∈ V s } . This space contains the constants, because ∑ i ≤ s φ i 2 = s \sum_{i\le s}\varphi_i^2=s ∑ i ≤ s φ i 2 = s .
Theorem 8 (Tight sampling sets are minimal cubature rules). In a homogeneous setting with V s V_s V s G G G -invariant, let Z = { z 1 , … , z s } Z=\{z_1,\ldots,z_s\} Z = { z 1 , … , z s } consist of s s s distinct points. The following are equivalent.
(i) Φ T Φ = s I \Phi^{\mathsf T}\Phi=sI Φ T Φ = s I , so Z Z Z is tight.
(ii) k s ( z j , z l ) = 0 k_s(z_j,z_l)=0 k s ( z j , z l ) = 0 for all j ≠ l j\ne l j = l . Equivalently, the functions k s ( ⋅ , z j ) k_s(\cdot,z_j) k s ( ⋅ , z j ) are pairwise orthogonal in L 2 ( μ ) L^2(\mu) L 2 ( μ ) .
(iii) The equal-weight rule 1 s ∑ j f ( z j ) \frac{1}{s}\sum_j f(z_j) s 1 ∑ j f ( z j ) integrates every f ∈ V s ⋅ V s f\in V_s\cdot V_s f ∈ V s ⋅ V s exactly.
(iv) Some rule ∑ j w j f ( z j ) \sum_j w_jf(z_j) ∑ j w j f ( z j ) with positive weights integrates every f ∈ V s ⋅ V s f\in V_s\cdot V_s f ∈ V s ⋅ V s exactly.
(v) The Lagrange basis of V s V_s V s at Z Z Z exists and is ℓ j = k s ( ⋅ , z j ) / s \ell_j=k_s(\cdot,z_j)/s ℓ j = k s ( ⋅ , z j ) / s .
The theorem is the homogeneous-space version of the classical theory of minimal (Gaussian) cubature [9 , 10 ] . A positive rule exact on V ⋅ V V\cdot V V ⋅ V needs at least dim V \dim V dim V nodes [9 ] , without any homogeneity assumption. A rule attaining this bound has nodes at which the reproducing kernel of V V V vanishes pairwise, and weights equal to the Christoffel numbers 1 / k V ( z j , z j ) 1/k_V(z_j,z_j) 1/ k V ( z j , z j ) . The only new ingredient is Lemma 4, which makes the Christoffel function constant and hence forces equal weights 1 / s 1/s 1/ s . Tight sampling sets are therefore exactly the minimal positive cubature rules for V s ⋅ V s V_s\cdot V_s V s ⋅ V s . On S 2 \mathbb{S}^2 S 2 with s = ( M + 1 ) 2 s=(M+1)^2 s = ( M + 1 ) 2 , the space V s ⋅ V s V_s\cdot V_s V s ⋅ V s consists of the polynomials of degree at most 2 M 2M 2 M , so tight sampling sets are exactly the tight spherical 2 M 2M 2 M -designs, namely those attaining the Delsarte–Goethals–Seidel (Fisher-type) bound ( M + 1 ) 2 (M+1)^2 ( M + 1 ) 2 [29 ] .
Proof. (i)⇔ \Leftrightarrow ⇔ (ii): Φ \Phi Φ is square, so Φ T Φ = s I \Phi^{\mathsf T}\Phi=sI Φ T Φ = s I if and only if Φ Φ T = s I \Phi\Phi^{\mathsf T}=sI Φ Φ T = s I , and ( Φ Φ T ) j l = k s ( z j , z l ) (\Phi\Phi^{\mathsf T})_{jl}=k_s(z_j,z_l) ( Φ Φ T ) j l = k s ( z j , z l ) with diagonal s s s . (i)⇔ \Leftrightarrow ⇔ (iii): ( Φ T Φ ) i k = ∑ j ( φ i φ k ) ( z j ) (\Phi^{\mathsf T}\Phi)_{ik}=\sum_j(\varphi_i\varphi_k)(z_j) ( Φ T Φ ) ik = ∑ j ( φ i φ k ) ( z j ) while ∫ φ i φ k d μ = δ i k \int\varphi_i\varphi_k\,\mathrm{d}\mu=\delta_{ik} ∫ φ i φ k d μ = δ ik . (iii)⇒ \Rightarrow ⇒ (iv) is immediate. For (iv)⇒ \Rightarrow ⇒ (ii) we follow the classical argument [10 ] . Exactness on f 2 f^2 f 2 shows that f ∈ V s f\in V_s f ∈ V s vanishing on Z Z Z is zero, so the Lagrange basis ℓ j \ell_j ℓ j exists (evaluation at Z Z Z is bijective on V s V_s V s ). Exactness on ℓ j ℓ k \ell_j\ell_k ℓ j ℓ k gives ∫ ℓ j ℓ k d μ = w j δ j k \int\ell_j\ell_k\,\mathrm{d}\mu=w_j\delta_{jk} ∫ ℓ j ℓ k d μ = w j δ j k , so { ℓ j / w j } \{\ell_j/\sqrt{w_j}\} { ℓ j / w j } is orthonormal and k s k_s k s in this basis is k s ( x , y ) = ∑ j ℓ j ( x ) ℓ j ( y ) / w j k_s(x,y)=\sum_j\ell_j(x)\ell_j(y)/w_j k s ( x , y ) = ∑ j ℓ j ( x ) ℓ j ( y ) / w j . Hence k s ( z r , z t ) = δ r t / w r k_s(z_r,z_t)=\delta_{rt}/w_r k s ( z r , z t ) = δ r t / w r and Lemma 4 then forces w r = 1 / s w_r=1/s w r = 1/ s . (ii)⇔ \Leftrightarrow ⇔ (v): k s ( ⋅ , z j ) / s ∈ V s k_s(\cdot,z_j)/s\in V_s k s ( ⋅ , z j ) / s ∈ V s takes the value δ j l \delta_{jl} δ j l at z l z_l z l if and only if (ii) holds.
Theorem 8 reduces the existence of tight sets on each space to a concrete question. Are there s s s points at which the single invariant function k s k_s k s vanishes pairwise? Once k s k_s k s is written down, condition (ii) settles the model cases:
Corollary 9 (Circle). On S 1 \mathbb{S}^1 S 1 with s = 2 M + 1 s=2M+1 s = 2 M + 1 , the tight sampling sets are exactly the rotations of the s s s equispaced points. Equivalently, the rotated trapezoidal rules are the only s s s -node positive rules exact for trigonometric polynomials of degree 2 M 2M 2 M .
Corollary 10 (Sphere). On S 2 \mathbb{S}^2 S 2 with s = ( M + 1 ) 2 s=(M+1)^2 s = ( M + 1 ) 2 , the addition theorem gives k s ( x , y ) = p M ( x ⋅ y ) k_s(x,y)=p_M(x\cdot y) k s ( x , y ) = p M ( x ⋅ y ) with p M = ∑ n = 0 M ( 2 n + 1 ) P n = ( M + 1 ) P M ( 1 , 0 ) p_M=\sum_{n=0}^{M}(2n+1)P_n=(M+1)P_M^{(1,0)} p M = ∑ n = 0 M ( 2 n + 1 ) P n = ( M + 1 ) P M ( 1 , 0 ) . So Z Z Z is tight if and only if its pairwise inner products are roots of p M p_M p M . This is the Delsarte–Goethals–Seidel description of tight 2 M 2M 2 M -designs [29 ] . Tight 2 M 2M 2 M -designs on S 2 \mathbb{S}^2 S 2 exist only for M = 1 M=1 M = 1 [11 , 41 ] , where p 1 ( t ) = 1 + 3 t p_1(t)=1+3t p 1 ( t ) = 1 + 3 t and the tight sets are exactly the regular tetrahedra. For s ≥ 9 s\ge9 s ≥ 9 no tight sampling set exists.
For s ≥ 9 s\ge9 s ≥ 9 on the sphere, the optimizer must therefore trade tightness against the aliasing weights. Table 3 confirms numerically that the optimized sets come much closer to tightness than Fibonacci lattices do.
Table 3. Theorem 7 in numbers (ℓ = 0.8 \ell= 0.8 ℓ = 0.8 ). The optimized sets are exactly tight where tightness is possible (equispaced on S 1 \mathbb{S}^{1} S 1 , tetrahedron on S 2 \mathbb{S}^{2} S 2 ) and far closer to tight than Fibonacci lattices otherwise.
Tight Frames and Fekete Points
Tightness has two further classical readings, and the first extends to m > s m>s m > s . Write u j : = Φ T e j = ( φ 1 ( z j ) , … , φ s ( z j ) ) ∈ R s u_j:=\Phi^{\mathsf T}e_j=(\varphi_1(z_j),\ldots,\varphi_s(z_j))\in\mathbb{R}^s u j := Φ T e j = ( φ 1 ( z j ) , … , φ s ( z j )) ∈ R s for the feature vector of the j j j -th landmark in V s V_s V s . By Lemma 4 , every u j u_j u j has the same norm, ∥ u j ∥ 2 = k s ( z j , z j ) = s \lVert u_j\rVert^2=k_s(z_j,z_j)=s ∥ u j ∥ 2 = k s ( z j , z j ) = s . Their frame operator is ∑ j u j u j T = Φ T Φ \sum_j u_j u_j^{\mathsf T}=\Phi^{\mathsf T}\Phi ∑ j u j u j T = Φ T Φ , and their Gram matrix is Φ Φ T = [ k s ( z j , z l ) ] \Phi\Phi^{\mathsf T}=[k_s(z_j,z_l)] Φ Φ T = [ k s ( z j , z l )] . Following Benedetto and Fickus [42 ] , define the frame potential
FP ( Z ) : = ∑ j , l = 1 m k s ( z j , z l ) 2 = ∥ Φ T Φ ∥ F 2 . \operatorname{FP}(Z):=\sum_{j,l=1}^{m} k_s(z_j,z_l)^2=\lVert\Phi^{\mathsf T}\Phi\rVert_F^2. FP ( Z ) := j , l = 1 ∑ m k s ( z j , z l ) 2 = ∥ Φ T Φ ∥ F 2 .
Recall that a determinant-maximizing set for an interpolation problem is called a Fekete point set [28 ] , or an extremal fundamental system on the sphere [43 ] . Its natural least-squares analogue for m > s m>s m > s is a D-optimal design , which maximizes det ( Φ T Φ ) \det(\Phi^{\mathsf T}\Phi) det ( Φ T Φ ) [44 ] . Both are well defined because a change of orthonormal basis of V s V_s V s replaces Φ \Phi Φ by Φ Q \Phi Q Φ Q with Q Q Q orthogonal.
Proposition 11 (Tight frames, frame potential and Fekete points). In a homogeneous setting with V s V_s V s G G G -invariant, let m ≥ s m\ge s m ≥ s . For every configuration Z Z Z of m m m points,
σ min ( Φ ) 2 ≤ m , det ( Φ T Φ ) ≤ m s , FP ( Z ) ≥ m 2 s . \sigma_{\min}(\Phi)^2\le m,\qquad\det(\Phi^{\mathsf T}\Phi)\le m^s,\qquad\operatorname{FP}(Z)\ge m^2s. σ m i n ( Φ ) 2 ≤ m , det ( Φ T Φ ) ≤ m s , FP ( Z ) ≥ m 2 s . Equality in any one of the three holds if and only if Φ T Φ = m I \Phi^{\mathsf T}\Phi=mI Φ T Φ = m I . This in turn is equivalent to each of the following:
(a) { u j / s } j = 1 m \{u_j/\sqrt{s}\}_{j=1}^m { u j / s } j = 1 m is a unit-norm tight frame for R s \mathbb{R}^s R s ;
(b) the equal-weight rule 1 m ∑ j f ( z j ) \frac{1}{m}\sum_j f(z_j) m 1 ∑ j f ( z j ) integrates every f ∈ V s ⋅ V s f\in V_s\cdot V_s f ∈ V s ⋅ V s exactly.
For m = s m=s m = s , det ( Φ T Φ ) = det ( Φ ) 2 \det(\Phi^{\mathsf T}\Phi)=\det(\Phi)^2 det ( Φ T Φ ) = det ( Φ ) 2 . So the tight sampling sets of Theorem 7 are exactly the configurations attaining the universal Fekete bound ∣ det Φ ∣ ≤ s s / 2 \lvert\det\Phi\rvert\le s^{s/2} ∣ det Φ ∣ ≤ s s /2 , whenever such configurations exist. Their Lagrange functions satisfy sup x ∣ ℓ j ( x ) ∣ = 1 \sup_x\lvert\ell_j(x)\rvert=1 sup x ∣ ℓ j ( x )∣ = 1 .
Proof. The eigenvalues σ k 2 \sigma_k^2 σ k 2 of Φ T Φ \Phi^{\mathsf T}\Phi Φ T Φ are nonnegative with sum ∥ Φ ∥ F 2 = ∑ j k s ( z j , z j ) = m s \lVert\Phi\rVert_F^2=\sum_j k_s(z_j,z_j)=ms ∥ Φ ∥ F 2 = ∑ j k s ( z j , z j ) = m s . The minimum is at most the mean m m m . The arithmetic–geometric mean inequality gives ∏ k σ k 2 ≤ m s \prod_k\sigma_k^2\le m^s ∏ k σ k 2 ≤ m s . Cauchy–Schwarz gives FP ( Z ) = ∑ k σ k 4 ≥ ( m s ) 2 / s \operatorname{FP}(Z)=\sum_k\sigma_k^4\ge(ms)^2/s FP ( Z ) = ∑ k σ k 4 ≥ ( m s ) 2 / s , which is the Welch bound [45 ] . Each inequality is an equality if and only if all σ k 2 = m \sigma_k^2=m σ k 2 = m . The frame operator of the normalized vectors u j / s u_j/\sqrt{s} u j / s is Φ T Φ / s \Phi^{\mathsf T}\Phi/s Φ T Φ/ s , so Φ T Φ = m I \Phi^{\mathsf T}\Phi=mI Φ T Φ = m I says exactly that { u j / s } \{u_j/\sqrt{s}\} { u j / s } is a tight frame with frame bound m / s m/s m / s , which is the bound forced on any unit-norm tight frame of m m m vectors in R s \mathbb{R}^s R s [42 ] . This is reformulation (a). Statement (b) is the computation (i)⇔ \Leftrightarrow ⇔ (iii) of Theorem 8 with m m m nodes. For the last claim, (v) of Theorem 8 and Cauchy–Schwarz give ∣ ℓ j ( x ) ∣ = ∣ k s ( x , z j ) ∣ / s ≤ k s ( x , x ) k s ( z j , z j ) / s = 1 \lvert\ell_j(x)\rvert=\lvert k_s(x,z_j)\rvert/s\le\sqrt{k_s(x,x)k_s(z_j,z_j)}/s=1 ∣ ℓ j ( x )∣ = ∣ k s ( x , z j )∣ / s ≤ k s ( x , x ) k s ( z j , z j ) / s = 1 , with equality at x = z j x=z_j x = z j . □
For m = s m=s m = s , Proposition 11 shows that three different notions of good sampling coincide on tight sets: the conditioning criterion of Theorem 7 (maximal σ min \sigma_{\min} σ m i n ), the Fekete criterion (maximal ∣ det Φ ∣ \lvert\det\Phi\rvert ∣ det Φ ∣ ), and the frame-potential criterion (minimal ∑ j ≠ l k s ( z j , z l ) 2 \sum_{j\ne l}k_s(z_j,z_l)^2 ∑ j = l k s ( z j , z l ) 2 ). When tight sets do not exist, as on S 2 S^2 S 2 for s ≥ 9 s\ge9 s ≥ 9 , the three criteria are genuinely different relaxations.
For m > s m>s m > s , Proposition 11 gives a clean extension of tightness. On S 1 S^1 S 1 with s = 2 M + 1 s=2M+1 s = 2 M + 1 , the m m m equispaced points are a tight frame for every m ≥ s m\ge s m ≥ s , because the trapezoidal rule with m m m nodes is exact up to degree m − 1 ≥ 2 M m-1\ge2M m − 1 ≥ 2 M . On S 2 S^2 S 2 with s = ( M + 1 ) 2 s=(M+1)^2 s = ( M + 1 ) 2 , the condition Φ T Φ = m I \Phi^{\mathsf T}\Phi=mI Φ T Φ = m I says exactly that Z Z Z is a spherical 2 M 2M 2 M -design with m m m points. For s = 4 s=4 s = 4 , examples are the octahedron and the cube (both 3-designs) and the icosahedron and dodecahedron (both 5-designs), and the last two also qualify for s = 9 s=9 s = 9 . The equivalence with frames is the familiar correspondence between designs and tight frames [42 , 44 ] .
What does not extend is Proposition 6 , because for m > s m>s m > s the principal angles are no longer controlled by Φ \Phi Φ alone. Tightness still describes the best-conditioned sampling of V s V_s V s , since it maximizes σ min ( Φ ) 2 \sigma_{\min}(\Phi)^2 σ m i n ( Φ ) 2 and det ( Φ T Φ ) \det(\Phi^{\mathsf T}\Phi) det ( Φ T Φ ) , but we have no analogue of Theorem 7 that links this conditioning to F F F when m > s m>s m > s . The cube is a tight frame for s = 4 s=4 s = 4 , yet for s = 4 s=4 s = 4 and m = 8 m=8 m = 8 it is a saddle point of F F F (Table 4 ), and the optimizer prefers the square antiprism.
Table 4. Platonic solids as critical points of F F F on S 2 S^2 S 2 (ℓ = 0.8 \ell= 0.8 ℓ = 0.8 ).
A Symmetry Argument
Tightness explains why even spacing is favorable, but it does not by itself show that symmetric configurations are stationary points of the objective. That follows from a classical principle of Michel [12 , 46 ] . For a smooth action of a compact (in particular finite) group on a finite-dimensional manifold, the gradient of every invariant function vanishes on orbits that are isolated in their stratum. For the action of Γ × S m \Gamma\times S_m Γ × S m on landmark configurations, this hypothesis reduces to a condition on the stabilizers of the individual landmarks.
Theorem 12 (Symmetric orbits are critical points). Let Ω \Omega Ω be a Riemannian manifold, let K K K be C 1 C^1 C 1 , and let Γ \Gamma Γ be a finite group of isometries preserving μ \mu μ and K K K . Suppose V s V_s V s is Γ \Gamma Γ -invariant (for example, a union of full eigenspaces). Let Z = { z 1 , … , z m } Z = \{z_1,\ldots,z_m\} Z = { z 1 , … , z m } be a Γ \Gamma Γ -orbit such that, for every j j j , the stabilizer Γ z j \Gamma_{z_j} Γ z j fixes no nonzero tangent vector in T z j Ω T_{z_j}\Omega T z j Ω . Then Z Z Z is a critical point of F F F , and more generally of every C 1 C^1 C 1 function on Ω m \Omega^m Ω m that is invariant under permutations of the landmarks and under the diagonal action of Γ \Gamma Γ .
Proof. F F F is invariant under both actions because K Z Z K_{ZZ} K Z Z and K Z Z ( s ) K_{ZZ}^{(s)} K Z Z ( s ) are. The subgroup H = { ( g , σ g ) : g ∈ Γ } ⊂ Γ × S m H = \{(g,\sigma_g):g \in\Gamma\} \subset\Gamma\times S_m H = {( g , σ g ) : g ∈ Γ } ⊂ Γ × S m , where σ g \sigma_g σ g is the permutation induced by g g g on Z Z Z , fixes the ordered configuration Z Z Z . A tangent vector v = ( v j ) v = (v_j) v = ( v j ) at Z Z Z fixed by H H H satisfies d g v j = v σ g ( j ) dg\,v_j = v_{\sigma_g(j)} d g v j = v σ g ( j ) . For g ∈ Γ z j g \in\Gamma_{z_j} g ∈ Γ z j this says that v j v_j v j is fixed by Γ z j \Gamma_{z_j} Γ z j , so v j = 0 v_j = 0 v j = 0 . Thus Z Z Z is an isolated fixed point of H H H , i.e. its orbit is isolated in its stratum, and Michel’s theorem [12 ] applies. Directly, the gradient of an H H H -invariant function at an H H H -fixed point is an H H H -fixed tangent vector, hence zero.
On the sphere, configurations whose stabilizers fix no tangent vector are what Cohn, Elkies, Kumar and Schürmann call group-balanced [47 ] . Leech classified the configurations on S 2 S^2 S 2 that are in equilibrium under every pairwise force law [48 ] . Theorem 12 is the same principle applied to an objective that is not a pairwise energy. On the circle, the m m m equispaced points form an orbit of the dihedral group D m D_m D m , and the reflection through each point acts as − 1 -1 − 1 on its tangent line. So equispaced landmarks are critical for every m m m , s s s . On the sphere, the vertices of the five Platonic solids have stabilizers containing a rotation of order 3, 4, or 5 about the vertex axis, which fixes no tangent vector. All five solids are therefore critical points, and numerically ∥ ∇ F ∥ ≤ 3 × 10 − 14 \lVert\nabla F\rVert\le3 \times10^{-14} ∥ ∇ F ∥ ≤ 3 × 1 0 − 14 at each of them (Table 4 ).
Because Theorem 12 applies to every invariant objective, it carries no information specific to F F F , and in particular none about minimality. The Hessian at the cube and at the dodecahedron has negative directions (Table 4 ). This mirrors the fact that the cube is not an optimal eight-point configuration for packing or energy problems either. For s = 4 s = 4 s = 4 and m = 8 m = 8 m = 8 the optimizer instead finds a square antiprism. It has the combinatorial type of the best packing of 8 points [33 ] , but it is not that packing itself, because its edges have two different lengths (§ 8 ).
Equispaced Landmarks on the Circle
On the circle we can compute the leakage of the equispaced configuration exactly, for any number of landmarks m ≥ s m \ge s m ≥ s , and even the individual principal angles. The Gram matrices of equispaced points are circulant, so the discrete Fourier transform diagonalizes them [49 ] . Sampling then aliases frequency n n n onto the residue n m o d m n \bmod m n mod m . Both facts are standard. The contribution here is the result stated for F F F . Here and in Appendix A we index the circle eigenvalues by frequency, writing β k = e − α I k ( α ) \beta_k = e^{-\alpha} I_k(\alpha) β k = e − α I k ( α ) for the eigenvalue of e ± i k θ e^{\pm ik\theta} e ± ik θ , so that the sorted eigenvalues are λ 1 = β 0 \lambda_1 = \beta_0 λ 1 = β 0 and λ 2 k = λ 2 k + 1 = β k \lambda_{2k} = \lambda_{2k+1} = \beta_k λ 2 k = λ 2 k + 1 = β k for k ≥ 1 k \ge1 k ≥ 1 .
Theorem 13 (Aliasing formula). Let s = 2 M + 1 s = 2M + 1 s = 2 M + 1 , m ≥ s m \ge s m ≥ s , and let Z Z Z be m m m equispaced points on S 1 S^1 S 1 . The principal angles between U Z U_Z U Z and V s V_s V s are indexed by the frequencies ∣ k ∣ ≤ M |k| \le M ∣ k ∣ ≤ M , with
sin 2 θ k = ∑ j ≠ 0 β ∣ k + j m ∣ ∑ j ∈ Z β ∣ k + j m ∣ , so F ( Z ) = ∑ k = − M M ∑ j ≠ 0 β ∣ k + j m ∣ ∑ j ∈ Z β ∣ k + j m ∣ . \sin^2 \theta_k = \frac{\sum_{j \ne0} \beta_{|k+jm|}}{\sum_{j \in\mathbb{Z}} \beta_{|k+jm|}}, \qquad\text{so}\qquad F(Z) = \sum_{k=-M}^{M} \frac{\sum_{j \ne0} \beta_{|k+jm|}}{\sum_{j \in\mathbb{Z}} \beta_{|k+jm|}}. sin 2 θ k = ∑ j ∈ Z β ∣ k + j m ∣ ∑ j = 0 β ∣ k + j m ∣ , so F ( Z ) = k = − M ∑ M ∑ j ∈ Z β ∣ k + j m ∣ ∑ j = 0 β ∣ k + j m ∣ . The condition number of the Gram matrix is
κ ( K Z Z ) = max r ∑ j β ∣ r + j m ∣ min r ∑ j β ∣ r + j m ∣ . \kappa(K_{ZZ}) = \frac{\max_r \sum_j \beta_{|r+jm|}}{\min_r \sum_j \beta_{|r+jm|}}. κ ( K Z Z ) = min r ∑ j β ∣ r + j m ∣ max r ∑ j β ∣ r + j m ∣ . For m = s m = s m = s , the matrix R Z R_Z R Z of Proposition 6 is diagonal in the Fourier basis with entries tan 2 θ k = ∑ j ≠ 0 β ∣ k + j m ∣ / β ∣ k ∣ \tan^2 \theta_k = \sum_{j \ne0} \beta_{|k+jm|}/\beta_{|k|} tan 2 θ k = ∑ j = 0 β ∣ k + j m ∣ / β ∣ k ∣ .
See Appendix § 9 for the proof. For large m m m the formula shows that the dominant alias of the highest retained frequency M M M is m − M m-M m − M , and the two frequencies ± M \pm M ± M contribute equally, so F ≈ 2 β m − M / β M F \approx2\beta_{m-M}/\beta_M F ≈ 2 β m − M / β M . Since β k ∼ e − α ( α / 2 ) k / k ! \beta_k \sim e^{-\alpha}(\alpha/2)^k/k! β k ∼ e − α ( α /2 ) k / k ! , the leakage decays super-exponentially in m m m (Figure 1 ).
Figure 1. Theorem 13 on the circle. Left: F F F at m m m equispaced landmarks for s = 5 s=5 s = 5 and several bandwidths. The decay is super-exponential, and the dotted line marks the double-precision resolution of F = s − tr ( ⋅ ) F=s-\operatorname{tr}(\cdot) F = s − tr ( ⋅ ) , with values below 10 − 16 10^{-16} 1 0 − 16 clipped. Right: F F F at equispaced landmarks with m = s m=s m = s , as a function of ℓ \ell ℓ .
The Algorithm
The algorithm treats the landmark coordinates Z = ( z 1 , … , z m ) Z=(z_1,\ldots,z_m) Z = ( z 1 , … , z m ) as free parameters and minimizes a differentiable, Cholesky-based form of the leakage objective by gradient descent. It begins with a one-time precomputation of the top-s s s eigenpairs of the data kernel matrix K N ≈ U Σ U ⊤ K_N\approx U\Sigma U^\top K N ≈ U Σ U ⊤ , with U ∈ R N × s U\in\mathbb{R}^{N\times s} U ∈ R N × s and Σ = diag ( ν 1 , … , ν s ) \Sigma=\operatorname{diag}(\nu_1,\ldots,\nu_s) Σ = diag ( ν 1 , … , ν s ) . The landmarks are then updated iteratively from an initial configuration until the gradient or change in F F F reaches the resolution of the objective.
To allow the landmarks to leave the data points, we extend the eigenvectors to any z ∈ R d z\in\mathbb{R}^d z ∈ R d via the Nyström extension [50 ] :
ψ i ( z ) = 1 ν i ∑ j = 1 N k ( z , x j ) U j i , that is, ψ ( z ) ⊤ = k ( z , X ) U Σ − 1 / 2 ∈ R 1 × s \psi_i(z)=\frac{1}{\sqrt{\nu_i}}\sum_{j=1}^{N} k(z,x_j)U_{ji}, \qquad\text{that is,}\qquad\psi(z)^\top=k(z,X)U\Sigma^{-1/2}\in\mathbb{R}^{1\times s} ψ i ( z ) = ν i 1 j = 1 ∑ N k ( z , x j ) U j i , that is, ψ ( z ) ⊤ = k ( z , X ) U Σ − 1/2 ∈ R 1 × s
Each ψ i = ∑ j c j k ( ⋅ , x j ) \psi_i=\sum_j c_j k(\cdot,x_j) ψ i = ∑ j c j k ( ⋅ , x j ) has coefficient vector c = u i / ν i c=u_i/\sqrt{\nu_i} c = u i / ν i , so its squared RKHS norm is c ⊤ K N c = u i ⊤ K N u i / ν i = 1 c^\top K_Nc=u_i^\top K_Nu_i/\nu_i=1 c ⊤ K N c = u i ⊤ K N u i / ν i = 1 , and distinct ψ i \psi_i ψ i are orthogonal. At a data point z = x j z=x_j z = x j the formula returns ν i U j i \sqrt{\nu_i}U_{ji} ν i U j i . Consequently V s = span { ψ i } V_s=\operatorname{span}\{\psi_i\} V s = span { ψ i } is an exact s s s -dimensional subspace of H \mathcal{H} H , and all the projector algebra of the earlier sections applies unchanged, except that the points z j z_j z j may now lie anywhere and not only at data points. These ψ i \psi_i ψ i are exactly the functions λ i ϕ i \sqrt{\lambda_i}\phi_i λ i ϕ i of § 2.1 for the empirical measure μ N \mu_N μ N , with λ i = ν i / N \lambda_i=\nu_i/N λ i = ν i / N . Because μ N \mu_N μ N has finite support, the translates K z j K_{z_j} K z j of landmarks off the data have components in H 0 \mathcal{H}_0 H 0 , and it is the completed basis of § 2.1 that keeps the projector algebra, the mass conservation (5) , and the bounds of § 3.2 valid in this case.
For m m m landmarks, define the matrices H = U Σ − 1 / 2 ∈ R N × s H=U\Sigma^{-1/2}\in\mathbb{R}^{N\times s} H = U Σ − 1/2 ∈ R N × s and Ψ ( Z ) = k ( Z , X ) H ∈ R m × s \Psi(Z)=k(Z,X)H\in\mathbb{R}^{m\times s} Ψ ( Z ) = k ( Z , X ) H ∈ R m × s , whose ( j , i ) (j,i) ( j , i ) entry is ψ i ( z j ) \psi_i(z_j) ψ i ( z j ) . For the purpose of ensuring a stable Cholesky factorization, also define A ( Z ) = k ( Z , Z ) + ε I ∈ R m × m A(Z)=k(Z,Z)+\varepsilon I\in\mathbb{R}^{m\times m} A ( Z ) = k ( Z , Z ) + ε I ∈ R m × m , where ε \varepsilon ε is a small jitter that keeps A A A numerically positive definite. By (4) , ∑ i a i = tr ( A − 1 Ψ Ψ ⊤ ) \sum_i a_i=\operatorname{tr}(A^{-1}\Psi\Psi^\top) ∑ i a i = tr ( A − 1 Ψ Ψ ⊤ ) . Taking the Cholesky factor A = L L ⊤ A=LL^\top A = L L ⊤ and setting Y = L − 1 Ψ Y=L^{-1}\Psi Y = L − 1 Ψ gives
F ( Z ) = s − ∥ L − 1 Ψ ( Z ) ∥ F 2 (11) F(Z)=s-\lVert L^{-1}\Psi(Z)\rVert_F^2 \tag*{(11)} F ( Z ) = s − ∥ L − 1 Ψ ( Z ) ∥ F 2 (11)
The Frobenius-norm form avoids forming A − 1 A^{-1} A − 1 . It needs one Cholesky factorization and one triangular solve, both of which autodiff frameworks differentiate stably. Since Ψ Ψ ⊤ = k ( Z , X ) U Σ − 1 U ⊤ k ( X , Z ) \Psi\Psi^{\top}=k(Z,X)U\Sigma^{-1}U^{\top}k(X,Z) Ψ Ψ ⊤ = k ( Z , X ) U Σ − 1 U ⊤ k ( X , Z ) , the objective can equivalently be read as a comparison between the landmark Gram matrix and the Nyström-extended rank-s s s kernel evaluated at Z Z Z .
Algorithm 1 Spectral alignment landmark optimization
Require: Data X = { x i } i = 1 N X=\{x_i\}_{i=1}^{N} X = { x i } i = 1 N , kernel k k k , target rank s s s , number of landmarks m ≥ s m\ge s m ≥ s , jitter ε \varepsilon ε , gradient tolerance tol g \operatorname{tol}_{g} tol g , relative decrease tolerance tol F \operatorname{tol}_{F} tol F , patience p p p
Ensure: Landmarks Z = ( z 1 , … , z m ) Z=(z_1,\ldots,z_m) Z = ( z 1 , … , z m )
Form K N K_N K N and compute its top-s s s eigenpairs ( U , Σ ) (U,\Sigma) ( U , Σ ) by Lanczos or randomized SVD
H ← U Σ − 1 / 2 H\leftarrow U\Sigma^{-1/2} H ← U Σ − 1/2
Initialize Z ( 0 ) Z^{(0)} Z ( 0 ) by greedy selection, random sampling, or k k k -means++
c ← 0 c\leftarrow0 c ← 0
for t = 0 , 1 , 2 , … t=0,1,2,\ldots t = 0 , 1 , 2 , … do
Ψ ← k ( Z ( t ) , X ) H \Psi\leftarrow k(Z^{(t)},X)H Ψ ← k ( Z ( t ) , X ) H ▷ Nyström-extended eigenfunctions
A ← k ( Z ( t ) , Z ( t ) ) + ε I A\leftarrow k(Z^{(t)},Z^{(t)})+\varepsilon I A ← k ( Z ( t ) , Z ( t ) ) + ε I
L ← chol ( A ) L\leftarrow\operatorname{chol}(A) L ← chol ( A ) , Y ← L − 1 Ψ Y\leftarrow L^{-1}\Psi Y ← L − 1 Ψ
F ( t ) ← s − ∥ Y ∥ F 2 F^{(t)}\leftarrow s-\lVert Y\rVert_{F}^{2} F ( t ) ← s − ∥ Y ∥ F 2
g ← ∇ Z F ( t ) g\leftarrow\nabla_ZF^{(t)} g ← ∇ Z F ( t ) by reverse-mode autodiff
if ∥ g ∥ ∞ < tol g \lVert g\rVert_{\infty}<\operatorname{tol}_{g} ∥ g ∥ ∞ < tol g then
return Z ( t ) Z^{(t)} Z ( t )
end if
Z ( t + 1 ) ← Z^{(t+1)}\leftarrow Z ( t + 1 ) ← Adam or L-BFGS step on Z ( t ) Z^{(t)} Z ( t ) using g g g
Retract Z ( t + 1 ) Z^{(t+1)} Z ( t + 1 ) onto the manifold if constrained ▷ e.g. z j ← z j / ∥ z j ∥ z_j\leftarrow z_j/\lVert z_j\rVert z j ← z j / ∥ z j ∥ on S 2 S^2 S 2
end for
On S 1 S^1 S 1 we parametrize landmarks by angles. On S 2 S^2 S 2 we use unconstrained vectors v j ∈ R 3 v_j\in\mathbb{R}^3 v j ∈ R 3 with z j = v j / ∥ v j ∥ z_j=v_j/\lVert v_j\rVert z j = v j / ∥ v j ∥ and renormalize after every optimizer step, which avoids the pole singularities of latitude–longitude coordinates and makes the Euclidean gradient tangent. The objective is smooth and deterministic, so L-BFGS usually works well, especially in the badly conditioned tail.
The gradient written out
Autodiff computes the gradient automatically, but the explicit formula is useful for checking an implementation and for seeing how landmarks interact. We derive it for the data-driven objective. Throughout, k : = k ( Z , X ) ∈ R m × N k:=k(Z,X)\in\mathbb{R}^{m\times N} k := k ( Z , X ) ∈ R m × N , A = k ( Z , Z ) + ε I A=k(Z,Z)+\varepsilon I A = k ( Z , Z ) + ε I , and G = U Σ − 1 U ⊤ G=U\Sigma^{-1}U^{\top} G = U Σ − 1 U ⊤ . Since Ψ = k H = k U Σ − 1 / 2 \Psi=kH=kU\Sigma^{-1/2} Ψ = k H = k U Σ − 1/2 , we have
J : = k G k ⊤ = Ψ Ψ ⊤ , F = s − L t r , L t r : = tr ( A − 1 J ) . J:=kGk^{\top}=\Psi\Psi^{\top},\qquad F=s-L_{\mathrm{tr}},\qquad L_{\mathrm{tr}}:=\operatorname{tr}(A^{-1}J). J := k G k ⊤ = Ψ Ψ ⊤ , F = s − L tr , L tr := tr ( A − 1 J ) .
The landmarks enter L t r L_{\mathrm{tr}} L tr through A A A , and hence A − 1 A^{-1} A − 1 , and through k k k , and hence J J J . The matrix G G G depends only on the data and is constant.
By the product rule, d L t r = tr ( d A − 1 J ) + tr ( A − 1 d J ) dL_{\mathrm{tr}}=\operatorname{tr}(dA^{-1}J)+\operatorname{tr}(A^{-1}dJ) d L tr = tr ( d A − 1 J ) + tr ( A − 1 dJ ) . Differentiating A − 1 A = I A^{-1}A=I A − 1 A = I gives d A − 1 = − A − 1 d A A − 1 dA^{-1}=-A^{-1}dA A^{-1} d A − 1 = − A − 1 d A A − 1 , and since G G G is constant, d J = d k G k ⊤ + k G d k ⊤ dJ=dkGk^{\top}+kGdk^{\top} dJ = d k G k ⊤ + k G d k ⊤ . Hence
d L t r = − tr ( A − 1 d A A − 1 J ) + tr ( A − 1 d k G k ⊤ ) + tr ( A − 1 k G d k ⊤ ) . dL_{\mathrm{tr}}=-\operatorname{tr}(A^{-1}dA A^{-1}J)+\operatorname{tr}(A^{-1}dkGk^{\top})+\operatorname{tr}(A^{-1}kGdk^{\top}). d L tr = − tr ( A − 1 d A A − 1 J ) + tr ( A − 1 d k G k ⊤ ) + tr ( A − 1 k G d k ⊤ ) .
Transposing the last term inside the trace and using the symmetry of A − 1 A^{-1} A − 1 and G G G gives tr ( A − 1 k G d k ⊤ ) = tr ( d k G k ⊤ A − 1 ) = tr ( A − 1 d k G k ⊤ ) \operatorname{tr}(A^{-1}kGdk^{\top})=\operatorname{tr}(dkGk^{\top}A^{-1})=\operatorname{tr}(A^{-1}dkGk^{\top}) tr ( A − 1 k G d k ⊤ ) = tr ( d k G k ⊤ A − 1 ) = tr ( A − 1 d k G k ⊤ ) , so the two d k dk d k terms coincide and together equal 2 tr ( G k ⊤ A − 1 d k ) = ⟨ 2 A − 1 k G , d k ⟩ 2\operatorname{tr}(Gk^{\top}A^{-1}dk)=\langle2A^{-1}kG,dk\rangle 2 tr ( G k ⊤ A − 1 d k ) = ⟨ 2 A − 1 k G , d k ⟩ . Here we write each term as a Frobenius inner product ⟨ Δ , d x ⟩ = tr ( Δ ⊤ d x ) \langle\Delta,dx\rangle=\operatorname{tr}(\Delta^{\top}dx) ⟨ Δ , d x ⟩ = tr ( Δ ⊤ d x ) for the matrices Δ \Delta Δ defined below. By cyclicity, the first term is − tr ( A − 1 J A − 1 d A ) = ⟨ − A − 1 J A − 1 , d A ⟩ -\operatorname{tr}(A^{-1}JA^{-1}dA)=\langle-A^{-1}JA^{-1},dA\rangle − tr ( A − 1 J A − 1 d A ) = ⟨ − A − 1 J A − 1 , d A ⟩ , because A − 1 J A − 1 A^{-1}JA^{-1} A − 1 J A − 1 is symmetric. Therefore
d L t r = ⟨ Δ k , d k ⟩ + ⟨ Δ A , d A ⟩ , Δ k = 2 A − 1 k G ∈ R m × N , Δ A = − A − 1 J A − 1 ∈ R m × m . dL_{\mathrm{tr}}=\langle\Delta_k,dk\rangle+\langle\Delta_A,dA\rangle,\qquad\Delta_k=2A^{-1}kG\in\mathbb{R}^{m\times N},\qquad\Delta_A=-A^{-1}JA^{-1}\in\mathbb{R}^{m\times m}. d L tr = ⟨ Δ k , d k ⟩ + ⟨ Δ A , d A ⟩ , Δ k = 2 A − 1 k G ∈ R m × N , Δ A = − A − 1 J A − 1 ∈ R m × m .
Write ∇ 1 k \nabla_1 k ∇ 1 k and ∇ 2 k \nabla_2 k ∇ 2 k for the gradients of the kernel in its first and second arguments. The entry k j l = k ( z j , x l ) k_{jl}=k(z_j,x_l) k j l = k ( z j , x l ) depends only on z j z_j z j , with d k j l = ∇ 1 k ( z j , x l ) ⋅ d z j d k_{jl}=\nabla_1 k(z_j,x_l)\cdot d z_j d k j l = ∇ 1 k ( z j , x l ) ⋅ d z j . The entry A j l = k ( z j , z l ) + ε δ j l A_{jl}=k(z_j,z_l)+\varepsilon\delta_{jl} A j l = k ( z j , z l ) + ε δ j l depends on z j z_j z j through row j j j and through column j j j . Collecting the terms that contain d z j d z_j d z j gives
∑ l = 1 m ( Δ A ) j l ∇ 1 k ( z j , z l ) + ∑ l = 1 m ( Δ A ) l j ∇ 2 k ( z l , z j ) = 2 ∑ l = 1 m ( Δ A ) j l ∇ 1 k ( z j , z l ) . \sum_{l=1}^{m}(\Delta A)_{jl}\nabla_1 k(z_j,z_l)+\sum_{l=1}^{m}(\Delta A)_{lj}\nabla_2 k(z_l,z_j)=2\sum_{l=1}^{m}(\Delta A)_{jl}\nabla_1 k(z_j,z_l). l = 1 ∑ m ( Δ A ) j l ∇ 1 k ( z j , z l ) + l = 1 ∑ m ( Δ A ) l j ∇ 2 k ( z l , z j ) = 2 l = 1 ∑ m ( Δ A ) j l ∇ 1 k ( z j , z l ) .
where the equality uses ∇ 2 k ( z l , z j ) = ∇ 1 k ( z j , z l ) \nabla_2 k(z_l,z_j)=\nabla_1 k(z_j,z_l) ∇ 2 k ( z l , z j ) = ∇ 1 k ( z j , z l ) , which follows from the symmetry of k k k , and the symmetry of Δ A \Delta A Δ A . For the diagonal entry l = j l=j l = j , observe that d d z k ( z , z ) = 2 ∇ 1 k ( z , z ) \frac{d}{d z}k(z,z)=2\nabla_1 k(z,z) d z d k ( z , z ) = 2 ∇ 1 k ( z , z ) , and this term vanishes for any stationary kernel. Combining with the d k d k d k term and with F = s − L t r F=s-L_{\mathrm{tr}} F = s − L tr gives
∇ z j F = − [ ∑ l = 1 N ( Δ k ) j l ∇ 1 k ( z j , x l ) + 2 ∑ l = 1 m ( Δ A ) j l ∇ 1 k ( z j , z l ) ] . (12) \nabla_{z_j}F=-\left[\sum_{l=1}^{N}(\Delta k)_{jl}\nabla_1 k(z_j,x_l)+2\sum_{l=1}^{m}(\Delta A)_{jl}\nabla_1 k(z_j,z_l)\right]. \tag*{(12)} ∇ z j F = − [ l = 1 ∑ N ( Δ k ) j l ∇ 1 k ( z j , x l ) + 2 l = 1 ∑ m ( Δ A ) j l ∇ 1 k ( z j , z l ) ] . (12)
The first sum in (12) couples each landmark to the data, weighted by how the extended eigenfunctions ψ i \psi_i ψ i load on each data point after preconditioning by A − 1 A^{-1} A − 1 . The second sum couples the landmarks to one another.
Numerical Conditioning
The Gaussian kernel k ( x , y ) = exp ( − ∥ x − y ∥ 2 / 2 ℓ 2 ) k(x,y)=\exp(-\lVert x-y\rVert^2/2\ell^2) k ( x , y ) = exp ( − ∥ x − y ∥ 2 /2 ℓ 2 ) has a single length scale ℓ \ell ℓ , the bandwidth, which sets how far a translate k ( ⋅ , z j ) k(\cdot,z_j) k ( ⋅ , z j ) reaches. For large ℓ \ell ℓ the translates are broad and nearly parallel, and for small ℓ \ell ℓ they are narrow and nearly orthogonal. This governs the conditioning of the landmark Gram matrix K Z Z K_{ZZ} K Z Z , which the Cholesky-based objective inverts at every iteration. Broad translates make the columns of K Z Z K_{ZZ} K Z Z nearly dependent and κ ( K Z Z ) \kappa(K_{ZZ}) κ ( K Z Z ) large, while narrow translates make K Z Z K_{ZZ} K Z Z close to the identity.
Consider the landmark spacing h h h , which is 2 π / m 2\pi/m 2 π / m on S 1 \mathrm{S}^1 S 1 and of order 4 π / m \sqrt{4\pi/m} 4 π / m on S 2 \mathrm{S}^2 S 2 [30 ] . Adding landmarks decreases h h h , so at fixed ℓ \ell ℓ more translates overlap and the Gram matrix becomes worse conditioned. Keeping the Cholesky-based objective numerically well posed therefore requires a smaller bandwidth as m m m grows. This section first quantifies this conditioning limit, which is an upper limit on ℓ \ell ℓ for a given m m m , and then identifies an opposite lower limit, below which the objective depends on the landmark positions only through terms too small to resolve in floating point.
On S 1 \mathrm{S}^1 S 1 and S 2 \mathrm{S}^2 S 2 the Gaussian eigenvalues decay super-exponentially [51 , 52 ] , so in floating point the Gram matrix has a finite numerical rank. Landmark counts much larger than this rank therefore force K Z Z K_{ZZ} K Z Z to have eigenvalues below the working precision, and so κ ( K Z Z ) \kappa(K_{ZZ}) κ ( K Z Z ) becomes prohibitively large. The rank grows as the bandwidth shrinks, since a narrower kernel has a slower-decaying spectrum and more eigenvalues remain above the working precision. Solving κ ( K Z Z ) = 10 12 \kappa(K_{ZZ})=10^{12} κ ( K Z Z ) = 1 0 12 for ℓ \ell ℓ (Figure 2 ) gives the largest admissible bandwidths in Table 1 . Beyond this limit two things can go wrong. The Cholesky factorization either fails or is dominated by the jitter ε \varepsilon ε , which biases F F F because ε \varepsilon ε then exceeds the smallest eigenvalues of K Z Z K_{ZZ} K Z Z . In addition, errors in ∇ tr ( A − 1 K Z Z ( s ) ) \nabla\operatorname{tr}(A^{-1}K_{ZZ}^{(s)}) ∇ tr ( A − 1 K Z Z ( s ) ) are amplified by κ ( A ) \kappa(A) κ ( A ) , so the descent direction becomes noise. This is Schaback’s uncertainty principle [4 ] at work, since flat kernels approximate smooth functions well but produce ill-conditioned systems. If a larger ℓ \ell ℓ is genuinely needed, a stable basis should be constructed. With the analytic expansion of Appendix § 9 .§ 1 , one can factor the decaying β n \beta_n β n out of K Z Z K_{ZZ} K Z Z analytically, in the spirit of RBF-QR [35 , 36 ] .
Table 1. Largest Gaussian bandwidth keeping κ ( K Z Z ) < 10 12 \kappa(K_{ZZ}) < 10^{12} κ ( K Z Z ) < 1 0 12 . On S 1 S^{1} S 1 the ratio ℓ max / h \ell_{\max}/h ℓ m a x / h converges to about 2.4 (it is 2.41 at m = 257 m = 257 m = 257 and 2.40 at m = 513 m = 513 m = 513 ), so ℓ max ∝ m − 1 \ell_{\max} \propto m^{-1} ℓ m a x ∝ m − 1 . On S 2 S^{2} S 2 the ratio is still decreasing at m = 400 m = 400 m = 400 . Recomputing it for Fibonacci sets with m = 900 m = 900 m = 900 , 1600 and 2500 gives values between 1.9 and 2.2, so ℓ max ∝ m − 1 / 2 \ell_{\max} \propto m^{-1/2} ℓ m a x ∝ m − 1/2 with a constant somewhat below the circle value. With the threshold 10 8 10^{8} 1 0 8 the ratios are about 2.0 on S 1 S^{1} S 1 and between 1.5 and 1.8 on S 2 S^{2} S 2 over the same range of m m m .
Figure 2. Conditioning limit of K ( Z , Z ) K(Z,Z) K ( Z , Z ) . Left: largest admissible bandwidth against landmark spacing, with the reference line ℓ = 2.5 h \ell= 2.5h ℓ = 2.5 h . Right: the ratio ℓ max / h \ell_{\max}/h ℓ m a x / h , which settles to a constant on S 1 S^{1} S 1 and decreases slowly toward a somewhat smaller value on S 2 S^{2} S 2 .
The bandwidth is also bounded from below. If ℓ ≪ q Z \ell\ll q_Z ℓ ≪ q Z , where q Z q_Z q Z is half the minimum pairwise distance of the landmarks, then the kernels are too narrow to see each other and K Z Z ≈ I K_{ZZ}\approx I K Z Z ≈ I . In that case write K Z Z = I + O Z Z K_{ZZ}=I+O_{ZZ} K Z Z = I + O Z Z , where O Z Z O_{ZZ} O Z Z has zero diagonal and its off-diagonal entries are e − ∥ z j − z l ∥ 2 / 2 ℓ 2 e^{-\lVert z_j-z_l\rVert^2/2\ell^2} e − ∥ z j − z l ∥ 2 /2 ℓ 2 . Whenever ∥ O Z Z ∥ < 1 \lVert O_{ZZ}\rVert<1 ∥ O Z Z ∥ < 1 , the Neumann series ( I + O Z Z ) − 1 = I − O Z Z + O Z Z 2 − ⋯ (I+O_{ZZ})^{-1}=I-O_{ZZ}+O_{ZZ}^2-\cdots ( I + O Z Z ) − 1 = I − O Z Z + O Z Z 2 − ⋯ converges, and substituting it into (6) gives
F ( Z ) = s − tr K Z Z ( s ) + tr ( O Z Z K Z Z ( s ) ) − tr ( O Z Z 2 K Z Z ( s ) ) + ⋯ F(Z)=s-\operatorname{tr}K_{ZZ}^{(s)}+\operatorname{tr}\left(O_{ZZ}K_{ZZ}^{(s)}\right)-\operatorname{tr}\left(O_{ZZ}^2K_{ZZ}^{(s)}\right)+\cdots F ( Z ) = s − tr K Z Z ( s ) + tr ( O Z Z K Z Z ( s ) ) − tr ( O Z Z 2 K Z Z ( s ) ) + ⋯
By Lemma 4 , the leading term is s − tr K Z Z ( s ) = s − m ( 1 − τ s ) s-\operatorname{tr}K_{ZZ}^{(s)}=s-m(1-\tau_s) s − tr K Z Z ( s ) = s − m ( 1 − τ s ) , which does not depend on the positions. The first position-dependent term is tr ( O Z Z K Z Z ( s ) ) \operatorname{tr}(O_{ZZ}K_{ZZ}^{(s)}) tr ( O Z Z K Z Z ( s ) ) . Since every pairwise distance is at least 2 q Z 2q_Z 2 q Z , each entry of O Z Z O_{ZZ} O Z Z is at most e − 2 q Z 2 / ℓ 2 e^{-2q_Z^2/\ell^2} e − 2 q Z 2 / ℓ 2 , and the entries between nearest neighbors attain this order. For equispaced points (q Z = h / 2 q_Z = h/2 q Z = h /2 ) at ℓ = 0.15 h \ell= 0.15h ℓ = 0.15 h this factor is e − 1 / ( 2 ⋅ 0.15 2 ) ≈ 2 × 10 − 10 e^{-1/(2\cdot0.15^2)} \approx2 \times10^{-10} e − 1/ ( 2 ⋅ 0.1 5 2 ) ≈ 2 × 1 0 − 10 . The landmark positions therefore still determine F F F , but only through a correction about ten orders of magnitude below the leading term, which the optimizer cannot resolve with absolute tolerances in double precision. The lower limit is thus a limit of numerical resolution, not a loss of information in the objective.
To locate the two limits empirically, we swept m m m and ℓ \ell ℓ for s = 5 s = 5 s = 5 on S 1 S^{1} S 1 with the analytic objective and uniform random initialization. We recorded whether the result was evenly spaced, meaning that the maximum relative deviation of consecutive gaps from 2 π / m 2\pi/m 2 π / m is below 5%. Figure 3 shows the outcome.
Figure 3. Trade-off between m m m and ℓ \ell ℓ on S 1 \mathbb{S}^{1} S 1 , s = 5 s=5 s = 5 . Left: markers show the outcome of the multistart runs in the ( m , ℓ / h ) (m,\ell/h) ( m , ℓ / h ) plane (circle: all runs evenly spaced, square: some, cross: none). The background is log 10 F e q u i ( m , ℓ ) \log_{10} F_{\mathrm{equi}}(m,\ell) log 10 F equi ( m , ℓ ) from Theorem 13 . The dashed white line is F e q u i = 10 − 9 F_{\mathrm{equi}}=10^{-9} F equi = 1 0 − 9 and the dotted line is ℓ = 0.15 h \ell=0.15h ℓ = 0.15 h . Right: median of the largest relative gap deviation versus ℓ / h \ell/h ℓ / h . The dashed line is the 5% evenness threshold.
The results support two conclusions. First, the lower limit is sharp and independent of m m m . Every failure below the window occurs at ℓ / h ≤ 0.15 \ell/h \le0.15 ℓ / h ≤ 0.15 , which is consistent with the flat-landscape analysis above. Second, the upper limit decreases as m m m grows, so the window shrinks. The admissible upper value of ℓ / h \ell/h ℓ / h therefore decreases from ≥ 1.9 \ge1.9 ≥ 1.9 at m = 10 m = 10 m = 10 to around 0.98 at m = 30 m = 30 m = 30 , while the lower limit stays near 0.15. Runs above the window fail once F e q u i F_{\mathrm{equi}} F equi (Theorem 13 ) drops below about 10 − 9 10^{-9} 1 0 − 9 , even when the Gram matrix is still well conditioned. At m = 30 m = 30 m = 30 and ℓ = 0.25 \ell= 0.25 ℓ = 0.25 , for example, κ ≈ 440 \kappa\approx440 κ ≈ 440 but F e q u i = 1.8 × 10 − 9 F_{\mathrm{equi}} = 1.8 \times10^{-9} F equi = 1.8 × 1 0 − 9 , and the optimizer stops at uneven configurations with F ≈ 7 × 10 − 8 F\approx7\times10^{-8} F ≈ 7 × 1 0 − 8 . Once the minimum is that small, the objective and its gradient are small as well, so many uneven configurations satisfy the optimizer’s absolute stopping tolerances even though their F F F is still above the minimum. At still larger ℓ \ell ℓ (with κ ≳ 10 8 \kappa\gtrsim10^{8} κ ≳ 1 0 8 ), ill-conditioning takes over and the computed F F F even becomes negative, with a median of − 8.5 × 10 − 3 -8.5\times10^{-3} − 8.5 × 1 0 − 3 at m = 20 m=20 m = 20 and ℓ = 1.2 \ell=1.2 ℓ = 1.2 . Inside the window, the recovered configurations are equispaced to high accuracy, with median gap deviations between 10 − 10 10^{-10} 1 0 − 10 and 10 − 5 10^{-5} 1 0 − 5 , and the attained F F F agrees with F e q u i F_{\mathrm{equi}} F equi to at least six digits.
The results from the circle extend to the sphere, where evenness was measured by the mesh ratio ρ = δ Z / q Z \rho=\delta_Z/q_Z ρ = δ Z / q Z , where δ Z \delta_Z δ Z is the covering radius and q Z q_Z q Z is half the minimum separation.1 We use δ Z \delta_Z δ Z for the covering radius to avoid confusion with the spacing h h h . In all but a few of ( m , ℓ ) (m,\ell) ( m , ℓ ) combinations shown in Figure 4 the optimized landmarks have a lower mesh ratio than the Fibonacci lattice, and in all cases they reach a lower objective (Figure 4 ). The advantage in F F F is largest at moderate-to-large ℓ / h \ell/h ℓ / h , where the objective is far from its flat limit. There F o p t / F F i b F_{\mathrm{opt}}/F_{\mathrm{Fib}} F opt / F Fib reaches 0.036 at ( m , ℓ ) = ( 64 , 0.5 ) (m,\ell)=(64,0.5) ( m , ℓ ) = ( 64 , 0.5 ) and 0.015 at ( 36 , 1.2 ) (36,1.2) ( 36 , 1.2 ) . For ℓ / h ≲ 0.3 \ell/h\lesssim0.3 ℓ / h ≲ 0.3 the two objectives agree to two or three digits, consistent with the flat-landscape limit F ≈ s − m ( 1 − τ s ) F\approx s-m(1-\tau_s) F ≈ s − m ( 1 − τ s ) . Even in this flat regime the optimized sets remain well spread (ρ ≤ 1.53 \rho\le1.53 ρ ≤ 1.53 ), because the weak residual repulsion between neighboring translates is still enough to separate landmarks, although the result is then less clearly tied to the eigenspace.
Figure 4. Trade-off on S 2 \mathbb{S}^2 S 2 , s = 9 s = 9 s = 9 . Median mesh ratio ρ \rho ρ of optimized landmarks (solid) and the Fibonacci lattice with the same m m m (dotted, same colour)
The single exception is ( m , ℓ ) = ( 36 , 1.2 ) (m,\ell)=(36,1.2) ( m , ℓ ) = ( 36 , 1.2 ) , where ℓ / h = 2.0 \ell/h=2.0 ℓ / h = 2.0 , F o p t = 2.7 × 10 − 7 F_{\mathrm{opt}}=2.7\times10^{-7} F opt = 2.7 × 1 0 − 7 , and ρ o p t = 1.76 \rho_{\mathrm{opt}}=1.76 ρ opt = 1.76 . This is the sphere analogue of the upper failure on the circle, in which the objective is so small that absolute stopping criteria are triggered before the minimum is reached. For the values of m m m tested, the useful window on the sphere is therefore roughly 0.3 ≲ ℓ / h ≲ 1.4 0.3 \lesssim\ell/h \lesssim1.4 0.3 ≲ ℓ / h ≲ 1.4 , where the objective is both informative and well resolved.
Results on The Circle
To first establish a baseline for accuracy, we use the exact eigenspace of Proposition 15 so that the objective is free of sampling noise. From 20 random starts per case, we ask whether the optimizer reliably finds the equispaced configuration, and whether the attained F F F agrees with the closed-form value of Theorem 13 . We then turn to a data-driven experiment, in which the eigenvectors are computed from N = 10,000 N = 10{,}000 N = 10 , 000 uniform samples on S 1 \mathbb{S}^1 S 1 with ℓ = 0.8 \ell= 0.8 ℓ = 0.8 .
Exact-Eigenspace Study
Table 2 reports 20 random starts per case with the analytic objective at ℓ = 0.8 \ell= 0.8 ℓ = 0.8 . In every case with m ≤ 10 m \le10 m ≤ 10 all 20 runs reached the equispaced configuration, the best F F F found matched the value from Theorem 13 , and no start found a lower value. The median gap deviations of order 10 − 9 10^{-9} 1 0 − 9 to 10 − 8 10^{-8} 1 0 − 8 show that the equispacing is exact to the optimizer’s tolerance. The Hessian at the equispaced configuration is positive definite modulo the rotation direction in all of these cases. The single failure is ( s , m ) = ( 9 , 17 ) (s,m) = (9,17) ( s , m ) = ( 9 , 17 ) , where none of the runs achieves equispacing. In that case, the leakage 7.8 × 10 − 10 7.8 \times10^{-10} 7.8 × 1 0 − 10 lies below the level of about 10 − 9 10^{-9} 1 0 − 9 at which random starts fail to reach equispacing in the trade-off study (§ 6 ), and the Gram matrix is poorly conditioned with κ ( K Z Z ) ≈ 4.3 × 10 5 \kappa(K_{ZZ}) \approx4.3 \times10^5 κ ( K Z Z ) ≈ 4.3 × 1 0 5 . Here h = 2 π / 17 h = 2\pi/17 h = 2 π /17 , so ℓ / h ≈ 2.2 \ell/h \approx2.2 ℓ / h ≈ 2.2 , which lies above the window identified in § 6 for m m m of this size. This is the behavior that § 6 predicts, and Remark 14 suggests how it might be avoided.
Table 2. Circle, ℓ = 0.8 \ell= 0.8 ℓ = 0.8 , exact eigenspace. “Hessian η 2 \eta_2 η 2 ” is the smallest nonzero eigenvalue of the Hessian of F F F at the equispaced configuration, whose eigenvalues we denote η 1 ≤ η 2 ≤ ⋯ \eta_1 \le\eta_2 \le\cdots η 1 ≤ η 2 ≤ ⋯ to distinguish them from the kernel eigenvalues (η 1 = 0 \eta_1 = 0 η 1 = 0 is the rotation). No start found a value below the equispaced one. For ( s , m ) = ( 9 , 17 ) (s,m) = (9,17) ( s , m ) = ( 9 , 17 ) the objective is below the level of about 10 − 9 10^{-9} 1 0 − 9 at which the trade-off study begins to fail, the Gram matrix is badly conditioned, and the runs stall away from equispacing.
Table 3 complements this study by quantifying Theorem 7 . The equispaced sets on the circle attain the maximum possible σ min ( Φ ) 2 = s \sigma_{\min}(\Phi)^2 = s σ m i n ( Φ ) 2 = s and are therefore exactly tight, and the same holds for the tetrahedron on the sphere. For the larger sphere cases the optimized sets are far closer to tight than Fibonacci lattices, even though exact tightness is impossible there.
Data-Driven Experiment
The experiment uses N = 10,000 N = 10{,}000 N = 10 , 000 uniform points on S 1 \mathbb{S}^{1} S 1 with ℓ = 0.8 \ell= 0.8 ℓ = 0.8 . For s = m = 5 s = m = 5 s = m = 5 with random initializations (and one greedy initialization) all runs reach the same minimum F = 0.4215 F = 0.4215 F = 0.4215 . This suggests a single basin, up to the rotation and permutation symmetries of the circle. The angular spacings of the optimized landmarks sum to 2 π ≈ 6.2832 2\pi\approx6.2832 2 π ≈ 6.2832 and sit within about 1% of 2 π / 5 = 1.2566 2\pi/5 = 1.2566 2 π /5 = 1.2566 , with a largest deviation of 0.0124 rad. These deviations are small but nonzero because the empirical measure μ N \mu_N μ N is not rotation invariant. The data-driven objective therefore lacks the symmetry that makes the equispaced configuration a critical point, and its minimizer is a slight perturbation of an equispaced set. (The same lack of invariance means that rotating all landmarks together changes F F F slightly, which fixes the overall rotation of the optimum.) With the exact eigenspace the deviations vanish to 10 − 9 10^{-9} 1 0 − 9 (Table 2 ).
We also compute the principal angles directly. With A = L L ⊤ A = LL^\top A = L L ⊤ , the singular values of Y = L − 1 Ψ Y = L^{-1}\Psi Y = L − 1 Ψ are the cosines of the principal angles between V 5 V_5 V 5 and U ^ Z \widehat{U}_Z U Z , where Ψ = κ ( Z ^ , X ) H \Psi= \kappa(\widehat{Z},X)H Ψ = κ ( Z , X ) H . For the optimal landmarks Z ^ \widehat{Z} Z from the optimizer the five squared cosines sum to
0.99695 + 0.98379 + 0.98341 + 0.81130 + 0.80305 = 4.57850 , 0.99695 + 0.98379 + 0.98341 + 0.81130 + 0.80305 = 4.57850, 0.99695 + 0.98379 + 0.98341 + 0.81130 + 0.80305 = 4.57850 ,
so F = 5 − 4.57850 = 0.42150 F = 5 - 4.57850 = 0.42150 F = 5 − 4.57850 = 0.42150 , which equals the optimizer’s best F F F to the printed precision. The Cholesky objective and the SVD diagnostic therefore agree. The leakage $1 - \cos^2 \theta$ in each direction also matches the Fourier picture. It is approximately 0.003 for the constant mode, 0.016 and 0.017 for the k = 1 k = 1 k = 1 pair, and 0.189 and 0.197 for the k = 2 k = 2 k = 2 pair. The leakage is largest for k = 2 k = 2 k = 2 because the landmark translates carry the k = ± 3 k = \pm3 k = ± 3 content (the λ 6 , λ 7 \lambda_6,\lambda_7 λ 6 , λ 7 pair) aliased onto k = ∓ 2 k = \mp2 k = ∓ 2 , and those k = 3 k = 3 k = 3 modes are the closest ones in the tail. This is exactly the mechanism of Theorem 13 , which gives a per-mode leakage of $\sin^2 \theta_k = tan 2 θ k / ( 1 + tan 2 θ k ) \tan^2\theta_k/(1+\tan^2\theta_k) tan 2 θ k / ( 1 + tan 2 θ k ) with tan 2 θ k = ∑ j ≠ 0 β ∣ k + 5 j ∣ / β ∣ k ∣ \tan^2\theta_k=\sum_{j\ne0}\beta_{\lvert k+5j\rvert}/\beta_{\lvert k\rvert} tan 2 θ k = ∑ j = 0 β ∣ k + 5 j ∣ / β ∣ k ∣ . With the exact eigenvalues this yields 0.0031, 0.0168, and 0.1989 for k = 0 , 1 , 2 k=0,1,2 k = 0 , 1 , 2 , in line with the measured values. By mass conservation (5) , the same 0.4215 is also the total amount of the tail i > 5 i>5 i > 5 that has leaked into U Z U_Z U Z .
The sandwich bound can be checked directly on these numbers. Since k ( x , x ) = 1 k(x,x)=1 k ( x , x ) = 1 we have ∑ i λ i = 1 \sum_i\lambda_i=1 ∑ i λ i = 1 , and therefore
∑ i > 5 λ i = 1 − ( 0.35847 + 0.21934 + 0.21888 + 0.07916 + 0.07683 ) = 1 − 0.95268 = 0.04732. \sum_{i>5}\lambda_i=1-(0.35847+0.21934+0.21888+0.07916+0.07683)=1-0.95268=0.04732. i > 5 ∑ λ i = 1 − ( 0.35847 + 0.21934 + 0.21888 + 0.07916 + 0.07683 ) = 1 − 0.95268 = 0.04732.
The mean of P Z ^ 2 P_{\hat{Z}}^2 P Z ^ 2 over the data is 0.07810, which estimates ∫ P Z ^ 2 d μ \int P_{\hat{Z}}^2\,\mathrm{d}\mu ∫ P Z ^ 2 d μ , so the excess is E = 0.07810 − 0.04732 = 0.03078 E=0.07810-0.04732=0.03078 E = 0.07810 − 0.04732 = 0.03078 . The sandwich bound ( λ 5 − λ 6 ) F ≤ E ≤ λ 1 F (\lambda_5-\lambda_6)F\le E\le\lambda_1F ( λ 5 − λ 6 ) F ≤ E ≤ λ 1 F gives a lower bound of ( 0.07683 − 0.01955 ) ( 0.4215 ) = 0.0241 (0.07683-0.01955)(0.4215)=0.0241 ( 0.07683 − 0.01955 ) ( 0.4215 ) = 0.0241 and an upper bound of 0.3585 × 0.4215 = 0.1511 0.3585\times0.4215=0.1511 0.3585 × 0.4215 = 0.1511 . The observed value E = 0.0308 E=0.0308 E = 0.0308 lies inside [ 0.0241 , 0.1511 ] [0.0241,0.1511] [ 0.0241 , 0.1511 ] and near its lower end. This is expected, because most of the leakage sits on the small eigenvalues (the k = 2 k=2 k = 2 modes), so the weighted excess is small compared to the worst case where all the mass lies on λ 1 \lambda_1 λ 1 .
The experiments with more landmarks than eigenvectors probe the regime of Theorem 13 . With s = 5 s=5 s = 5 and m = 10 m=10 m = 10 , the leakage falls to F = 2.0613 × 10 − 5 F=2.0613\times10^{-5} F = 2.0613 × 1 0 − 5 very quickly and equispacing is maintained, in close agreement with the value 2.0428 × 10 − 5 2.0428\times10^{-5} 2.0428 × 1 0 − 5 predicted for the exact eigenspace. Figure 5 shows a larger data-driven example, with s = 9 s=9 s = 9 , m = 25 m=25 m = 25 and ℓ = 0.30 \ell=0.30 ℓ = 0.30 , so that h = 2 π / 25 h=2\pi/25 h = 2 π /25 and ℓ / h ≈ 1.19 \ell/h\approx1.19 ℓ / h ≈ 1.19 , inside the window of § 6 .
Figure 5. Circle, s = 9 s=9 s = 9 , m = 25 m=25 m = 25 , ℓ = 0.30 \ell=0.30 ℓ = 0.30 (ℓ / h ≈ 1.19 \ell/h\approx1.19 ℓ / h ≈ 1.19 ), data-driven eigenvectors from N = 10,000 N=10{,}000 N = 10 , 000 uniform samples.
Results on the Sphere
The sphere experiments test whether the picture established on the circle survives in a setting where exact tightness is mostly impossible [11 ] . We examine which configurations the optimizer finds, whether the symmetric critical points predicted by Theorem 12 are minima, and how the sandwich bound behaves. Unless stated otherwise, the objective uses the exact truncated kernel K ( s ) K^{(s)} K ( s ) of Proposition 16 .
Landmarks are parametrized by unconstrained vectors v j ∈ R 3 v_j\in\mathbb{R}^3 v j ∈ R 3 with z j = v j / ∥ v j ∥ z_j=v_j/\lVert v_j\rVert z j = v j / ∥ v j ∥ , and they are renormalized after every optimizer step. Since F F F depends on v j v_j v j only through its direction, the gradient with respect to v j v_j v j is tangent to the sphere at z j z_j z j , and renormalization changes neither F F F nor its gradient direction. We used Adam with learning rate 0.03, followed by L-BFGS with a strong Wolfe line search, a gradient-and-patience stopping rule, jitter ε = 10 − 13 \varepsilon=10^{-13} ε = 1 0 − 13 , and ℓ = 0.8 \ell=0.8 ℓ = 0.8 .
Table 4 evaluates F F F at the Platonic solids. As Theorem 12 predicts, all are critical points to machine precision. The signature of the Euclidean Hessian of Z ↦ F ( Z / ∥ Z ∥ ) Z\mapsto F(Z/\lVert Z\rVert) Z ↦ F ( Z / ∥ Z ∥) counts negative, zero and positive eigenvalues. The zero eigenvalues are always m + 3 m+3 m + 3 in number, corresponding to m m m radial directions plus 3 rotations.
Table 5 summarizes ten random starts per case. Figure 6 shows the best configurations. For m = 4 m = 4 m = 4 , 6 and 12 the identification is rigorous up to numerical tolerance, through the Tammes problem of maximizing the minimum separation of m m m points [31 ] . Fejes Tóth’s bound [32 ] is attained for m = 4 , 6 , 12 m = 4, 6, 12 m = 4 , 6 , 12 , and the maximizers are unique up to isometry. We therefore claim to recover the regular tetrahedron, octahedron and icosahedron, with separations arccos ( − 1 3 ) = 109.4712 ∘ \arccos\left(-\frac{1}{3}\right) = 109.4712^\circ arccos ( − 3 1 ) = 109.471 2 ∘ , 90 ∘ 90^\circ 9 0 ∘ and arctan 2 = 63.4349 ∘ \arctan2 = 63.4349^\circ arctan 2 = 63.434 9 ∘ (for uniqueness at m = 12 m = 12 m = 12 see also [34 ] ). In the best run (which all ten starts reach) the nearest-neighbor angle of every landmark equals these values to within 10 − 7 10^{-7} 1 0 − 7 degrees. An independent test also shows that the best F F F equals F F F at the explicitly constructed polyhedron (Table 4 ) to about 15 significant digits.
Table 5. 10 Random Starts on the Sphere, ℓ = 0.8 \ell= 0.8 ℓ = 0.8 , exact eigenspace. “Runs at best” counts starts within relative 10 − 6 10^{-6} 1 0 − 6 of the best value achieved. Every optimized set beats the Fibonacci lattice in both F F F and mesh ratio. The tetrahedron, octahedron and icosahedron are recovered exactly: their F F F values match Table 4 to all printed digits, and all nearest-neighbor angles agree to 10 − 7 10^{-7} 1 0 − 7 degrees.
Figure 6. Best landmark configurations on S 2 S^2 S 2 from ten random starts (ℓ = 0.8 \ell= 0.8 ℓ = 0.8 , exact eigenspace), drawn with the geodesic edges of their convex hull.
To further verify the tightness claims, we certify the design strength against the number of points. A finite set Z = { z 1 , … , z m } ⊂ S 2 Z = \{z_1,\ldots,z_m\} \subset S^2 Z = { z 1 , … , z m } ⊂ S 2 is a spherical t t t -design if the equal-weight rule integrates every polynomial of degree at most t t t exactly,
1 m ∑ j = 1 m p ( z j ) = ∫ S 2 p d μ for all p ∈ Π t , \frac{1}{m}\sum_{j=1}^{m}p(z_j)=\int_{S^2}p\,d\mu\qquad\text{for all }p\in\Pi_t, m 1 j = 1 ∑ m p ( z j ) = ∫ S 2 p d μ for all p ∈ Π t ,
and its strength is the largest such t t t [29 ] . Since the restriction of Π t \Pi_t Π t to S 2 S^2 S 2 is ⨁ n ≤ t H n \bigoplus_{n\le t}\mathcal{H}_n ⨁ n ≤ t H n , where H n \mathcal{H}_n H n is the space of spherical harmonics of degree n n n , and since every Y ∈ H n Y\in\mathcal{H}_n Y ∈ H n with n ≥ 1 n\ge1 n ≥ 1 has zero mean, the definition reduces to a condition on each degree separately. For n ≥ 1 n\ge1 n ≥ 1 define the degree-n n n moment
M n ( Z ) : = ( 1 2 n + 1 ∑ k = 1 2 n + 1 ∣ 1 m ∑ j = 1 m φ n k ( z j ) ∣ 2 ) 1 / 2 = ( 1 m 2 ∑ j , l = 1 m P n ( z j ⋅ z l ) ) 1 / 2 , (13) M_n(Z) := \left(\frac{1}{2n+1}\sum_{k=1}^{2n+1}\left|\frac{1}{m}\sum_{j=1}^{m}\varphi_{nk}(z_j)\right|^2\right)^{1/2} = \left(\frac{1}{m^2}\sum_{j,l=1}^{m}P_n(z_j\cdot z_l)\right)^{1/2}, \tag*{(13)} M n ( Z ) := 2 n + 1 1 k = 1 ∑ 2 n + 1 m 1 j = 1 ∑ m φ nk ( z j ) 2 1/2 = m 2 1 j , l = 1 ∑ m P n ( z j ⋅ z l ) 1/2 , (13)
where { φ n k } k \{\varphi_{nk}\}_k { φ nk } k is an L 2 ( μ ) L^2(\mu) L 2 ( μ ) -orthonormal basis of H n \mathcal{H}_n H n . The second expression follows from the addition theorem used in Proposition 16 . It shows that M n M_n M n does not depend on the basis and is invariant under rotations, reflections and relabelling of Z Z Z . Then
Z is a t -design ⟺ M n ( Z ) = 0 for 1 ≤ n ≤ t , Z\text{ is a }t\text{-design}\iff M_n(Z)=0\text{ for }1\le n\le t, Z is a t -design ⟺ M n ( Z ) = 0 for 1 ≤ n ≤ t ,
so the strength is the largest t t t for which M 1 , … , M t M_1,\ldots,M_t M 1 , … , M t all vanish. Two special cases are worth noting. First, M 1 ( Z ) = ∥ 1 m ∑ j z j ∥ M_1(Z)=\left\lVert\frac{1}{m}\sum_j z_j\right\rVert M 1 ( Z ) = m 1 ∑ j z j is the length of the centroid. Second, M 1 = M 2 = 0 M_1=M_2=0 M 1 = M 2 = 0 is equivalent to a zero centroid together with the isotropy condition ∑ j z j z j T = m 3 I \sum_j z_jz_j^{\mathsf{T}}=\frac{m}{3}I ∑ j z j z j T = 3 m I , which is the 2-design criterion used for ( 16 , 16 ) (16,16) ( 16 , 16 ) below.
We evaluated (13) through the harmonic averages (first form), not the Legendre double sum. The double sum equals M 2 2 M_2^2 M 2 2 , and its roundoff of about 10 − 16 10^{-16} 1 0 − 16 would hide any moment below about 10 − 8 10^{-8} 1 0 − 8 . The harmonic averages are linear in the data and resolve moments down to about 10 − 12 10^{-12} 1 0 − 12 . Table 6 reports M n M_n M n for 1 ≤ n ≤ 7 1\le n\le7 1 ≤ n ≤ 7 at the best run of each case. Every entry is either at most 1.7 × 10 − 9 1.7\times10^{-9} 1.7 × 1 0 − 9 , which is the size expected from the stopping rule (gradient below 3 × 10 − 9 3\times10^{-9} 3 × 1 0 − 9 ), or at least 2.3 × 10 − 3 2.3\times10^{-3} 2.3 × 1 0 − 3 . Nothing lies in between, a gap of six orders of magnitude. We call M n M_n M n vanishing when M n < 10 − 8 M_n<10^{-8} M n < 1 0 − 8 . Any threshold in the gap gives the same strengths:
Table 6. Degree-n n n moments [13 ] of the best configuration in each case (ℓ = 0.8 \ell= 0.8 ℓ = 0.8 , exact eigenspace). Every entry is either below 1.7 × 10 − 9 1.7 \times10^{-9} 1.7 × 1 0 − 9 or above 2.3 × 10 − 3 2.3 \times10^{-3} 2.3 × 1 0 − 3 . The strength is the largest t t t with M 1 , … , M t < 10 − 8 M_1,\ldots,M_t < 10^{-8} M 1 , … , M t < 1 0 − 8 .
t ( 4 , 4 ) = 2 , t ( 4 , 6 ) = 3 , t ( 4 , 8 ) = 1 , t ( 9 , 9 ) = 1 , t ( 9 , 12 ) = 5 , t ( 16 , 16 ) = 2 , t(4,4)=2,\quad t(4,6)=3,\quad t(4,8)=1,\quad t(9,9)=1,\quad t(9,12)=5,\quad t(16,16)=2, t ( 4 , 4 ) = 2 , t ( 4 , 6 ) = 3 , t ( 4 , 8 ) = 1 , t ( 9 , 9 ) = 1 , t ( 9 , 12 ) = 5 , t ( 16 , 16 ) = 2 ,
where t ( s , m ) t(s,m) t ( s , m ) denotes the strength of the best configuration for the pair ( s , m ) (s,m) ( s , m ) . The ( 16 , 31 ) (16,31) ( 16 , 31 ) minimizer is not a 1-design. Its centroid has length M 1 = 1.0 × 10 − 2 M_1=1.0\times10^{-2} M 1 = 1.0 × 1 0 − 2 , and all of M 1 , … , M 7 M_1,\ldots,M_7 M 1 , … , M 7 lie between 2.3 × 10 − 3 2.3\times10^{-3} 2.3 × 1 0 − 3 and 3.1 × 10 − 2 3.1\times10^{-2} 3.1 × 1 0 − 2 , so it is not a design of any strength. The strengths of the tetrahedron, octahedron and icosahedron agree with their known values [29 ] .
The geometry of the minimizers that are not Platonic solids is also informative. For s = 4 s=4 s = 4 and m = 8 m=8 m = 8 the optimizer finds a square antiprism rather than the cube. Its 16 edges come in two lengths, 71.90 ∘ 71.90^\circ 71.9 0 ∘ and 79.82 ∘ 79.82^\circ 79.8 2 ∘ , so it is not the equilateral Tammes antiprism [33 ] , but it has the same combinatorial type. This identification rests on the edge pattern only, we did not test for the D 4 d D_{4d} D 4 d symmetry of the antiprism. The optimizer for s = m = 9 s=m=9 s = m = 9 has twelve nearest-neighbor edges of equal length 69.37 ∘ 69.37^\circ 69.3 7 ∘ and forms a tricapped trigonal prism, consisting of two equilateral triangles at heights ± 0.7095 \pm0.7095 ± 0.7095 and an equatorial triangle rotated by 60 ∘ 60^\circ 6 0 ∘ . This is the combinatorial type of the 9-point Tammes solution [33 ] , but with a smaller separation (69.37 ∘ 69.37^\circ 69.3 7 ∘ against arccos ( 1 / 3 ) = 70.53 ∘ \arccos(1/3)=70.53^\circ arccos ( 1/3 ) = 70.5 3 ∘ ), so it is not the Tammes configuration. We checked that it is invariant under a 3-fold rotation and the horizontal mirror to within 5 × 10 − 9 5 \times10^{-9} 5 × 1 0 − 9 , so its symmetry group contains D 3 h D_{3h} D 3 h , and its inertia tensor is isotropic to within 1%. The m = 16 m = 16 m = 16 , s = 16 s = 16 s = 16 optimizer has zero centroid and an exactly isotropic inertia tensor ∑ j z j z j T = 16 3 I \sum_j z_j z_j^{\mathsf T} = \frac{16}{3}I ∑ j z j z j T = 3 16 I . These two conditions are equivalent to being a spherical 2-design [29 ] . The configuration has six pairs at the tetrahedral angle 109.47°, which is suggestive of tetrahedral symmetry, but we did not test for it. The (16, 31) optimizer has a centroid of length 1.0 × 10 − 2 1.0 \times10^{-2} 1.0 × 1 0 − 2 , and its moments M 1 , … , M 7 M_1,\ldots,M_7 M 1 , … , M 7 are all between 2.3 × 10 − 3 2.3 \times10^{-3} 2.3 × 1 0 − 3 and 3.1 × 10 − 2 3.1 \times10^{-2} 3.1 × 1 0 − 2 (Table 6 ). It is therefore well spread but is not a spherical design, even approximately at the level of the other cases.
To test whether the conclusions above depend on having the exact eigenspace, we repeated the sphere experiments with the data-driven eigenspace used in practice. We drew N = 10,000 N = 10{,}000 N = 10 , 000 uniform points X ⊂ S 2 X \subset S^2 X ⊂ S 2 , computed the full eigendecomposition of the Gaussian kernel matrix (ℓ = 0.8 \ell= 0.8 ℓ = 0.8 ), and took the empirical Mercer eigenvalues and the truncated kernel. With the completed basis of § 2.1 , which accounts for the components of off-data translates in H 0 \mathcal{H}_0 H 0 , Theorem 2 and Corollary 3 hold exactly for μ N \mu_N μ N , and we can compare the sandwich bounds. We used the same ten random starts and the same optimizer as for Table 5 , kept the best run, and compared it with the best analytic configuration from that table. Table 7 and Figure 7 summarize the results.
Table 7. Empirical (N = 10,000 N = 10{,}000 N = 10 , 000 ) versus exact eigenspace on S 2 \mathbb{S}^2 S 2 , ℓ = 0.8 \ell= 0.8 ℓ = 0.8 , best of ten starts. The cross-evaluation columns give the analytic objective at the empirical optimum and the empirical objective at the analytic optimum. Each exceeds the best value of its own objective, so each optimum is specific to its objective.
Figure 7. Sandwich bounds and optimal landmarks on S 2 S^{2} S 2 (ℓ = 0.8 \ell= 0.8 ℓ = 0.8 ) with the empirical eigenspace from N = 10,000 N = 10{,}000 N = 10 , 000 uniform samples (blue) and the exact eigenspace (orange). Each case uses the best of ten random starts. Top left: for s = m s = m s = m , the excess E = ∫ P Z 2 d μ − ∑ i > s λ i E = \int_{P_{Z}^{2}} d\mu- \sum_{i>s} \lambda_i E = ∫ P Z 2 d μ − ∑ i > s λ i (dots) and the interval [ ( λ s − λ s + 1 ) F , λ 1 F ] [(\lambda_s - \lambda_{s+1})F, \lambda_1F] [( λ s − λ s + 1 ) F , λ 1 F ] of Theorem 2 (bars). Top right: for m > s m > s m > s , ∫ P Z 2 d μ \int_{P_{Z}^{2}} d\mu ∫ P Z 2 d μ and the interval [ λ s F , τ s + λ 1 F ] [\lambda_sF, \tau_s + \lambda_1F] [ λ s F , τ s + λ 1 F ] of Corollary 3. Bottom left: best objective value under each eigenspace (bars), with cross-evaluations. Dashes give the empirical objective at the analytic optimum and crosses the analytic objective at the empirical optimum. Bottom right: mesh ratio of the empirical and analytic optima (left axis), and the largest difference between their sorted pairwise geodesic angles (grey bars, right axis, degrees). The angle difference does not depend on rotation, reflection or point labelling.
For every ( s , m ) (s,m) ( s , m ) pair, the integrated power function at the best empirical configuration lies at the lower end of the sandwich bound, and the best empirical F F F values are 1–6% below the analytic ones. The cross-evaluations show that the analytic objective is barely affected by the perturbation because the analytic optima are nondegenerate minima, so a small displacement changes F F F only at second order. The empirical objective lacks the rotational symmetry of the exact problem, and so it pulls the optimum away from the symmetric configuration at first order.
The empirical optima are well spread in every case, with mesh ratios between 1.23 and 1.41, well below the Fibonacci values in Table 5 . They are, however, slightly worse than the exact optima, with mesh ratios higher by 0.014–0.054 and minimum separations smaller by 0.6°–2.8°. The sorted pairwise angles of the two optima differ by at most 1.6°–4.4°, with root-mean-square differences of 0.6°–1.4°. The empirical optima are therefore recognizable distortions of the symmetric configurations rather than different configurations. For instance, the nearest-neighbor angles of the empirical (4, 4) optimum range over 106.6°–109.9° instead of the tetrahedral 109.47°, and those of the (9, 12) optimum range over 61.7°–63.2° instead of the icosahedral 63.43°.
Sampling breaks the rotational symmetry and splits the degenerate eigenvalues, which perturbs the optimal landmarks by a few degrees. We expect this perturbation to shrink as N N N grows, since the eigenvalue splitting does, but we did not vary N N N here. However the qualitative picture that minimizers of F F F are evenly spread with power function near the lower end of the sandwich bound, as well as approximating the symmetric configurations predicted by the exact theory, remains unchanged.
The circle and the sphere
Exact eigenspaces
The objective F F F depends on the kernel only through K Z Z K_{ZZ} K Z Z and K Z Z ( s ) K_{ZZ}^{(s)} K Z Z ( s ) , so it can be evaluated in closed form whenever the Mercer expansion is known explicitly. This happens on the circle and the sphere. With μ \mu μ the normalized uniform measure, the Gaussian kernel K ( x , y ) = exp ( − ∥ x − y ∥ 2 / 2 ℓ 2 ) K(x,y)=\exp(-\lVert x-y\rVert^2/2\ell^2) K ( x , y ) = exp ( − ∥ x − y ∥ 2 /2 ℓ 2 ) is invariant under the rotation group, so its eigenspaces are the irreducible representations of that group and its eigenvalues can be written down. Throughout we set α : = 1 / ℓ 2 \alpha:=1/\ell^2 α := 1/ ℓ 2 , and we index the distinct eigenvalues by frequency (on S 1 S^1 S 1 ) or degree (on S 2 S^2 S 2 ), writing them β k \beta_k β k or β n \beta_n β n to distinguish them from the eigenvalues λ i \lambda_i λ i listed with multiplicity. On the unit sphere ∥ x − y ∥ 2 = 2 − 2 x ⋅ y \lVert x-y\rVert^2=2-2x\cdot y ∥ x − y ∥ 2 = 2 − 2 x ⋅ y , and the kernel therefore takes the form K ( x , y ) = e − α e α x ⋅ y K(x,y)=e^{-\alpha}e^{\alpha x\cdot y} K ( x , y ) = e − α e α x ⋅ y , which is the starting point for both expansions below. We begin with the circle, where the eigenvalues are modified Bessel functions of integer order.
Proposition 15 (Circle). On S 1 S^1 S 1 with μ = d θ / 2 π \mu=d\theta/2\pi μ = d θ /2 π ,
K ( θ , ϕ ) = ∑ k ∈ Z β ∣ k ∣ e i k ( θ − ϕ ) , β k = e − α I k ( α ) , K(\theta,\phi)=\sum_{k\in\mathbb{Z}}\beta_{\lvert k\rvert}e^{ik(\theta-\phi)},\qquad\beta_k=e^{-\alpha}I_k(\alpha), K ( θ , ϕ ) = k ∈ Z ∑ β ∣ k ∣ e ik ( θ − ϕ ) , β k = e − α I k ( α ) , where I k I_k I k is the modified Bessel function of the first kind. The L 2 ( μ ) L^2(\mu) L 2 ( μ ) -normalized real eigenfunctions are 1 , 2 cos k θ , 2 sin k θ 1,\sqrt{2}\cos k\theta,\sqrt{2}\sin k\theta 1 , 2 cos k θ , 2 sin k θ , and β k \beta_k β k has multiplicity 2 2 2 for k ≥ 1 k\geq1 k ≥ 1 , so that λ 1 = β 0 \lambda_1=\beta_0 λ 1 = β 0 and λ 2 k = λ 2 k + 1 = β k \lambda_{2k}=\lambda_{2k+1}=\beta_k λ 2 k = λ 2 k + 1 = β k . Gaps occur only at s = 2 M + 1 s=2M+1 s = 2 M + 1 . For such s s s ,
K ( s ) ( θ , ϕ ) = β 0 + 2 ∑ k = 1 M β k cos k ( θ − ϕ ) , τ s : = ∑ i > s λ i = 1 − β 0 − 2 ∑ k = 1 M β k . K^{(s)}(\theta,\phi)=\beta_0+2\sum_{k=1}^{M}\beta_k\cos k(\theta-\phi),\qquad\tau_s:=\sum_{i>s}\lambda_i=1-\beta_0-2\sum_{k=1}^{M}\beta_k. K ( s ) ( θ , ϕ ) = β 0 + 2 k = 1 ∑ M β k cos k ( θ − ϕ ) , τ s := i > s ∑ λ i = 1 − β 0 − 2 k = 1 ∑ M β k .
Proof. This follows from the generating function e α cos t = ∑ k I k ( α ) e i k t e^{\alpha\cos t}=\sum_k I_k(\alpha)e^{ikt} e α c o s t = ∑ k I k ( α ) e ik t with t = θ − ϕ t=\theta-\phi t = θ − ϕ , since x ⋅ y = cos ( θ − ϕ ) x\cdot y=\cos(\theta-\phi) x ⋅ y = cos ( θ − ϕ ) . The tail formula uses K ( x , x ) = 1 K(x,x)=1 K ( x , x ) = 1 , so ∑ i λ i = 1 \sum_i\lambda_i=1 ∑ i λ i = 1 .
On the sphere the same construction goes through with Legendre polynomials in place of complex exponentials, and the Bessel functions acquire half-integer order. The eigenspaces now have growing dimension, which is why gaps appear at the perfect squares.
Proposition 16 (Sphere). On S 2 S^2 S 2 with μ = d σ / 4 π \mu= \mathrm{d}\sigma/4\pi μ = d σ /4 π ,
K ( x , y ) = ∑ n ≥ 0 β n ( 2 n + 1 ) P n ( x ⋅ y ) , β n = e − α i n ( α ) = e − α π 2 α I n + 1 / 2 ( α ) . K(x,y)=\sum_{n\geq0}\beta_n(2n+1)P_n(x\cdot y),\qquad\beta_n=e^{-\alpha}i_n(\alpha)=e^{-\alpha}\sqrt{\frac{\pi}{2\alpha}}I_{n+1/2}(\alpha). K ( x , y ) = n ≥ 0 ∑ β n ( 2 n + 1 ) P n ( x ⋅ y ) , β n = e − α i n ( α ) = e − α 2 α π I n + 1/2 ( α ) . where P n P_n P n is the Legendre polynomial and i n i_n i n the modified spherical Bessel function. The eigenspace of β n \beta_n β n is the space of spherical harmonics of degree n n n , of dimension 2 n + 1 2n+1 2 n + 1 . Gaps occur only at s = ( M + 1 ) 2 s=(M+1)^2 s = ( M + 1 ) 2 , and then
K ( s ) ( x , y ) = ∑ n = 0 M β n ( 2 n + 1 ) P n ( x ⋅ y ) , τ s = 1 − ∑ n ≤ M ( 2 n + 1 ) β n . K^{(s)}(x,y)=\sum_{n=0}^{M}\beta_n(2n+1)P_n(x\cdot y),\qquad\tau_s=1-\sum_{n\leq M}(2n+1)\beta_n. K ( s ) ( x , y ) = n = 0 ∑ M β n ( 2 n + 1 ) P n ( x ⋅ y ) , τ s = 1 − n ≤ M ∑ ( 2 n + 1 ) β n .
Proof. Use the Funk–Hecke expansion e α t = ∑ n ≥ 0 ( 2 n + 1 ) i n ( α ) P n ( t ) e^{\alpha t}=\sum_{n\geq0}(2n+1)i_n(\alpha)P_n(t) e α t = ∑ n ≥ 0 ( 2 n + 1 ) i n ( α ) P n ( t ) and the addition theorem ∑ k φ n k ( x ) φ n k ( y ) = ( 2 n + 1 ) P n ( x ⋅ y ) \sum_k\varphi_{nk}(x)\varphi_{nk}(y)=(2n+1)P_n(x\cdot y) ∑ k φ nk ( x ) φ nk ( y ) = ( 2 n + 1 ) P n ( x ⋅ y ) for L 2 ( μ ) L^2(\mu) L 2 ( μ ) -orthonormal harmonics. This is consistent with [53 ] .
The practical consequence is that, by Remark 1, the objective needs only K Z Z ( s ) K_{ZZ}^{(s)} K Z Z ( s ) and never an explicit eigenbasis. On S 1 S^1 S 1 this matrix is a short cosine sum, and on S 2 S^2 S 2 it is a Legendre sum that can be evaluated by the three-term recurrence. Both forms are exact, rotation invariant, and compatible with automatic differentiation. No data, no N × N N\times N N × N kernel matrix, and no eigensolver are required, so the only inputs are the bandwidth ℓ \ell ℓ and the truncation level s s s .
The analytic spectra also agree with what a data-driven computation produces. For N = 10,000 N=10{,}000 N = 10 , 000 uniform points on S 1 S^1 S 1 with ℓ = 0.8 \ell=0.8 ℓ = 0.8 , the empirical values λ i = ν i / N \lambda_i=\nu_i/N λ i = ν i / N match β k = e − α I k ( α ) \beta_k=e^{-\alpha}I_k(\alpha) β k = e − α I k ( α ) to within 2%, and we observed a similar agreement on S 2 S^2 S 2 for the empirical spectrum used in § 8 . The empirical eigenvalues within a degenerate pair are split slightly by sampling noise, whereas the analytic pairs are exactly degenerate. That the empirical values converge to the Mercer eigenvalues as N N N grows follows from [54 ] , which justifies using the analytic expressions as the reference in all later comparisons.
Proof of the Aliasing Theorem on the Circle
Proof of Theorem 13. The kernel is K ( θ , θ ′ ) = ∑ n ∈ Z β ∣ n ∣ e i n ( θ − θ ′ ) K(\theta,\theta')=\sum_{n\in\mathbb{Z}}\beta_{\lvert n\rvert}e^{in(\theta-\theta')} K ( θ , θ ′ ) = ∑ n ∈ Z β ∣ n ∣ e in ( θ − θ ′ ) , where β ∣ n ∣ \beta_{\lvert n\rvert} β ∣ n ∣ is the eigenvalue of the frequency-n n n mode. Since β ∣ n ∣ \beta_{\lvert n\rvert} β ∣ n ∣ is nonincreasing in ∣ n ∣ \lvert n\rvert ∣ n ∣ , the top-s s s eigenspace is V s = span { ψ k : ∣ k ∣ ≤ M } V_s=\operatorname{span}\{\psi_k:\lvert k\rvert\leq M\} V s = span { ψ k : ∣ k ∣ ≤ M } with ψ k = β ∣ k ∣ e i k θ \psi_k=\sqrt{\beta_{\lvert k\rvert}}e^{ik\theta} ψ k = β ∣ k ∣ e ik θ and s = 2 M + 1 s=2M+1 s = 2 M + 1 . We use the complex characters in place of the real eigenbasis. This is allowed by Remark 1: F F F depends only on K Z Z ( s ) = ∑ ∣ k ∣ ≤ M β ∣ k ∣ e i k ( z j − z l ) K_{ZZ}^{(s)}=\sum_{\lvert k\rvert\leq M}\beta_{\lvert k\rvert}e^{ik(z_j-z_l)} K Z Z ( s ) = ∑ ∣ k ∣ ≤ M β ∣ k ∣ e ik ( z j − z l ) , which is the same for the real and the complex basis of V s V_s V s . All sums ∑ j β ∣ r + j m ∣ \sum_j\beta_{\lvert r+jm\rvert} ∑ j β ∣ r + j m ∣ converge because ∑ n β ∣ n ∣ = K ( x , x ) < ∞ \sum_n\beta_{\lvert n\rvert}=K(x,x)<\infty ∑ n β ∣ n ∣ = K ( x , x ) < ∞ . Take z j = 2 π j / m z_j=2\pi j/m z j = 2 π j / m , j = 0 , … , m − 1 j=0,\ldots,m-1 j = 0 , … , m − 1 , and define the orthonormal DFT vectors ( f r ) j = m − 1 / 2 e i r z j (f_r)_j=m^{-1/2}e^{irz_j} ( f r ) j = m − 1/2 e i r z j , r ∈ Z m r\in\mathbb{Z}_m r ∈ Z m .
Sampling aliases frequencies, i.e. e i n z j = e i ( n m o d m ) z j e^{inz_j}=e^{i(n\bmod m)z_j} e in z j = e i ( n mod m ) z j , so the sample vector of e i n θ e^{in\theta} e in θ at Z Z Z is m f n m o d m \sqrt{m}f_{n\bmod m} m f n mod m . Therefore
K Z Z = m ∑ r ∈ Z m ( ∑ j ∈ Z β ∣ r + j m ∣ ) f r f r ∗ . K_{ZZ}=m\sum_{r\in\mathbb{Z}_m}\left(\sum_{j\in\mathbb{Z}}\beta_{\lvert r+jm\rvert}\right)f_rf_r^*. K Z Z = m r ∈ Z m ∑ j ∈ Z ∑ β ∣ r + j m ∣ f r f r ∗ .
So K Z Z K_{ZZ} K Z Z is circulant, with eigenvectors f r f_r f r and eigenvalues κ r = m ∑ j β ∣ r + j m ∣ > 0 \kappa_r=m\sum_j\beta_{\lvert r+jm\rvert}>0 κ r = m ∑ j β ∣ r + j m ∣ > 0 .
Likewise K Z Z ( s ) = m ∑ ∣ k ∣ ≤ M β ∣ k ∣ f k m o d m f k m o d m ∗ K_{ZZ}^{(s)}=m\sum_{\lvert k\rvert\leq M}\beta_{\lvert k\rvert}f_{k\bmod m}f_{k\bmod m}^* K Z Z ( s ) = m ∑ ∣ k ∣ ≤ M β ∣ k ∣ f k mod m f k mod m ∗ . If k ≠ k ′ k\ne k' k = k ′ with ∣ k ∣ , ∣ k ′ ∣ ≤ M \lvert k\rvert,\lvert k'\rvert\leq M ∣ k ∣ , ∣ k ′ ∣ ≤ M , then 0 < ∣ k − k ′ ∣ ≤ 2 M < m 0<\lvert k-k'\rvert\leq2M<m 0 < ∣ k − k ′ ∣ ≤ 2 M < m , so k ≠ k ′ ( m o d m ) k\ne k'\pmod m k = k ′ ( mod m ) . Because m ≥ s m\geq s m ≥ s , each residue contains at most one ∣ k ∣ ≤ M \lvert k\rvert\leq M ∣ k ∣ ≤ M , so K Z Z ( s ) K_{ZZ}^{(s)} K Z Z ( s ) has eigenvalue m β ∣ k ∣ m\beta_{\lvert k\rvert} m β ∣ k ∣ at residue k k k and 0 0 0 at the other m − s m-s m − s residues.
By (2) with ψ k ( Z ) = m β ∣ k ∣ f k \psi_k(Z)=\sqrt{m\beta_{\lvert k\rvert}}f_k ψ k ( Z ) = m β ∣ k ∣ f k and K Z Z − 1 f k = κ k − 1 f k K_{ZZ}^{-1}f_k=\kappa_k^{-1}f_k K Z Z − 1 f k = κ k − 1 f k ,
⟨ ψ k , Π Z ψ k ′ ⟩ H = ψ k ( Z ) ∗ K Z Z − 1 ψ k ′ ( Z ) = δ k k ′ a k , a k = β ∣ k ∣ ∑ j ∈ Z β ∣ k + j m ∣ . (14) \langle\psi_k,\Pi_Z\psi_{k'}\rangle_{\mathcal{H}}=\psi_k(Z)^*K_{ZZ}^{-1}\psi_{k'}(Z)=\delta_{kk'}a_k,\qquad a_k=\frac{\beta_{\lvert k\rvert}}{\sum_{j\in\mathbb{Z}}\beta_{\lvert k+jm\rvert}}. \tag*{(14)} ⟨ ψ k , Π Z ψ k ′ ⟩ H = ψ k ( Z ) ∗ K Z Z − 1 ψ k ′ ( Z ) = δ k k ′ a k , a k = ∑ j ∈ Z β ∣ k + j m ∣ β ∣ k ∣ . (14)
since f k ∗ f k ′ = δ k k ′ f_k^*f_{k'}=\delta_{kk'} f k ∗ f k ′ = δ k k ′ for these residues. Summing the leakages, F ( Z ) = ∑ ∣ k ∣ ≤ M ( 1 − a k ) F(Z)=\sum_{|k|\le M}(1-a_k) F ( Z ) = ∑ ∣ k ∣ ≤ M ( 1 − a k ) , which is the stated formula because 1 − a k = ∑ j ≠ 0 β ∣ k + j m ∣ / ∑ j ∈ Z β ∣ k + j m ∣ 1-a_k=\sum_{j\ne0}\beta_{|k+jm|}/\sum_{j\in\mathbb{Z}}\beta_{|k+jm|} 1 − a k = ∑ j = 0 β ∣ k + j m ∣ / ∑ j ∈ Z β ∣ k + j m ∣ . (Equivalently, F = s − tr ( K Z Z − 1 K Z Z ( s ) ) = s − ∑ ∣ k ∣ ≤ M m β ∣ k ∣ / κ k F=s-\operatorname{tr}(K_{ZZ}^{-1}K_{ZZ}^{(s)})=s-\sum_{|k|\le M}m\beta_{|k|}/\kappa_k F = s − tr ( K Z Z − 1 K Z Z ( s ) ) = s − ∑ ∣ k ∣ ≤ M m β ∣ k ∣ / κ k .)
By Step 3, the compression Q s Π Z Q s ∣ V s Q_s\Pi_ZQ_s|_{V_s} Q s Π Z Q s ∣ V s is diagonal in the orthonormal basis { ψ k } \{\psi_k\} { ψ k } of V s V_s V s , with eigenvalues a k a_k a k . These are the cos 2 θ k \cos^2\theta_k cos 2 θ k , hence sin 2 θ k = 1 − a k \sin^2\theta_k=1-a_k sin 2 θ k = 1 − a k , as claimed. The same conclusion follows from symmetry.
Q s Π Z Q s Q_s\Pi_ZQ_s Q s Π Z Q s commutes with the rotation by 2 π / m 2\pi/m 2 π / m , which preserves Z Z Z . The characters e i k θ e^{ik\theta} e ik θ with ∣ k ∣ ≤ M |k|\le M ∣ k ∣ ≤ M are eigenvectors of that rotation with eigenvalues e ∓ 2 π i k / m e^{\mp2\pi ik/m} e ∓ 2 π ik / m , which are pairwise distinct because ∣ k − k ′ ∣ ≤ 2 M < m |k-k'|\le2M<m ∣ k − k ′ ∣ ≤ 2 M < m . A commuting operator is diagonal on a simple spectrum, so each character is an eigenvector of Q s Π Z Q s ∣ V s Q_s\Pi_ZQ_s|_{V_s} Q s Π Z Q s ∣ V s .
The m m m eigenvalues of K Z Z K_{ZZ} K Z Z are κ r \kappa_r κ r , r ∈ Z m r\in\mathbb{Z}_m r ∈ Z m . The factor m m m cancels in the ratio of the largest to smallest:
κ ( K Z Z ) = max r ∑ j β ∣ r + j m ∣ min r ∑ j β ∣ r + j m ∣ . \kappa(K_{ZZ})=\frac{\max_r\sum_j\beta_{|r+jm|}}{\min_r\sum_j\beta_{|r+jm|}}. κ ( K Z Z ) = min r ∑ j β ∣ r + j m ∣ max r ∑ j β ∣ r + j m ∣ .
The residues of − M , … , M -M,\ldots,M − M , … , M now exhaust Z m \mathbb{Z}_m Z m , so Φ \Phi Φ is square and Proposition 6 applies. The matrix R Z R_Z R Z has eigenvalues tan 2 θ k \tan^2\theta_k tan 2 θ k and is diagonal in the same basis. Since tan 2 θ k = sin 2 θ k / cos 2 θ k \tan^2\theta_k=\sin^2\theta_k/\cos^2\theta_k tan 2 θ k = sin 2 θ k / cos 2 θ k ,
tan 2 θ k = ∑ j ≠ 0 β ∣ k + j m ∣ / ∑ j β ∣ k + j m ∣ β ∣ k ∣ / ∑ j β ∣ k + j m ∣ = ∑ j ≠ 0 β ∣ k + j m ∣ β ∣ k ∣ . \tan^2\theta_k=\frac{\sum_{j\ne0}\beta_{|k+jm|}/\sum_j\beta_{|k+jm|}}{\beta_{|k|}/\sum_j\beta_{|k+jm|}}=\frac{\sum_{j\ne0}\beta_{|k+jm|}}{\beta_{|k|}}. tan 2 θ k = β ∣ k ∣ / ∑ j β ∣ k + j m ∣ ∑ j = 0 β ∣ k + j m ∣ / ∑ j β ∣ k + j m ∣ = β ∣ k ∣ ∑ j = 0 β ∣ k + j m ∣ .