Seed-independent Nonuniform Sampling
A general framework for sparse sampling

It is becoming more and more common for NMR spectroscopists to nonuniformly sparsely subsample their signals in the time domain, a technique referred to as Nonuniform Sampling, or NUS. While I was playing around with one of the more widely used sampling methods, called Poisson-gap, I ended up describing a highly general multidimensional gap sampling framework. Under gap sampling, each sampled data point is determined from the previously sampled data point in the current trace by a simple recurrence relation:

where $g(x_i)$ is referred to as a ‘gap equation’. Multidimensional gap sampling schedules are built up recursively from lower-dimensional sub-schedules according to the above relation. The popular Poisson-gap method obeys a stochastic gap equation by drawing from a Poisson distribution at each evalution of its gap equation. The related sine-gap and sine-burst methods, developed in parallel with the framework, obey deterministic gap equations and require no pseudorandom number generators.

The generality of the gap sampling framework was so tempting that I decided
to write a sampling program that could use any user-supplied gap equation.
The **gaputil** program was the result, and wraps the
Julia mathematical programming language to
interpret almost any conceivable gap equation during schedule generation.

Following on the heels of gap sampling, I decided to investigate if probability density-based sampling methods could be stripped of their pseudorandom seed dependence. Indeed, using Sub-random number sequences, it was possible.

In fact, sub-random numbers could be used to augment the deterministic gap
equations for added incoherence in the resulting NUS schedules. The
**rejutil** and **jitutil** programs were the fruits of this labor, and
the **gaputil** program was also expanded to admit sub-random numbers
into its deterministic gap equations.

To show that seed-independent sampling can produce schedules that perform similarly to stochastic methods, a Monte Carlo simulation was run. An ensemble of Poisson-gap samples was constructed. Synthetic and real time-domain data were then subsampled using both the ensemble of Poisson-gap schedules and the gap-framework schedules, and residuals from Iterative Soft Thresholding (IST) reconstruction were computed and compared.

The results were interesting. Sine-gap and sine-burst sampling using the general framework yielded residuals that were comparable or better to Poisson-gap sampling. This is a first for seed-independent sampling methods, which have until now been regarded as inferior to pseudorandomly sampled methods.

The **nusutils** programs are all fairly portable C, but require Julia for
equation interpretation. They’re hosted on GitHub: