Using Total Variation Denoising to Clean Accelerometer Data

Question

I know this is maybe a very basic question but I am doing this as a hobby and I can't find a solution to this problem. Basically I am trying to remove some noise from data I am reading from an accelerometer. This is what I want to achieve (Taken from Total Variation Denoising (An MM algorithm)):

I read in Picking the correct filter for accelerometer data that Total Variaton Denoising would fit my needs. So I read Wikipedia - Total Variation Denoising article from Wikipedia and I think I have to use one of this equations:

But I don't understand how I apply this to my signal. Suppose I have a set of x,y points like in the plots above, how I apply the equation to that data? I implemented some simple low-pass and high-pass filters like this:

gravity[0] = alpha * gravity[0] + (1 - alpha) * event.values[0];

But this is maybe too complex and I don't know where to start or how. I want to implement this in Java or C so Matlab is not an option (I have seen a lot of MatLab implementing this). I will appreciate any help to guide me in the right direction!

Answer 1

Apart from Total Variation Denoising you could try a first much simpler approach: a median-filter. You just move a window along your data and replace the current input value by the median of all data in the window. You just have to optimize the window length (by experimenting).

By the way, the equations you copied into your question are for 2-dimensional data, but your data are 1-D.

Answer 2

Well, unless it is a more programming question (how to translate from MATLAB script to C code), you might find interesting the following implementation: click, proposed in this article: A direct algorithm for 1D total variation denoising.

Good luck!

Answer 3

If your data model is Piece Wise Smooth Signal then you should use Total Variation as regularization.

Let's try comparing 2 methods for Denoising with 2 different regularization (Both works on the Derivative of the Signal):

$$ \text{Toal Variation:} \quad \arg \min_{z} \frac{1}{2} {\left\| z - b \right\|}_{2}^{2} + \lambda {\left\| D z \right\|}_{1} $$

$$ \text{Tikhonov Regularization:} \quad \arg \min_{z} \frac{1}{2} {\left\| z - b \right\|}_{2}^{2} + \lambda {\left\| D z \right\|}_{2}^{2} $$

Where $ D $ is the finite difference method.

Both are pretty easy to solve (For small signals even simple Sub Gradient Method will do nicely).

Results

As can be seen while the Tikhonov Regularization decays the noise (Using limiting the derivative) yet leaves a signal which isn't Piece Wise Smooth, the Total Variation Regularization works as intended and almost restore the signal perfectly.

The full code is available on my StackExchange Signal Processing Q14968 GitHub Repository (Look at the SignalProcessing\Q14968 folder).