Differentiating Truncated Data

thegreenlaser

I don't have a ton of experience in numerical methods, so I'm hoping someone can help me out. Suppose I have a sequence of position data points for a car, but they've been truncated to integer values. I want to find the speed (derivative), but for speeds which are low relative to the time between measurements, I find that repeated measurements kill my evaluation of the derivative. For example, if the actual position sequence of the car was {0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9}, it would be measured as {0, 0, 0, 0, 1, 1, 1, 1, 1}. So if I apply a simple difference operator, instead of getting a constant speed like the actual position sequence implies, I would be getting mostly zero speed with a sudden spike at the point where the measured position changes from 0 to 1.

So my question is, how do I properly differentiate data that looks truncated or stepped like this? (noting that I need to be able to do it in real time, i.e. without using any future data points) I've tried a few different things, but have only had marginal success. Any suggestions would be greatly appreciated.

haruspex

You need a mathematical model (based on physical considerations) for what the underlying data might look like. The simplest would be constant speed, next a constant accn, etc. The number of parameters should be rather less than the number of datapoints. E.g. with only 3 or 4 datapoints go for constant speed; with 8 or 9 you might justify an acceleration term.
Having chosen the model(s), find the parameters that give the best (least squares) fit to the data. So for constant speed it would be a straight line fit.
A more sophisticated approach could involve background knowledge, like expected limits on acceleration (which might depend on the speed).
All of that should be manageable in real time, but the results might still not be wonderful.

Stephen Tashi

As haruspex indicates, your question doesn't have a definite answer since you haven't provided enough "givens" to solve it or to define what a "proper" way would be. Perhaps if you describe the actual real life problem, some more "givens" will be revealed.

We should start by using better terminology. Your goal isn' t to "differentiate the data". Your goal is apparently to estimate the velocity of an object from truncated position data. To define a "proper" way, we need to know the penalties for making an error. And what is the overall objective of computing the velocity. Is it an end in itself? Or are you trying to aim a gun to hit a moving target or something where the velocity is merely an aid to the final objective?

thegreenlaser

I guess I was hoping for some more general solutions to the problem of truncated data, and the velocity was just an example of it. However, since those general solutions don't seem to exist, I'll give a little more info. Basically I'm trying to implement a PID controller on a small robot car (which should never exceed about 1 m/s^2 acceleration, though that's a very rough value). To implement the feedback loop, I need to be able to accurately estimate the velocity in real time (i.e. using the current position, and the last n positions). I need accuracy, because if the estimated velocity is too high or too low, it causes the car to over/under-react. In particular, the truncated data causes the derivative to swing wildly, which makes the car's movement very jerky, which is unacceptable.

By the way, since I posted the initial question my group members and I hacked out a solution (involving a moving average), which works just well enough to make the car's motion acceptably smooth. I'm still very curious to hear what someone who knows something about numerical methods would have to say about this problem, though.

Stephen Tashi

The bottom line of this problem is to control the car. Since you are doing something to exert force on the car then what you do is another "given". The deluxe approach to control problems is called Kalman filtering. This implies more than filtering the data from one variable (such as the velocity data.) It requires setting up the physics of the problem and I don't know if the method handles data where some of the measurement error is due to truncation. We should investigate that question.

I'm not an expert on Kalman filtering, but I might be able to help you with the math just to the extent that i've read about now and then. The engineering sections of the forum would be the place to ask about actually implementing something on a PID controller.

thegreenlaser

The Kalman filtering thing is interesting. I'll read up on it and post here again if I'm having any trouble with it.

Stephen Tashi

I see people write articles about Kalman filtering with "quantized data". Perhaps truncated measurements fall into that category.