Non-Uniform Sampling

For decades, digital signal processing has been built on a rigid foundation: data sampled at perfectly regular intervals. This uniformity is the key that unlocks the power of the Fast Fourier Transform (FFT), our primary tool for deciphering the frequency content of signals. However, the real world rarely adheres to such perfect schedules. From astronomical observations blocked by weather to medical scans limited by patient tolerance, data often arrives with unavoidable gaps and irregular spacing. Applying standard tools to this irregular data leads to distorted results, a problem that has long been treated as a nuisance to be corrected. This article explores a paradigm shift in this thinking, reframing non-uniform sampling not as a problem, but as a powerful and efficient solution.

First, in "Principles and Mechanisms," we will delve into why uniform grids fail, exploring concepts like spectral leakage and the Point Spread Function. We will then introduce the specialized tools designed to handle irregular data, from the Lomb-Scargle periodogram to the revolutionary concepts of sparsity and Compressed Sensing. Following this, the "Applications and Interdisciplinary Connections" chapter will showcase how these principles are applied in the real world, enabling breakthroughs in fields as diverse as astronomy, chemistry, medicine, and ecology. By the end, the reader will understand how embracing incompleteness allows scientists to measure faster, see clearer, and model the continuous flow of reality from discrete, imperfect snapshots.

To truly understand non-uniform sampling, we must first appreciate the beautiful, yet rigid, world it seeks to liberate us from: the world of uniform grids and the classical Fourier transform. It’s a story about breaking symmetries, taming ghosts, and discovering that in many cases, the information we seek is so elegantly structured that we need far less data to capture it than we ever thought possible.

For over a century, the Fourier transform has been a cornerstone of science and engineering. It gives us a magnificent recipe for understanding any signal, be it the sound of a violin or the light from a distant star. The recipe says: break the signal down into its constituent pure frequencies—a sum of simple sine and cosine waves. The standard, computationally miraculous way to do this is the Fast Fourier Transform (FFT). But the FFT comes with a strict rule: you must provide it with samples of your signal that are perfectly evenly spaced in time, taken from a uniform grid.

Why this insistence on uniformity? It's because a uniform grid endows the family of sine and cosine waves with a wonderful property: ​​orthogonality​​. Think of the basis functions—$\cos(2\pi k x)$ and $\sin(2\pi k x)$—as the perpendicular axes of a coordinate system. When you sample them on a uniform grid, they remain perfectly perpendicular to each other in a discrete sense. Measuring the amount of a certain frequency in your signal is as simple and clean as projecting a vector onto one of the axes to find its coordinate. Each frequency component can be measured independently, without interfering with the others.

But what happens when we cannot, or do not wish to, sample on a perfect grid? Imagine an astronomer tracking a star; daylight and weather create unavoidable gaps. Or a doctor running an MRI scan; staying in the machine for hours to collect every single data point is impractical. In these real-world scenarios, our sampling points are scattered irregularly. On this irregular set of points, the sine and cosine waves lose their pristine orthogonality. They are no longer perpendicular. Projecting our signal onto one "frequency axis" now casts a shadow on all the others. The energy from a single, pure frequency "leaks" out and contaminates the measurements of other frequencies. This phenomenon, known as ​​spectral leakage​​, is the fundamental sickness that non-uniform sampling must cure. Naively applying an FFT to irregularly spaced data, perhaps by pretending the samples are uniform or by crudely binning them onto a grid, is a recipe for disaster. It introduces severe, unpredictable errors in both the magnitude and phase of the resulting spectrum, creating a distorted caricature of reality. The elegant mathematics of the FFT breaks down completely.

To visualize what goes wrong, we can think of the sampling process as viewing the "true" spectrum of our signal through a special lens. The pattern of this lens's distortion is determined entirely by the sampling pattern. This distortion pattern, in the frequency domain, is called the ​​Point Spread Function (PSF)​​. It is nothing more than the Fourier transform of the sampling schedule itself—a function that is 1 at every point we measured and 0 everywhere else. The spectrum we actually compute is the true spectrum "convolved" with this PSF; in other words, every true spectral peak is blurred and duplicated according to the shape of the PSF.

Let's consider two ways of leaving out data. First, imagine we sample deterministically, keeping only every 10th point of a uniform grid. This highly regular, sparse pattern produces a PSF that is itself a series of sharp, distinct spikes. The result? Our computed spectrum contains the true spectrum plus several coherent, sharp "ghost" copies of it, also known as aliases, shifted to predictable locations. These ghosts can be easily mistaken for real signals, a disastrous outcome for scientific discovery.

Now, consider a different approach: what if we randomly decide whether to keep or discard each point on the original grid? The result is something remarkable. The PSF for this random schedule looks completely different. It has one tall, sharp central peak (which preserves our true signal's position) sitting on a bed of low-level, random, noise-like fluctuations that extend across the entire spectrum. We have traded discrete, dangerous ghosts for a weak, incoherent "grass" of artifacts. The key insight is that these artifacts look like noise, not like a structured signal. And as we will see, this distinction is one that a clever algorithm can exploit.

Faced with the breakdown of the FFT, we must ask: what is our goal? The answer determines the tool we should use.

Sometimes, we don't need to reconstruct the full signal with its phase information. An astronomer might only want to know the dominant periods (frequencies) in a star's brightness variations. In this case, we only need to estimate the ​​power spectrum​​. For this, the ​​Lomb-Scargle periodogram​​ is a brilliant tool. Instead of trying to force a Fourier transform, it takes a more direct approach. For each frequency it tests, it finds the best-fitting sine and cosine wave to the irregularly sampled data points using the principle of least squares. It even cleverly adjusts the phase of the sinusoids at each frequency to maintain a form of orthogonality, making the calculation stable and robust. The resulting "power" at that frequency is a measure of how much that best-fit sinusoid reduces the overall error. It is a method designed from the ground up for irregular data, but it is an analysis tool for power, not a reversible transform for signal filtering or reconstruction.

When we do need to reconstruct the full signal, we need a true replacement for the FFT. This is where the ​​Non-Uniform Fast Fourier Transform (NUFFT)​​ comes in. The direct way to compute a Fourier transform from non-uniform data is to perform the direct summation, but for $N$ data points and $K$ frequencies, this is painfully slow, with a cost of $\mathcal{O}(NK)$. The NUFFT is a masterpiece of numerical ingenuity that speeds this up to nearly the same $\mathcal{O}(N \log N)$ complexity as the standard FFT. The trick is subtle but powerful: instead of forcing the data onto a grid, it takes each irregularly located data point and "spreads" its value with a tiny, smooth kernel onto a few neighboring points of a fine, oversampled uniform grid. Then, it performs a standard, lightning-fast FFT on this new gridded data. Finally, it divides by the transform of the spreading kernel in the frequency domain to correct for the initial spreading. It is a principled, accurate, and fast method that respects the true location of every data point.

For decades, the story of sampling was dominated by the Nyquist-Shannon sampling theorem, which states that to perfectly capture a signal, you must sample at a uniform rate at least twice its highest frequency. Attempting to sample below this rate was thought to be heresy, leading to an irretrievable loss of information. But this theorem comes with a hidden assumption: that the signal could be any possible function up to its maximum frequency.

What if we know something more about our signal? Many signals in the real world are not just arbitrary wiggles. They are ​​sparse​​. An NMR spectrum of an organic molecule isn't a random noise pattern; it consists of a few sharp, well-defined peaks against a flat baseline. A photograph is not random static; it has smooth regions and sharp edges, which makes it highly compressible (the principle behind JPEG).

This assumption of sparsity changes everything. It is the key that unlocks the magic of ​​Compressed Sensing (CS)​​.

Remember our PSF analogy. A random sampling schedule creates artifacts that look like low-level, incoherent noise. A sparse signal, on the other hand, consists of a few strong, coherent peaks. A non-linear reconstruction algorithm can be designed to solve the following puzzle: "Find the sparsest possible spectrum (the one with the fewest peaks) that is perfectly consistent with the few random measurements I actually took." This algorithm can computationally distinguish the structured, sparse signal from the grass-like, non-structured artifacts and eliminate the latter, recovering the true spectrum with stunning fidelity.

This approach shatters the "structured aliasing" problem that plagues uniform grids, especially in high dimensions. The rigid symmetries of a uniform grid can conspire in just the right way to make a sparse signal perfectly cancel itself out at the sampling points, rendering it invisible. Randomness breaks these harmful symmetries, ensuring that any sparse signal will leave a detectable trace.

The practical implications, for example in multi-dimensional NMR spectroscopy, are breathtaking. To achieve a desired outcome, we must follow two classical rules:

1. The underlying grid spacing, $\Delta t$, must be small enough to capture the full range of frequencies—this sets the ​​spectral width​​.
2. The total duration of the measurement, $T_{max}$, must be long enough to distinguish closely spaced frequencies—this sets the ​​resolution​​.

Classically, satisfying both rules meant acquiring a huge number of points, $N$, from $t=0$ to $T_{max}$ with spacing $\Delta t$. But compressed sensing tells us we don't have to! By sampling a random subset of $M$ points across the full duration $T_{max}$, we can preserve the resolution, and by keeping the underlying grid defined by $\Delta t$, we preserve the spectral width. The number of samples $M$ we actually need no longer depends on the grid size $N$, but on the signal's sparsity $K$. In fact, theory shows that $M$ needs to be just slightly larger than $K$, scaling roughly as $M \gtrsim K \log(N/K)$. This allows for monumental reductions in experiment time, turning acquisitions that would have taken days or weeks into a matter of hours.

This new paradigm seems almost too good to be true, and in science, there is rarely a free lunch. The power of non-uniform sampling and compressed sensing comes with important caveats.

The first cost is ​​quantitation​​. The non-linear algorithms used for CS reconstruction, while brilliant at identifying peaks, are not perfect at reporting their true amplitudes. They often employ steps that behave like "soft-thresholding," a process that systematically shrinks the estimated size of peaks. Crucially, this shrinkage is magnitude-dependent: weaker or broader peaks are suppressed more than strong, sharp ones. This breaks the direct proportionality between peak integral and concentration, a relationship that is the bedrock of quantitative analysis in fields like chemistry. Thus, while NUS can give a beautiful qualitative picture in record time, using it for precise quantitative measurements requires extreme care and specialized methods.

The second cost relates to ​​signal-to-noise ratio (SNR)​​. Let's imagine a fair fight: for the same total amount of instrument time, do we get a better SNR by measuring all the points once (uniform sampling), or by measuring a fraction of the points many times (NUS)? For a very simple signal containing just one or a few peaks, the answer is clear: uniform sampling wins. The complex, non-linear CS reconstruction introduces a small but real "noise amplification" factor, $\kappa > 1$, which means the final reconstructed SNR will be slightly lower, by a factor of $1/\sqrt{\kappa}$, than what an ideal uniform acquisition would have achieved.

The true power of non-uniform sampling, therefore, is not in improving the quality of simple signals that are already easy to measure. Its revolutionary impact is in making it possible to acquire complex, sparse signals that were previously beyond our reach due to time constraints. It represents a fundamental shift in perspective: from brute-force data collection to intelligent acquisition, where we leverage prior knowledge about the structure of our signals to capture the essence of reality with astonishing efficiency.

The world, as we observe it, does not march to the steady beat of a metronome. A physician cannot draw a patient's blood every second on the second; a satellite’s view of a distant star is blocked by the Earth for half of its orbit; a biologist studying a lake might be kept away by a storm. Our measurements of nature are almost always intermittent, gappy, and irregularly spaced in time.

For a long time, this was seen as a nuisance, a departure from the idealized, uniformly sampled world of the standard Fourier transform. But as so often happens in science, wrestling with this apparent imperfection has led to a much deeper understanding and an entirely new set of powerful tools. It has even taught us how to be more clever and efficient in how we ask questions of the world. This journey, from making sense of messy data to the art of intentional incompleteness, reveals the profound and unifying role of non-uniform sampling across the sciences.

Let’s start with a simple, practical problem. When a drug is administered, its concentration in the bloodstream rises and then falls as the body metabolizes and eliminates it. A critical measure for pharmacologists is the "Area Under the Curve" (AUC), which represents the total exposure of the body to the drug over time. This is simply the integral of the concentration function, $\int C(t) dt$. But we can't measure $C(t)$ continuously; we only have a handful of measurements from blood samples taken at specific, and often irregularly spaced, times.

How do we compute the integral? One might be tempted to use a sophisticated numerical rule, but the real world of clinical data rewards robustness over complexity. The standard, and wisest, approach is the composite trapezoidal rule. It works by connecting each pair of adjacent data points with a straight line and calculating the area of the trapezoid beneath it. The total AUC is just the sum of these small trapezoidal areas. This method has a simple elegance: it naturally handles any spacing between points, $\Delta t_k$, and because it uses linear interpolation, it will never invent unphysical phenomena like negative drug concentrations between two positive measurements. It is a beautiful lesson in how the simplest tool is often the right one for a messy job, a principle that is the bedrock of pharmacokinetic analysis.

This same fundamental idea—of honoring the actual time intervals between measurements—applies everywhere. It's the same logic an engineer uses to calculate the total energy delivered by a fluctuating voltage source from a series of sporadic sensor readings, and the same principle an ecologist must use to estimate the average change in a lake's biomass from seasonal field trips. To linearly interpolate data onto a uniform grid or, even worse, to simply ignore the time gaps, is to fool oneself. Such practices can systematically underestimate the variability of a system or distort its dynamic properties, leading to false conclusions about the very phenomena we seek to understand.

But what if we are interested not just in the total amount of something, but in its rhythm, its hidden periodicities? This question takes us from the rhythms of the body to the music of the spheres. Astronomers face the ultimate non-uniform sampling problem. Day-night cycles, weather, and the orbits of telescopes mean that our view of any given star is constantly interrupted.

Suppose we are searching for an exoplanet by looking for the tiny, periodic dimming of a star's light as the planet passes in front of it. This is a search for a faint, periodic signal buried in a gappy data stream. If we were to take our unevenly sampled data, fill the gaps with zeros, and feed it into a standard Fast Fourier Transform (FFT), the result would be a disaster. The sharp transitions at the edges of the data segments create a riot of spurious frequencies, a phenomenon called spectral leakage, which can easily swamp the true signal.

This is where a remarkable tool born from necessity, the Lomb-Scargle periodogram, enters the stage. It is, in essence, a Fourier transform redesigned from the ground up to work with unevenly sampled data. Instead of forcing the data onto a rigid, uniform grid, it asks, for every possible frequency, "How well does a sine wave at this frequency fit my scattered data points?" By systematically checking all frequencies, it can pick out the true periodicity with astonishing accuracy, allowing astronomers to detect the subtle signature of a planet orbiting a star hundreds of light-years away. This technique is so fundamental that it's used to analyze everything from the famous 11-year cycle of sunspots from gappy historical records to the variability of quasars.

So far, we have treated non-uniform sampling as a fact of life to be dealt with. But a revolutionary shift in thinking occurred: what if we chose to sample non-uniformly on purpose? This is the gateway to the world of compressed sensing.

The insight is this: many signals and images of scientific interest are "sparse." This means that when represented in the right way (like in the frequency domain), they consist of only a few significant components amidst a sea of zeros. An audio signal is a few dominant frequencies; a medical image is mostly smooth regions with sharp edges. If the object of our interest is sparse, why should we need to measure everything to know what it is?

Consider a multi-dimensional NMR (Nuclear Magnetic Resonance) experiment, a cornerstone of chemistry and structural biology for determining molecular structures. A full 2D or 3D experiment can be agonizingly slow, sometimes taking days, because it requires sampling a massive, uniform grid of points. But a typical NMR spectrum is sparse—just a few sharp peaks. By cleverly measuring a small, random-like, non-uniform subset of the grid points, we can acquire the data in a fraction of the time. Then, a compressed sensing algorithm solves a kind of mathematical puzzle: "Find the sparsest possible spectrum that is consistent with the few measurements I have." By promoting sparsity, often using a technique called $\ell_1$-norm minimization, the algorithm can perfectly reconstruct the full, high-resolution spectrum from the radically undersampled data.

This principle of "doing more with less" extends far beyond spectroscopy. In Mass Spectrometry Imaging (MSI), which creates detailed chemical maps of biological tissues, the same logic applies. Instead of scanning every single pixel—a process that can take many hours for a large sample—one can acquire data from a sparse, spatially-random set of locations. This allows for rapid surveying of large areas. The sampling strategy can even be made intelligent, for example, by stratifying the random samples within different known regions of a tissue to ensure that statistical comparisons between those regions remain valid and powerful. Non-uniform sampling, in this light, becomes a design principle for efficiency.

Our final journey takes us to the problem of modeling systems that are continuously evolving. We have discrete, irregular snapshots, but we believe they are generated by an underlying continuous and dynamic process. How can we reconstruct the full story?

Imagine tracking a ship in a foggy sea. We only get occasional glimpses of its position. Between glimpses, our best guess of its location comes from our model of its dynamics—its speed and heading. When a new glimpse arrives, we update our belief. The crucial ingredient in this process is knowing how long it has been since the last glimpse. This is the essence of the Kalman filter, a powerful tool for state estimation in fields from aerospace engineering to economics. When measurements arrive at irregular intervals, $\Delta t_k$, a correctly formulated Kalman filter must use this varying time step in its prediction phase. To assume a fixed $\Delta t$ when the data is irregular is to have a faulty internal clock, leading the filter to become overconfident or lost, producing nonsensical results.

But what if we want to reconstruct the entire continuous path of the process, not just its state at discrete times? Here we turn to modern non-parametric methods. Techniques like smoothing splines model the unknown trajectory as a flexible curve, elegantly bending to pass near the observed data points. This approach naturally handles irregular spacing and can be embedded within sophisticated statistical models, like the Negative Binomial models used to find genes that transiently switch on and off during development from unevenly-sampled single-cell RNA-sequencing data.

An even more profound idea is found in Gaussian Process (GP) regression. Instead of assuming a particular form for the unknown function, a GP places a probability distribution over the space of all possible smooth functions. The observed data points, no matter how sparsely or irregularly they are spaced, serve to "nail down" this cloud of possibilities, leaving us with a posterior distribution that gives not only the most likely trajectory but also a principled measure of uncertainty at every point in time. This method is incredibly powerful for reconstructing, for instance, the fluctuating trajectories of immune-system molecules (cytokines) from the sparse and irregular blood draws of a clinical study. These models, which explicitly treat time as continuous, provide a robust framework for analyzing irregularly sampled ecological data to detect the "critical slowing down"—a tell-tale rise in variance and autocorrelation—that can act as an early warning signal for a catastrophic ecosystem collapse.

From a simple computational trick to a deep principle of measurement and modeling, the story of non-uniform sampling is a testament to the creativity of science. It teaches us that the messy, unruly rhythm of observation is not an obstacle to be overcome, but a feature of the world to be embraced. By doing so, we have learned to see farther, measure faster, and understand the continuous, flowing reality that lies beneath our discrete and imperfect gaze.