Fast, Stable Jackson Approximation on Spherical Caps via Displacement Structure

Many scientific datasets live on a patch of a sphere rather than the whole globe: a regional weather domain, a satellite footprint, a polar ice cap. Approximation theorists have built smoothing operators for exactly this setting. Jackson-type operators are localized polynomial filters defined directly on a spherical cap, and for them one can prove matching upper and lower bounds on how fast the approximation error falls as the polynomial degree grows. In practice these operators are rarely used. Applying or inverting one on a fine grid of $N$ points costs $O(N^2)$ to $O(N^3)$ with generic dense linear algebra, and nobody has characterized their numerical stability.

This note argues that the matrices behind cap Jackson operators have hidden structure, and that the structure comes from the geometry itself. The cap looks the same under any rotation about its center, so a Fourier transform in the angle around the center splits the problem into independent one-dimensional pieces. Within each piece, the matrix nearly commutes with the tridiagonal "multiply by $\cos\theta$" matrix. In the language of displacement rank, a count of how far a matrix is from commuting with a simple shift-like operator, each piece has displacement rank at most two. That puts cap operators inside the class of matrices that existing fast algorithms can apply and invert in near-linear time. It also gives a cheap computational instrument for an open theoretical question: whether higher-order "Boolean sum" Jackson operators keep their accelerated error rate on caps.

Core Claim

Fix a cap $D(x_0,\gamma)$ of angular radius $\gamma \le \pi/2$ around a center $x_0$. Use polar coordinates about $x_0$, with colatitude $\theta\in[0,\gamma]$ and azimuth $\phi$. Discretize with a product grid: Gauss–Jacobi nodes in $\cos\theta$ on $[\cos\gamma,1]$ and equispaced nodes in $\phi$.

Any operator on the cap that commutes with rotations about $x_0$ becomes block-circulant on this grid. We will check that the Jackson operators $J_{k,s}^m$ of The Direct and Converse Inequalities for Jackson-Type Operators on Spherical Cap, which are built from cap translation operators and Gegenbauer projections, have this property. A fast Fourier transform (FFT) in $\phi$ then reduces the operator to about $k$ independent blocks, one per azimuthal frequency $\mu$.

In the associated-Legendre coefficient basis, the block for frequency $\mu$ contains the cap Gram matrix $G_\mu[\ell,\ell'] = \int_{\cos\gamma}^{1} P_\ell^\mu(x)P_{\ell'}^\mu(x)\,dx$, for degrees $\mu \le \ell,\ell' \le k$. Let $T_\mu$ be the truncated tridiagonal Jacobi matrix encoding the three-term recurrence $xP_\ell^\mu = a_\ell P_{\ell+1}^\mu + b_\ell P_\ell^\mu + c_\ell P_{\ell-1}^\mu$. Then

$$T_\mu G_\mu - G_\mu T_\mu = E_\mu, \qquad \operatorname{rank}(E_\mu)\le 2.$$

The argument is short. Entry $(\ell,\ell')$ of the commutator is $\int_{\text{cap}} \big(xP_\ell^\mu\big)P_{\ell'}^\mu - P_\ell^\mu\big(xP_{\ell'}^\mu\big)$, which vanishes identically. The only exceptions are the last row and column, where truncating at degree $k$ drops the $P_{k+1}^\mu$ term.

This corrects a claim often made about this problem. Restricting to a cap destroys the orthogonality of spherical harmonics, but it does not destroy the three-term recurrence, and the recurrence is what displacement structure needs. The Jackson operator is a polynomial filter composed with this Gram structure, so it inherits low displacement rank, at worst with a small increase. The recurrence-width algorithms of Recurrence Width for Structured Dense Matrix Vector Multiplication then apply each block and solve with it in $\tilde O(k)$ operations. The full cap operator on $N\sim k^2$ points costs $\tilde O(N)$ instead of $O(N^2)$ to apply. Solving goes from $O(k^4)=O(N^2)$ with dense per-block factorization, or $O(N^3)$ with no structure at all, down to $\tilde O(N)$.

Two consequences matter as much as the speed. First, the tridiagonal $T_\mu$ gives a stable way to compute a spectral decomposition of each block. That allows truncated pseudoinverses and Tikhonov-regularized inverses for the ill-conditioned systems that dense cap grids produce. Second, the Boolean sums $\oplus^r J_{k,s} = I-(I-J_{k,s})^r$ become cheap to apply at high degree, so we can measure their error decay directly on caps.

Relation to Prior Work

The closest precedent is The fast Slepian transform. It shows that the one-dimensional time-frequency concentration matrix is Toeplitz and splits as circulant plus a rank-$O(\log N\log(1/\epsilon))$ correction. It uses this to compute projections and regularized inverses in $O(N\log N\log(1/\epsilon))$, and it names spherical and two-dimensional extensions as open. We take the step to caps, but through a different mechanism. The colatitude blocks are not Toeplitz, so we use exact commutation with a Jacobi matrix rather than circulant-plus-low-rank. We also aim the result at Jackson operators, whose error theory is already known. Geophysics has studied cap concentration problems with azimuthal decoupling, but none of that work is in our search results. We treat the azimuthal splitting as standard and claim novelty only for the displacement characterization, the fast and stable inversion built on it, and its use for Jackson and Boolean-sum operators.

Two papers supply the algorithms. The recurrence-width framework of Gu et al. (Recurrence Width for Structured Dense Matrix Vector Multiplication, A Two-pronged Progress in Structured Dense Matrix Vector Multiplication.) computes $Ab$, $A^Tb$ and $A^{-1}b$ in $\tilde O(t^\omega n)$ for matrices defined by one-dimensional polynomial recurrences, where $t$ is the recurrence width and $\omega$ the matrix-multiplication exponent. Our contribution is to show that the cap problem reduces to a family of such one-dimensional problems. The authors flag that the stability of their divide-and-conquer approach in floating point is uncharacterized. We therefore also build a tridiagonal-eigensolver route and compare the two. The skew-circulant inversion formulas of A new Toeplitz inversion formula, stability analysis and the value and Skew cyclic displacements and decompositions of inverse matrix for an innovative structure matrix require strict Toeplitz or cyclic structure. They cover only the azimuthal direction here, where plain circulants are enough.

The approximation theory constrains what we can claim. The Direct and Converse Inequalities for Jackson-Type Operators on Spherical Cap proves error $O(k^{-2})$ matched to the second-order modulus of smoothness. Its constants depend on $\gamma$ in an uncharacterized way. Approximation by boolean sums of Jackson operators on the sphere proves the $r$-th Boolean sum reaches $O(k^{-2r})$, but only on the full sphere, where orthogonality of global harmonics makes the algebra work. On caps, boundary terms could cap the rate at something below $k^{-2r}$. This is an open question our fast solver lets us probe numerically. It is not a claim we make.

For singular systems, A Singular Woodbury and Pseudo-Determinant Matrix Identities and Application to Gaussian Process Regression handles rank-deficient Gaussian-process systems, for example with improper priors on a linear trend. It uses the Bott–Duffin inverse, a generalized inverse restricted to a subspace, implemented with dense algebra in detkit. We keep its identities and replace the dense inner solves with our structured ones.

Research Program

Stage one is algebraic. We first verify that the discrete Jackson operator is block-circulant, meaning it commutes with rotations about $x_0$. If Wang and Cao's cap translation breaks that symmetry, we will report it and fall back to Gram and interpolation systems, which remain structured. We then derive the exact displacement generators of $J_{k,s}^m$ and of $\oplus^r J_{k,s}$ in each azimuthal block. Finally, we prove a bound on displacement rank as a function of $s$, $m$ and $r$. We expect a small constant for $J_{k,s}^m$ and at most linear growth in $r$ for Boolean sums, since each extra factor of $(I-J)$ adds a bounded commutator term.

Stage two is algorithmic. We implement two solvers for each block. The first is the recurrence-width solver of Gu et al. The second is a commuting-tridiagonal eigensolver that diagonalizes the block through $T_\mu$ and then applies truncated or Tikhonov inverses spectrally. We wrap both inside the Bott–Duffin identities so they can handle singular trend-constrained fits.

Stage three is analytical and numerical. We measure forward error against extended-precision references as the condition number grows. We map how the constant $C_{m,\gamma}$ behaves as $\gamma\to 0$ and as $\gamma\to\pi/2$. We also estimate the achieved decay exponent of $\|\oplus^r J_{k,s}f - f\|$ on caps for $r=1,2,3$.

Baselines

Naive reference. The simplest baseline assembles the discrete cap operator as a dense $N\times N$ matrix. It applies the operator by dense multiplication and solves by Cholesky or LU, with Tikhonov regularization when ill-conditioned. This fixes ground-truth accuracy up to $N\approx 2\times10^4$ and fixes the cost curve that any structured method must beat.

Strongest competitor. Azimuthal FFT followed by dense per-block Cholesky factorization. This baseline already exploits the rotational symmetry and costs $O(k^4)$, which is $O(N^2)$. It is the baseline a numerical analyst would build first. It isolates exactly what displacement structure adds beyond symmetry. It uses the same grid, quadrature and regularization, and gets the same optimized BLAS (dense linear algebra) libraries and hardware. Beating it means lower wall-clock time at matched relative error ($10^{-10}$ for well-posed solves, and matched regularized residual for ill-posed ones) for $k\ge 512$. It also means no worse forward error across condition numbers. We expect the dense-block route to win at small $k$, in line with the small-size overhead reported in Structured Transforms for Small-Footprint Deep Learning, and we will report the crossover honestly.

Iterative baseline. Conjugate gradient with fast operator application, run unpreconditioned and with a per-block diagonal preconditioner. This tests whether a direct structured solver is needed at all. It receives the same tolerance, and we count total operations including the number of iterations.

Singular-system baseline. detkit from A Singular Woodbury and Pseudo-Determinant Matrix Identities and Application to Gaussian Process Regression. It is used for trend-constrained cap Gaussian-process regression, with our structured inner solves swapped in as the only change. We found no reported cap-domain result on Lacuna for this baseline or any other. That paper reports no numerical runtimes, only that its singular identities are "significantly faster than legacy approaches" when basis functions are numerous. All reference numbers will therefore come from our own reruns.

Ablation. The key-ingredient ablation keeps everything fixed but replaces the displacement-rank-2 generators with a generic hierarchical low-rank compression of each block at matched tolerance. This separates the benefit of the exact algebraic structure from the benefit of simply compressing a smooth kernel.

Why not just…?

Why not just use global spherical harmonics with a mask or taper? Masking reproduces the boundary problem that cap operators were designed to avoid. Global harmonics restricted to a cap are no longer orthogonal, and a sharp mask causes Gibbs-type oscillation at the edge. The research file points to this failure (§5.1), and the fast Slepian paper documents the analogous leakage in one dimension. We include this approach as an accuracy comparison: same degree, error measured within a band near the cap boundary. We expect it to be competitive in the cap interior, which we will state if it happens.

Why not just flatten the cap and use planar FFT solvers? For small caps this is a genuine threat, because the distortion from projection shrinks as $\gamma\to0$. We will measure the gap as a function of $\gamma$. Our prediction is that the planar method matches ours for small $\gamma$ and loses on hemispheres, where metric distortion is large. Evidence that bases matched to the geometry approximate better (On the Approximation Power of Splines: Orthogonal Versus Hexagonal Lattices, Wavelets on the sphere: implementation and approximations) motivates this expectation but does not settle it. If flattening wins even at $\gamma=\pi/2$, the practical case for this project shrinks to the Boolean-sum study.

Why not just use azimuthal FFT plus dense blocks, or a low-rank compression? The dense-block route is the strongest baseline above, and at moderate resolution it may be good enough. Plain low-rank compression is a weaker option, for two reasons. The cap operator has many eigenvalues near one, the same obstruction the fast Slepian transform identifies in one dimension. And Structured Transforms for Small-Footprint Deep Learning found displacement rank 1–2 outperforming low-rank layers that used 16 times more parameters. The hierarchical low-rank ablation tests this claim directly on our operators.

Proposed Experiments

Test fields. We use ERA5 fields from WeatherBench (WeatherBench: A Benchmark Data Set for Data-Driven Weather Forecasting), namely Z500 geopotential and 2-meter temperature at the 1.40525° resolution. We extract caps with $\gamma\in\{5^\circ,15^\circ,45^\circ,90^\circ\}$ centered over regions including the North Atlantic and the Arctic, and resample them to our product grids at degrees $k$ from 64 to 2048. That gives $N$ up to about $4\times10^6$. We complement these with synthetic functions of prescribed smoothness, for which the smoothness moduli are known analytically. The published WeatherBench numbers are forecasting RMSEs (for example IFS about 154 m²/s² at three days). They measure a different task, so they are not baselines here. We borrow only the benchmark's cosine-latitude-weighted RMSE as our error metric.

Decisive checks. The first is the displacement-rank measurement: numerical rank of $T_\mu A_\mu - A_\mu T_\mu$ across all blocks, degrees and $r$. If it grows with $k$, the central claim fails. The second is the runtime and accuracy crossover against FFT-plus-dense-blocks, where we require a win at $k\ge512$ with matched error. The third is forward-error scaling against condition number for the recurrence-width solver versus the tridiagonal eigensolver. This directly addresses the stability question left open by Gu et al. and by Wang and Cao. The fourth is the fitted exponent of Boolean-sum error on caps on synthetic smooth functions. A measured rate near $k^{-2r}$ would support extending the full-sphere theorem to caps. A rate that stalls near $k^{-2}$ would localize a boundary obstruction worth proving. Either outcome is informative. The fifth is end-to-end trend-constrained Gaussian-process regression on the ERA5 caps, comparing detkit's dense path with our structured path on runtime and log-determinant agreement.