2
$\begingroup$

A continuous state space model is defined as follows. $$ \dot{\textbf{x}}(t)=\textbf{A}\textbf{x}(t)+\textbf{B}\textbf{u}(t) \\ \textbf{y}(t)=\textbf{C}\textbf{x}(t)+\textbf{D}\textbf{u}(t) $$

If we want to calculate the state $\textbf{x}$ for a specific time $t$, we need to use the state transition matrix $\Phi$. However, when looking at a discrete state space model, things look different. $$ \textbf{x}[k+1]=\textbf{A}_d\textbf{x}[k]+\textbf{B}_d\textbf{u}[k] \\ \textbf{y}[k]=\textbf{C}\textbf{x}[k]+\textbf{D}\textbf{u}[k] $$

With the discrete state space model, there seem to be no 1st order differential equations incorporated anymore. Instead, we can directly calculate the next sample, without the need for a state transition matrix. How come this is the case?

$\endgroup$
  • $\begingroup$ How could there be a differential equation in discrete time? $\endgroup$ – Matt L. Jul 10 '18 at 19:57
  • 1
    $\begingroup$ in a discrete-time state variable model, $\mathbf{A}_d$ is the state transition matrix. At least for a single sample period. For longer than one sampling period (like from $\mathbf{x}[n_0]$ to $\mathbf{x}[n]$), i believe it the state transition matrix is $$\mathbf{A}_d^{n-n_0}$$ what you have is a first-order difference equation instead of a first-order differential equation. $\endgroup$ – robert bristow-johnson Jul 12 '18 at 8:06
4
$\begingroup$

I will ask you something that will give you intuition.
How would you calculate the Gradient of an image?
Image is a discretization of reality, so how would you estimate the gradient of the "Reality" if you're given only the image?

In the case above we use Finite Differences to approximate the continuous derivative.
So what actually is approximating $ \dot{x} \left( t \right) $ is:

$$ \dot{x} \left( k \Delta t\right) \approx \frac{ x \left[ k + 1 \right] - x \left[ k \right]}{ \Delta t} $$

I do a little abuse of the $ k $ parameter yet I think you can understand what is going on there.

$\endgroup$
  • $\begingroup$ @robertbristow-johnson, First, you should always use \left( and \right). See for instance automated LaTeX generators like codecogs.com/eqnedit.php. Try to click on the brackets. I actually uses only k and k + 1 (Forward Difference). It was a later edit by Matt which used the Central Difference to approximate the derivative. $\endgroup$ – Royi Jul 12 '18 at 6:56
2
$\begingroup$

Hi: I've been wondering about the same exact thing myself and the light bulb finally turned on a few days ago when I went back to Kalman's 1960 paper. ( I've read it many times but not recently ). The paper is at the link below and the short explanation is on the right hand side of page 6. The longer explanation is in the reference (18) which I have but haven't looked at yet. http://sites.math.rutgers.edu/~sontag/kalman4.pdf.

I forget where I got (18) but, if you want it and can't find it, let me know and I can send you a copy. It might be on the internet but I can't recall and didn't bother looking since the shorter explanation might suffice anyway.

$\endgroup$
  • $\begingroup$ \I can tell you for sure the Discrete State equation are discretizations of the Differential equations and indeed Finite Differences Method is used to do so. See for instance how it is done for other Differential Equations - en.wikipedia.org/wiki/Finite_difference_method. $\endgroup$ – Royi Jul 12 '18 at 15:55
  • $\begingroup$ Hi Royi: Ok. I'll check out the wiki. It's still puzzling why Kalman wouldn't use it though. I have a feeling he would have known about that approach !!!! LOL.. $\endgroup$ – mark leeds Jul 12 '18 at 16:09
  • $\begingroup$ Hi: I found some books that discuss it ( gelb, stengle and jazwinski ) and kalman is constructing a solution to the non-stochastic version of the differential equation by using a taylor series explansion. He then takes that solution and converts it to the discrete version of the state space formulation. That's all ll have right now and It's gonna take me a while to understand the details but atleast I know where to look. I don't like jumping into the "middle" of discussions so it's best for me to start say jazwinski from chapter 1 and work up to the discussion. It's on my to-do list. $\endgroup$ – mark leeds Jul 12 '18 at 20:20
  • $\begingroup$ Try the books and presentations of Paul Zarchan. I think he shows the discretization process. $\endgroup$ – Royi Jul 13 '18 at 5:58
  • $\begingroup$ Royi found the following link and used it to answer a related question. This link answers this person's question EXACTLY so I'm putting it here. Thanks Royi. engr.iupui.edu/~skoskie/ECE595_f05/handouts/discretization.pdf $\endgroup$ – mark leeds Jul 18 '18 at 6:30
0
$\begingroup$

A Markov random process has the form

$$ p(x_i\mid x_{i-1},x_{i-2},x_{i-3},\dots x_0)=p(x_i\mid x_{i-1}) $$ State Variables have a similar Markov property. The state $\mathbf{x}(t_{k+1})$ evolves as a function of the present state $\mathbf{x}(t_{k})$ present input $\mathbf{u}(t_{k})$. You don't need any additional previous states to evolve the system to the next state. You don't need any previous $\mathbf{u}(t_{k-1})$ $\mathbf{u}(t_{k-2}) \; \dots $ $\mathbf{u}(t_{0})$. All the history is in the present state $\mathbf{x}(t_{k})$.

A continuous time system with a Markov property would be expressed as a differential equation because the next time, $t+\Delta$ isn't fixed, while for a discrete time process the next time $k+1$ is established from $k$.

The continuous time process can be evaluated at specific times with the state transition matrix and the form of the equations are identical to the discrete time case.

There are systems that are inherently Markov discrete time, there is no implicit differentiation.

In summery, it is the Markov property that both continuous and discrete time equations share.

$\endgroup$
  • $\begingroup$ matt or royi or robert or stanley or anyone else: if you have time and can be bothered, can you look at the paper I linked to and tell me if kalman is really just taking the centered difference approximation to the derivative as described in the other answer. I know you guys know your stuff but, if that was simple, wouldn't he have just done that in the paper ? I have the other paper that has more deails if anyone wants that. Thanks. $\endgroup$ – mark leeds Jul 12 '18 at 5:51
  • $\begingroup$ i hadn't dealt with Kalman filters since grad school. that is 4 decades ago. all i remember is that Kalman represents the system as a state-variable system with an additive noise source to the output $\mathbf{y}[n]$ and then (assuming that the system is "completely observable") makes a good guess at what the state $\mathbf{x}[n]$ is, from the observations of $\mathbf{y}[n]$. i don't remember how it's done anymore. there's a lot from statistical communications theory that i forgot. (since i never really worked in it.) $\endgroup$ – robert bristow-johnson Jul 12 '18 at 8:13
  • $\begingroup$ (with a little paraphrasing): "You don't need any additional previous states to evolve the system to the next state. You don't need any previous $\mathbf{u}([n-1]$ $\mathbf{u}[n-2] \; \dots $ $\mathbf{u}[n_0]$. All the history is in the present state $\mathbf{x}[n]$." That is true. And this is more basic than Kalman filters. It is literally how the state-variable model works whether in continuous time or discrete time. $\endgroup$ – robert bristow-johnson Jul 12 '18 at 8:19
  • $\begingroup$ no problem robert and thanks. I was just wondering whether going from the differential equation formulation to the discrete state space formulation can be done by just using the finite difference derivative approximation or is the approach in the paper that I linked to needed or maybe the two approaches are somehow equivalent possibly. hopefully one of the other DSP gurus will provide their wisdom in the near future. otherwise, I'll just assume that kalman's approach is necessary. $\endgroup$ – mark leeds Jul 12 '18 at 8:19
  • 1
    $\begingroup$ @mark lteeds Getting in the wayback machine with Mr Peabody, Kalman wrote his paper in an analog world. Most people needed help to make the transition from analog to discrete time. $\endgroup$ – Stanley Pawlukiewicz Jul 12 '18 at 17:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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