ergodic-sampling/findings.md

# Sampling patterns, reconstruction methods, and how they relate to ground-truth structure

Written 2026-09-12. Refer to [ergodic_sampling_test.py](ergodic_sampling_test.py) for analysis and figures.

## What the analysis tested

The analysis found here: https://code.karsttech.com/jeremy/ergodic-sampling, uses a 64 by 64 grid and
keeps only 11.8% of the cells (484 samples), placed either on a sparse grid (every third cell) or in
the "ergodic" irregular pattern from the Ergodic Sampling paper (found by minimizing equation 4). 
From those samples we rebuild the full grid with several methods and measure how much the reconstruction
differs from the ground truth. The value of merit plotted is RMS error: the typical size of the difference
between the reconstruction and the true field at a cell, and normalized to be scale invariant.
Each RMS error value shown is the average over 25 iterations with a freshly generated ground truth.

The reconstruction methods:

- **Spline interpolation**: fits a smooth surface through the sample points. This is the
  conventional baseline the paper also compares against.
- **Compressive sensing**: the paper's method, iterative thresholding that assumes the signal is
  built from a small number of components in some transform. It is run two ways: with a Fourier
  transform (components are sinusoidal waves) and with the symlet wavelet from the paper.
- **Kriging**: the interpolation method from geostatistics, not used in the paper; it was added
  as a strong reference and a frequently used tool for modeling gravity and magnetic data. It 
  estimates each empty cell as a weighted average of the samples, where the weights come from a 
  model of how similar the field tends to be at each separation distance. The similarity model 
  is itself estimated from the samples, so kriging adapts to the data: for a smooth field it 
  interpolates broadly, and for structureless data it learns that the samples saynothing about 
  their neighbors and backs off.

The three kinds of ground truth:

- **White noise (control)**: every cell is an independent random number. There is no structure at
  all, so nothing between the samples can be predicted. This serves as a good control because it 
  emphasizes any tendency of the reconstruction to hallucinate structure based on its
  assumptions about the data.
- **Fourier-sparse**: a sum of 12 sinusoidal waves, half of them varying too quickly for the
  sparse grid to follow. This is exactly the kind of signal compressive sensing is designed for,
  and matches the paper's own demonstration signal.
- **Potential-field**: a smooth random map that mimics the paper's gravity survey data.

## Some summarized results

RMS error, mean plus or minus spread over 25 trials (best per column in bold):

| method | white noise (control) | Fourier-sparse | potential-field |
|---|---|---|---|
| sparse + spline | 1.218 ± 0.018 | 0.514 ± 0.093 | 0.068 ± 0.012 |
| sparse + compressive sensing (Fourier) | 1.076 ± 0.014 | 0.111 ± 0.132 | 0.812 ± 0.152 |
| sparse + kriging | 1.014 ± 0.005 | 0.480 ± 0.085 | **0.059 ± 0.010** |
| ergodic + spline | 1.443 ± 0.044 | 0.693 ± 0.116 | 0.161 ± 0.030 |
| ergodic + compressive sensing (Fourier) | 1.063 ± 0.009 | **0.000 ± 0.000** | 0.251 ± 0.044 |
| ergodic + compressive sensing (symlet) | 1.282 ± 0.030 | 0.716 ± 0.113 | 0.138 ± 0.026 |
| ergodic + kriging | **1.001 ± 0.005** | 0.569 ± 0.091 | 0.095 ± 0.016 |

![Figure 1](plt3.png)

*Figure 1. Reconstruction error broken down by sampling pattern + reconstruction formulation. Bar
color shows the sampling pattern with blue for sparse grid and orange for ergodic. Bars are the mean 
over 25 trials per truth class. The dashed line in the left panel marks the best score attainable
on structureless / random data, which is predicting zero at every unsampled cell (0.94).*

## Some probably unsurprising results

**1. On truly random ground truth, ergodic + kriging came out best of everything tested.**
When the field has no structure, the smartest possible move is to admit it by outputting the mean
(zero) at every unsampled cell, which scores 0.94 on our scale. Ergodic + kriging lands essentially
on that mark (1.001) because its similarity model is estimated from the samples, and correctly 
concludes the samples carry no information about their neighbors, so it barely interpolates at all.
As expected, every method with a built-in belief about structure does worse than the 
guess-zero-everywhere answer: spline draws smooth hills that do not exist (1.22 on the sparse grid, 
1.44 on the ergodic pattern) and the symlet version paints in wavelet texture (1.28). The 
misprediction gap of up to ~50% worse than guessing zero is the cost of hallucinated 
structure made concrete.

**2. On the potential-field ground truth, the plain sparse grid is the best pattern (figure 3).** 
This field is smooth enough that every third cell is dense enough sampling, the situation classical
sampling theory covers. Here the sparse grid wins simply on coverage. The ergodic pattern, being 
irregular, leaves larger gaps which costs about 1.6 times the error margin. That cost is the
premium for insurance that pays out on the Fourier-sparse truth, where half the signal varies too
fast for the sparse grid: there the sparse grid garbles the fast waves into false slow ones
(this is traditional destructive aliasing, compare the sparse-grid and ergodic columns of
figure 2). THIS CASE IS MOSTLY THEORETICAL: sparse sampling's win here does not carry over to
real applications for two reasons. First, the rough scale of variation is always a known prior
in practice (it is how any sample spacing gets chosen at all), but acting on that prior does not
lead to a comfortably dense regular grid: any scale at where we knew there were no spatial
frequencies smaller than what uniform spacing resolves would be better served by sensing the same 
area with fewer, ergodically spaced samples. The regular grid's win in this column is really a
statement that its sample budget was larger than the known field scale required. Second, for
potential fields in particular, variation much finer than the survey scale reflects shallow
sources rather than the deep signal of interest, which is why this ground truth is generated
with a source-depth attenuation term. See the "Potential Future Work" section for some related
thoughts.

![Figure 2](plt1a.png)

*Figure 2. One realization of the Fourier-sparse ground truth with all eight pattern and method
combinations. Top row: the ground truth on the left followed by each reconstruction, labelled with 
its leakage and RMS error. Middle row: the signed error of each reconstruction, on a single shared color
scale. Bottom row: the sampling locations that produced the column above. Ergodic sampling with Fourier 
compressive sensing on a Fourier-sparse ground truth recovers the field exactly, leaving a blank error
panel. Every sparse sampling method captures only the slow part of the field and leaves the unobserved
high frequency error.*

![Figure 3](plt1b.png)

*Figure 3. The same layout for one realization of the potential-field ground truth. Because this field is
smooth on the scale of the sample spacing, every method except Fourier compressive sensing reproduces it
closely; Fourier compressive sensing insists on a handful of dominant waves and hallucinates high frequency
noise, which shows up as the striped error panel in its column. What error remains for the other methods
gathers in the widest gaps between samples, which is why the more even coverage of the sparse grid wins 
here: its farthest cell from a sample is 1.41 cells away, against 3 cells for the ergodic pattern.*

**3. Matching the reconstruction method to how the ground truth was generated wins, as expected.**
Each column of the table is won by the method whose built-in assumption mirrors the generator: 
kriging on the smooth random fields (its fitted similarity model actually recovers the
generator's parameters exactly), Fourier compressive sensing on the sum-of-waves signal, and
kriging again on noise because it alone can gracefully back off to predicting zero. Mismatches
are dramatically worse: Fourier compressive sensing assumes a few dominant waves and scores 0.812 
on the smooth field, and the symlet version, which assumes the wrong kind of building block for a
sum-of-waves signal, reaches only 0.716 where the Fourier version is exact.

## Predicting the error without the ground truth

Everything above scores a reconstruction against a truth we happen to know, but in a real survey the 
the practical question is whether the reconstruction can say, by itself, where it is likely to be wrong. 
Kriging answers that for free: alongside an estimate at every cell it reports the standard deviation of 
that estimate, computed from the sample locations and from a similarity model fitted to the sample values 
alone. No ground truth enters at any point.

Figures 4 to 7 test that predicted error map for both ground truth classes and for both the kriging and
the symlet compressive sensing reconstruction. Each figure has the same layout. The top row shows the
truth, the reconstruction, and their signed difference. The middle row puts the truth-free predicted
standard deviation beside two things it should resemble: the error actually measured over 64 independent
truths drawn from the same generator and sampled with the same pattern, and the absolute error in the
single realization above. The bottom row shows the sampling pattern, a cell-by-cell scatter of predicted
against actual error, and a calibration curve in which cells are binned into deciles of the prediction.
Fixed axes are chosen so that the results are directly comparable from figure to figure, not just subplots.

Two cautions matter when reading these. First, one realization of an error is one draw of a random
variable, so even a perfect prediction correlates with it only up to a ceiling, which is printed on each
scatter panel. The comparison against the 64-truth ensemble is a test showing the prediction tracks the 
actual error pattern with correlations of 0.90 to 0.99. Second, uniform ergodic coverage intentionally 
flattens the predicted map, since the whole point of the pattern is to leave no cell poorly covered, and 
that narrow range is what pushes the single-realization ceiling down. The calibration curves run close to 
the one-to-one line in every case, slightly below it, meaning the predicted magnitudes are roughly correct.
**One takeaway here** is not the magnitude of the error mismatch between the single realization and the 
predicted error map, but it's structure. If the error map is dominated by high frequency variations on the 
scale of a discovered anomaly like an ore deposit, then smaller variations would be expected to average 
out over the span of the contiguous region of the anomaly and thus a more precise estimate of the size and 
extent of the anomaly could be gathered than by a simply measuring the reconstruction. This is because we 
can leverage the structure of the ergodic sampling points and their implied error structure to reign in 
the uncertainty in our anomaly predictions.

![Figure 4](plt2a1.png)

*Figure 4. Fourier-sparse ground truth, ergodic sampling, kriging reconstruction. Kriging is the wrong
prior for this field class, so the errors are large, but the predicted map still identifies where errors
are most likely.*

![Figure 5](plt2a2.png)

*Figure 5. Fourier-sparse ground truth, ergodic sampling, symlet compressive sensing reconstruction: the
same predicted map tested against a reconstruction built on symlet wavelets. Provided as a direct 
comparison to the reconstruction methods used in the paper.*

![Figure 6](plt2b1.png)

*Figure 6. Potential-field ground truth, ergodic sampling, kriging reconstruction. This is the matched
case, where the fitted similarity model recovers the generator's parameters, and it is where the
prediction is most accurate.*

![Figure 7](plt2b2.png)

*Figure 7. Potential-field ground truth, ergodic sampling, symlet compressive sensing reconstruction.
Provided as a direct comparison to the reconstruction methods used in the paper.*

## The bigger picture

Choosing how to reconstruct in essence is a choice about how much you trust what you know about
the underlying signal. A correct guess about signal structure rewards all the way up to perfect
recovery with minimal samples when the assumption is exactly right. The same choices punish wrong
assumptions: a method that expects structure will manufacture it out of nothing, and on our 
structureless control every such method lost to simply predicting zero, with kriging only slightly
worse than predicting zero. The paper's ergodic pattern is best understood in this light: it is 
deliberately designed without any knowledge of the signal, as insurance that keeps every option open.
Alongside it, our error-prediction experiment (figures 4 to 7) shows that a map of the expected 
error at every cell can be computed from nothing but the sample values and their locations, and 
it tracks the actual error pattern closely (correlation 0.90 to 0.99 against the error measured over 64
independent trials, with correctly calibrated magnitudes).

## Does kriging reconstruction strictly dominate symlet wavelet reconstruction?

Largely yes. Kriging beat symlet compressive sensing in every Monte-Carlo column above, and a
follow-up test showed it wins even on truths that are exactly sparse in the symlet basis: the
decimated wavelet transform and point sampling are both spatially localized, a coherent pair that
violates compressive sensing's incoherence requirement. Two caveats: for signals of a few isolated
wavelet-like anomalies (the paper's Figure 15 regime) symlet keeps a relative edge, though at
11.8% sampling both methods there do worse than predicting zero; and for sparse-spectrum signals
Fourier compressive sensing, not kriging, is the right choice (exact recovery kriging cannot
match). Symlet was never the best with any of my ground-truth construction methods.

The potential-field truths are generated from the same stationary covariance family that kriging
fits, so it's no coincidence that kriging is the mathematically optimal reconstruction; its dominance
is a statement about matched assumptions and generalizability, not about kriging being universally
superior. This is tangential to the main purpose of the paper (chosen ergodic sample spacing),
and I only mention it because kriging seems to be more applicable to magnetic and gravity sensing.

## Potential future work

Since we have shown that for cases where no small scale variation exists to capture, sparse sampling
wins due to optimal coverage; we know that in such a case Ergodic sampling would still be superior 
if we knew at what distance scale local variation existed and further reduced our sample count.

I propose the following:

Develop a sampling procedure which optimizes for collection cost in two collection scenarios
 - Where travel is the dominant cost
   - This applies to survey type collection where a vehicle carrying a sensor is used
   - Compute an optimal survey path which leverages Ergodic sensing methods but reframed as a
     densely sampled path; choosing the path dynamically as sensed signal spatial scales are discovered.

 - Where number of sample locations are the dominant cost
   - This applies to satellite-pointing type collection or ground-station collection
   - Compute an optimal survey path which leverages Ergodic sensing methods, but is scale-adaptive.
     Rather than having coverage sparsity as a prior, this would discover the required coverage
     dynamically to attain a certain reconstruction confidence metric.

Both scenarios should ideally attempt to iteratively estimate a confidence level based on how much future
predictions match the current model (created from previous samples), and therefore determine when sampling
should stop due to being sufficient for our confidence interval goals.