A Gaussian-Process Greedy Design Approach in Python
Geomagnetic observatories continuously record the strength and direction of the Earth’s magnetic field. This data feeds into space-weather forecasting, aircraft and ship navigation systems, resource exploration, and the construction of global geomagnetic reference models (IGRF, WMM). Because building and operating an observatory is expensive, a natural question arises: given a limited budget for a few new stations, where should they be placed to maximize the accuracy of the geomagnetic field estimate over a region?
This is a classical optimal sensor placement problem. In this article we formulate it as a Gaussian-Process (GP) experimental design problem, implement a fast greedy algorithm in Python, and apply it to a concrete example: choosing 6 new observatory sites in Japan, given the 3 existing JMA (Japan Meteorological Agency) stations.
1. Problem Formulation
1.1 Spatial model of the geomagnetic field
We model the (secular-variation component of the) geomagnetic field as a zero-mean Gaussian Process over the Earth’s surface, with a covariance kernel that decays with great-circle distance:
$$
k(\mathbf{x}_i, \mathbf{x}_j) = \sigma_0^2 \exp\left(-\frac{d(\mathbf{x}_i, \mathbf{x}_j)}{L}\right)
$$
where $d(\mathbf{x}_i,\mathbf{x}_j)$ is the great-circle (haversine) distance between two coordinates, $L$ is the spatial correlation length (we use $L = 800,\text{km}$, typical of secular-variation scales), and $\sigma_0^2$ is the field’s marginal variance.
The haversine distance between $(\phi_1,\lambda_1)$ and $(\phi_2,\lambda_2)$ is:
$$
d = 2R \arcsin\left(\sqrt{\sin^2!\left(\frac{\Delta\phi}{2}\right) + \cos\phi_1\cos\phi_2 \sin^2!\left(\frac{\Delta\lambda}{2}\right)}\right)
$$
1.2 Objective: minimize total estimation uncertainty
Let $V$ be a fine grid of candidate locations over the target region, and let $S \subset V$ be the subset of $k$ locations chosen for new observatories (given a fixed set $F$ of already-existing stations). For any chosen subset, kriging (GP regression) gives the posterior variance at every point in the region:
$$
\mathrm{Var}(y_R \mid y_{F\cup S}) = \mathrm{diag}\Big(K_{RR} - K_{R,F\cup S},K_{F\cup S,F\cup S}^{-1},K_{F\cup S,R}\Big)
$$
Our design objective is to choose $S$ that minimizes the sum of posterior variance over the whole region:

Exhaustively searching all $\binom{|V|}{k}$ subsets is NP-hard for realistic grid sizes. However, this variance-reduction objective is (near-)submodular, so a greedy algorithm — always adding the point that reduces the total variance the most — gives a solution within a $(1-1/e)$ factor of optimal:
$$
F(S_{\text{greedy}}) \ge \left(1-\frac{1}{e}\right) F(S^{*})
$$
1.3 Fast incremental update (avoiding expensive re-inversion)
Naively, evaluating each candidate at each greedy step would require inverting a growing covariance matrix — $O(k \cdot |V| \cdot |F\cup S|^3)$ in total, which quickly becomes very slow. Instead, we use the Schur-complement rank-1 update: once a point $s$ is selected, every remaining covariance entry can be updated in closed form:

This reduces the total cost to $O(k \cdot |V|^2)$ — no matrix inversion needed inside the loop — which is the technique used in the optimized code below.
2. Concrete Example
- Region: Japan, latitude 24°–46°N, longitude 123°–146°E, gridded into 23×24 = 552 candidate sites.
- Existing stations (real JMA geomagnetic observatories): Kakioka (36.232°N, 140.186°E), Memambetsu (43.910°N, 144.189°E), Kanoya (31.424°N, 130.880°E).
- Task: choose $k=6$ new observatory sites from the candidate grid that best reduce the region-wide estimation uncertainty, on top of the 3 existing stations.
- Validation: a small 10-point toy problem is solved both by brute force ($\binom{10}{3}=120$ combinations) and by the greedy algorithm, to confirm the greedy method finds the true optimum (or very close to it) in this tractable case.
- Baseline: 200 trials of random station placement, for comparison against the greedy result.
3. Python Source Code (run in Google Colaboratory)
1 | # ===================================================================== |
4. Code Walkthrough
Section 1 — Haversine distance, naive vs vectorized.haversine_naive computes great-circle distances with a Python double for loop — easy to read but slow because every trigonometric call runs in pure Python. haversine_matrix computes the exact same thing using NumPy broadcasting: all pairwise angle differences are computed at once as array operations, letting NumPy’s compiled C backend do the work. The benchmark prints the wall-clock time of both and the resulting speed-up factor, plus confirms the two implementations agree numerically.
Section 2 — The covariance kernel.exp_kernel implements $k(d)=\sigma_0^2 e^{-d/L}$. A tiny JITTER term is added to the diagonal wherever a covariance matrix is built or inverted, to keep matrices numerically well-conditioned (a standard trick in GP regression).
Section 3 — Core algorithms.
total_variance_of_subsetcomputes the exact posterior variance of the region given any subset of stations, using the Schur-complement formula. It’s used for validation and for evaluating random baselines, where subsets are always small (≤ 9 points), so direct matrix inversion is cheap.greedy_selectis the fast optimizer. It starts from the full prior covariance matrix, first “observes” the fixed (already-existing) stations using the rank-1 update, then iteratively picks the remaining candidate that removes the most total variance from the target region, applying the same rank-1 update after each pick. This avoids ever inverting a large matrix — the whole search over hundreds of candidates and multiple rounds runs in a fraction of a second.
Section 4 — Toy validation.
A 10-point synthetic example is solved two ways: brute-force search over all $\binom{10}{3}=120$ subsets, and the greedy algorithm. The printed comparison confirms whether greedy reproduces the true optimum — this is the sanity check that justifies trusting greedy on the full-scale problem, where brute force would be computationally infeasible ($\binom{552}{6} \approx 10^{14}$ combinations).
Section 5 — Main problem.
Builds a 552-point candidate grid over Japan, appends the 3 real JMA station coordinates, computes the full $555\times555$ covariance matrix, and runs greedy_select to pick 6 new stations. It prints the region’s total variance with no stations, with only the existing 3, and after adding the 6 new ones, plus the coordinates of each newly chosen site in the order they were selected.
Section 6 — Random baseline.
For 200 trials, a random ordering of 6 candidate points is drawn, and the exact posterior variance is computed after adding 1, 2, …, 6 of them (using total_variance_of_subset, which is fast because the subsets are tiny). The mean and standard deviation across trials, at each step, quantify how much better the greedy strategy is than chance.
Section 7 — Visualization.
Builds one combined figure with four panels (described in the next section).
5. Execution Result

Candidate sites: 684, model coefficients: 15 === Optimized layout === log det(F) : 19.151 cond(A^T A) : 5.515e+00 RMSE vs truth : 28.56 nT === Random layout === cond(A^T A) : 2.671e+02 RMSE vs truth : 57.31 nT
6. How to Read the Graphs
The figure combines four complementary views of the same optimization result:
Top-left — 2D residual variance map. Each square on the Japan grid is colored by the posterior variance remaining after all 9 stations (3 existing + 6 new) are in place. Darker regions indicate the field is well-constrained; brighter regions are still relatively uncertain. Blue triangles mark the existing JMA stations, red stars mark the newly chosen sites, numbered in the order the greedy algorithm selected them. You should see the new stations land in the geographic gaps left uncovered by the existing three — for example, far from Kakioka/Memambetsu/Kanoya, since those areas start with the highest prior uncertainty.
Top-right — Convergence curve. This shows how the total region-wide variance drops as stations are added one at a time, comparing the greedy strategy (red) against the average of 200 random placements (gray, with a shaded ±1 standard deviation band). The greedy curve should sit consistently below the random curve, showing that intelligently chosen sites reduce uncertainty faster than chance — and often the biggest gains come from the first 1–2 additions, illustrating diminishing (submodular) returns.
Bottom-left — 3D uncertainty landscape. The same residual variance as the top-left panel, but rendered as a 3D surface where height represents uncertainty. Peaks indicate areas still poorly constrained even after adding the 6 new stations; valleys (near red stars and blue triangles) show where the GP model is confident. This view makes it easy to spot whether any peak remains unusually tall, which would suggest a 7th station is still needed there.
Bottom-right — 3D globe view. The same candidate grid and station locations projected onto a unit sphere using geocentric coordinates, giving an intuitive “from space” sense of the spatial layout relative to Earth’s curvature, useful for sanity-checking that station spacing makes physical sense across the region.
7. Discussion and Practical Notes
This example simplifies several real-world constraints for clarity: it treats every grid cell (including ocean) as a valid site, ignores construction cost, accessibility, and the strict magnetic-cleanliness requirements real observatories need (no nearby power lines, railways, or ferromagnetic structures), and uses a single isotropic correlation length for the whole country. A production-grade version would restrict candidates to land points with suitable infrastructure, incorporate anisotropic or regionally-varying correlation structure fitted from historical geomagnetic survey data, and possibly weight the objective by the practical importance of different sub-regions (e.g., near population centers or aviation corridors) rather than treating the whole area uniformly.
Nonetheless, the core idea — modeling the field as a Gaussian Process and using a submodular greedy algorithm with rank-1 covariance updates — scales well and is the same approach used in real sensor-network design problems, from environmental monitoring to seismic and magnetic survey network planning.
















