2
$\begingroup$

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?

  • 0
    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).2010-11-21

3 Answers 3

1

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.

  • 0
    Well, using the monomial basis implies having to manipulate a Vandermonde matrix (no matter what norm you're minimizing in), and this can be ill-conditioned depending on point order and distribution. One could instead choose to use a Bernstein or orthogonal basis, and the matrix from these basis sets stands a better chance of being well-conditioned since the basis functions "don't look very much alike". Of course, if sticking with the rule of thumb I gave in a comment earlier, worries of ill-conditioning are probably moot and academic.2010-08-24
1

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.

1

You can try the Kalman filter.

  • 0
    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.2010-12-12