In the previous article we considered how noise reduction filters may be useful in practical applications. In this article we walk through the mathematical and technical aspects of implementing the noise reduction filters used there. We conclude with final remarks comparing our regularization operators to the broader class of moving averages.  The reader is assumed to be conversant in elementary calculus.

Mathematical definition

In this section we build up to the mathematical definition of our discrete mollifier transforms. Considerations of implementation are found in the appropriate sections below.

The continuous case

Pulling a rabbit out of the hat, consider the standard mollifier with parameter epsilon:

the constant A > 0 being chosen so that

To be particular,

The standard mollifiers are smooth (infinitely differentiable) functions vanishing outside the neighbourhood of the origin with radius epsilon.

The insight is that convolution against the standard mollifiers produces smooth functions, even if the original function undergoing the convolution is highly irregular. To be precise, introduce the integral operator sending a function to its convolution against the standard mollifiers:

We call this the mollification of u with parameter epsilon. The convolution is well-defined whenever u is locally integrable in the Lebesgue sense, in which case its mollification is in fact a smooth function. We have thus obtained the smoothing operator in the continuous case:

It is from the good convergence properties of the mollifications back to the original function, as epsilon tends to zero, that the procedure gains its attractiveness. We will not delve into further details on that matter here, preferring instead to turn our attention to the discretization of the mollification operators themselves.

The discrete case

To discretize the mollification operators, we approximate the integrals defining the mollification of a locally integrable function u by means of the trapezoidal rule. Other schemes for numerical quadrature may be applied, but the trapezoidal method reduces in the final analysis down to a particularly nice convolutional form suitable for efficient implementation on a computer, and obtains satisfactory error bounds.

Construe now u as being sampled at n equidistant points, indexed from 0 to n-1, and take epsilon to be k≥1 times the mesh size. Abusing notation ever so slightly, the integral we wish to approximate at index j is thus

Sparing the reader the inevitable juggling of indicies, the discrete mollification of u at index j works out to be

at least for indicies j satisfying 0 ≤ j-k < j+k ≤ n-1, that is, for k ≤ j ≤ n-k-1. It is this form we next seek to implement.

Implementation

We consider the naive implementation of the discrete mollification in Python. It is a simple exercise to port this snippet into any sensible programming language. Readers concerned with efficiency may consult the following subsection and optimize as they see fit.

Translating the discrete mollification operator above into Python directly produces:

The effectiveness of the discrete smoothing operator defined above may be witnessed in the following figure.

Optimizations

Considering the convolutional form of the discrete mollification operators, the computational efficiency may be improved by precomputing the weights for various k and performing the convolution in a more optimized fashion, say through scipy.signal.fftconvolve. We undertake no such endevaour here.

Correcting the tails

The attentive reader may have noticed that the first and last k sample points of the original signal are left unaltered by our implementation, producing noisy artifacts at the tails of our filtered signal. This is undesirable and easy to fix.

Remembering that the discrete mollification is only defined for indicies j satisfying k ≤ j ≤ (n-1)-k, we may simply pad our signal at both ends so as to achieve these inequalities for the portion of the padded signal corresponding to the original signal. In code:

Here is the result:

Comparison with the class of moving averages

We now conclude with a brief comparison of our discrete mollifiers with the broader class of moving averages. A moving average is a convolutional operator of the form

with the weights summing to unity:

Even though our discrete mollifiers are not strictly of the moving average type, they are so asymptotically. Indeed, one may show the estimate

for some constant M≥0 independent of k, proving

Summary

In this article we have undertaken the construction, analysis, and implementation of a family of discrete smoothing operators. Furthermore, the convolutional form of these operators paves the way for efficient implementation in any programming language, making noise reduction filters broadly available. We also related the discrete mollifiers defined here to the broader class of moving averages, discovering their asymptotic membership to this class.

Smoothing Out Noisy Signals Using Discrete Mollifier Transforms – Part 2

We present a family of discrete regularization operators, suitably adapted to remove noise from time series data. The operators are discrete analogues of their continuous mollifier counterparts, which are well-known in the literature on partial differential equations for producing smooth approximations of irregular functions. In this article we demonstrate the utility of the noise reduction filters on electrocardiographic data, after which a technical discussion is presented in part two of this two-part series.

Time series

Time-dependent data may only be sampled at discrete points in time, thus producing a discrete sequence of observations. Such a time-sampled sequence is usually referred to as a time series.

Examples of time series include electrocardiograms (ECG) from hospital patients and name popularity trends over time, the first of which is discussed in more detail below. Other examples include digital audio signals, the evolution of stock prices, et cetera.

Noise

Sampling continuous phenomena over time is not always smooth sailing. The famous Shannon–Nyquist theorem is a classical example providing sufficient conditions on the sampling rate of a signal, that is, the number of samples per second, to avoid such effects as aliasing; it tells us that sampling at a rate twice that of the highest frequency occuring in the signal will be sufficient.

Another challenge presented to us is noise. Even if the underlying phenomenon being sampled is of a continuous, or even smooth, nature, the procedure of sampling a signal generally introduces noise as an artefact on top of the true signal which one wants to capture – measured data which is not really there.

It is therefore natural to ask if it is possible to remove the noise and recover the true, underlying signal. Many such techniques do indeed exist, and the noise reduction filters presented here were developed by the author when he was working as a summer intern on the Pacertool project at Simula Research Laboratory in the summer of 2019.

Removing noise from electrocardiographic (ECG) signals

During the summer of 2019 at Simula Research Laboratory, the author was tasked with the creation of tools for automated analysis of ECG signals. This entailed in part the automatic detection of QRS complexes in such signals.

An ECG signal is produced by placing electrodes on the patient's limbs and chest to record the electrical activity of their heart, thereby producing a waveform of the type which is here exemplified by public data from WFDB:

An algorithm for automatic QRS detection in ECG signals must be able to precisely pinpoint the onsets (Q) and offsets (S) of the complex, a task which is readily seen to be complicated by the presence of noise. Indeed, signal spikes produced by the noise may fool the algorithm into premature onset or offset detection, or even into thinking there is a QRS complex where there is none.

A common remedy is to preprocess the signal by smoothing out noise before pinpointing the complexes, here achieved by the discrete mollifier transform to be studied in more detail in part two of this series:

Conclusion

There are plenty of situations where noise reduction of time series data is desirable, and the techniques for doing so are well within reach for anyone with minimal programming experience. Here we had a brief look at situations where noise reduction is beneficial. In the next article, we take a mathematical and technical look at how the particular class of discrete mollifier transforms used above are defined, implemented, and how they relate to other common regularization operators. See you there!

Algorithms

Smoothing Out Noisy Signals Using Discrete Mollifier Transforms – Part 2

Smoothing Out Noisy Signals Using Discrete Mollifier Transforms