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?

  • 2
    I must be dumb, I don't understand this question. :/2010-08-11
  • 0
    I have tried to convert to latex. If I messed up please let me know/edit it.2010-08-24
  • 1
    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.2010-08-24
  • 0
    @Laurent: Fixed that. Please let me know if there is more to be fixed.2010-08-24
  • 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.

  • 1
    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.2010-08-24
  • 1
    ...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.2010-08-24
  • 0
    @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.2010-08-24
  • 0
    Yes, I really do wish there was a functional form given to work with...2010-08-24
  • 1
    ...though, if pursuing the polynomial fitting approach, one can almost always do better than the monomial basis.2010-08-24
  • 0
    what do you mean "do better"? All bases that span the polynomials of degree $k$ are equivalent; the LP above has the same feasible set of functions $x(t)$ regardless of how I choose to parametrize the polynomials.2010-08-24
  • 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
    well, thanks.. i'll look into this subject!2010-10-24
  • 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