Take the 2-minute tour ×

Here is a time sample: $Q = \{(t_i, x_i) | 0 \leq x_i \leq x_{i+1}, 1 \leq i \leq n\}$

and rules:

(1) $T_1 \leq t_{i+1} - t_i < T_2$ where $T_1, T_2 > 0$

(2) $x_i$ comes with error:

$x_i = \lfloor x(t_i) \rfloor$ where $\lfloor x \rfloor$ - whole part of $x$, $x(t_i)$ - voluntary unknown law of object motion.

How we can find (approximately but sufficiently accurate) speed of the object at the given time?

share|improve this question
I must be dumb, I don't understand this question. :/ –  BBischof Aug 11 '10 at 16:14
I have tried to convert to latex. If I messed up please let me know/edit it. –  Aryabhata Aug 24 '10 at 2:50
I think $x_{t_i}$ should be changed back to $x(t_i)$. There are two x's in this problem. The subscripted $x_1,\dots,x_n$ are a given list of numbers, while $x(t)$ is a function. –  Laurent Lessard Aug 24 '10 at 3:07
@Laurent: Fixed that. Please let me know if there is more to be fixed. –  Aryabhata Aug 24 '10 at 3:20
Yes, the subscripted $x_1,…,x_n$ are a given list of numbers obtained by the measurement system, while $x(t)$ is a unknown nondecreasing function that describes the path traveled by the object at the given time (it's similar to the total number of steps traversed in a trip). –  Max Nov 21 '10 at 20:55

3 Answers 3

If I understand the question correctly, we are given real numbers $0 \leq x_1 \leq \dots \leq x_n$, and real numbers $0 < t_1 < \dots < t_n$. We also have some unknown differentiable function $x(t)$ that satisfies: $$ x_i \leq x(t_i) < x_i+1 \quad for\quad i=1,2,\dots ,n $$ Our goal is to estimate $\frac{d}{dt}x(t)$.

Suppose we are interested in the derivative at some point $t_0$. It is clear that the constraints above do not constrain the possible values of the derivative at $t_0$. Indeed, given any set of $x_i$ and $t_i$, one could find an admissible function $x(t)$ for which the derivative at $t_0$ is anything we want it to be. So unless we know something more about the "law of motion" governing x, there isn't a reasonable way to estimate the velocity.

In the absence of more information, I'll just assume that x is a polynomial. This will enforce some sort of smoothness. Finding the lowest-degree polynomial that satisfies all the constraints can be cast as a linear program. To see how, suppose that our polynomial is of degree k. Namely, $x(t) = a_0 + a_1 t + \dots + a_{k}t^k$. Then, consider the LP: \begin{align*} minimize &\quad z \\ \text{subject to:}&\quad 0 \leq x(t_i) \leq z\quad i=1,\dots,n \end{align*} Start with $n=0$, and keep increasing until you find an optimal $z$ that is less than 1. Now that you have your polynomial approximation for $x$, you can easily evaluate its derivative anywhere.

share|improve this answer
LP would be appropriate if you're fitting a polynomial to minimize with respect to either $\|\mathbf{x}\|_\infty$ (Chebyshev norm) or $\|\mathbf{x}\|_1$ (Manhattan norm); least squares would be fine most of the time, though. If the data exhibits non-polynomial behavior, however (e.g. asymptote-like behavior), then fitting globally to a single polynomial is poor form. –  Guess who it is. Aug 24 '10 at 2:17
...and examples like the Runge phenomenon inspire the oft-quoted rule of thumb that anything higher than a quartic fit to error-contaminated data might not be a good idea. –  Guess who it is. Aug 24 '10 at 2:30
@Mangladan -- while the 2-norm may be appropriate in typical scenarios (e.g. a signal corrupted by Gaussian noise), the error specified in OP's problem is precisely an infinity-norm constraint. You're absolutely right that fitting globally to a polynomial (esp deg > 4) can be a poor choice. It depends on where the underlying x comes from. –  Laurent Lessard Aug 24 '10 at 3:02
Yes, I really do wish there was a functional form given to work with... –  Guess who it is. Aug 24 '10 at 3:13
...though, if pursuing the polynomial fitting approach, one can almost always do better than the monomial basis. –  Guess who it is. Aug 24 '10 at 3:18

Since you mention that your $x_i$ is error-contaminated; the sanest solution (in the absence of other pertinent information that could be used to simplify your problem, e.g. a conjectured functional form for $x(t)$) would be probably a smoothing spline; this is a similar but probably more amenable proposal to Laurent's, with the advantage that any bad nonpolynomial behavior your data might exhibit can be confined to only a few intervals.

I don't know what computing environment you're using, but MATLAB at least has smoothing splines in its Spline Toolbox (check the documentation for syntax and proper use); and there are FORTRAN programs developed by Carl de Boor (in fact, the MATLAB toolbox was based on these old FORTRAN programs) @ NetLib ; pppack is the particular library you want.

share|improve this answer

You can try the Kalman filter.

share|improve this answer
well, thanks.. i'll look into this subject! –  Max Oct 24 '10 at 16:32
Can you help me to apply Kalman filter to the described problem? First, we need to use the following inequality constraints: $x_i \le x_{i+1}$ and respectively $\frac{dx}{dt}(t_i) \ge 0$. Second, the measurement error (the fractional part of $x$) not a random white noise value. So we need to use some special modification of the Kalman filter. –  Max Dec 12 '10 at 7:53

Your Answer


