Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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
2  
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
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. –  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
add comment

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
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. –  J. M. Aug 24 '10 at 2:17
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. –  J. M. 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... –  J. M. Aug 24 '10 at 3:13
1  
...though, if pursuing the polynomial fitting approach, one can almost always do better than the monomial basis. –  J. M. Aug 24 '10 at 3:18
show 2 more comments

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
add comment

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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.