First, some background: I've done some Kalman filters "for pretend" and they always worked out just fine. Now I'm doing one for a client, and of course it's blowing up in my face -- go figure. What's happening is that the state covariance matrix is acquiring some negative eigenvalues, followed shortly by the whole thing rapidly and exponentially growing (bang). It's an extended Kalman filter, in which I'm doing some slightly questionable (i.e. rectangular) numerical integration. I don't know if that's a good candidate for the culprit, so I don't want to go to the effort to fix it unless there's a good chance that it's the problem (or one of them). The question: What sorts of things should I be looking for to see _why_ this dratted thing is blowing up in my face? How likely is it that I'm seeing a numerical instability vs. a real true problem with my formulation? (I've got a pretty wide spread of state values -- from millions down to hundredths, and variances that range from 100s to .001s). If it's a problem with the formulation, are there any tools to tell? I'm working out of Dan Simon's "Optimal State Estimation" book, and the only thing he says about the Extended Kalman Filter is that "it can sometimes be unstable and hard to tune", but he doesn't say _why_, or how to figure out if yours is, or if there are any kluges or fixes that can be applied. And finally -- I used to frequent an applied math newsgroup that was pretty good, but I can't figure out which one. Does anyone have any recommendations about the right place to cross-post this question? Thanks in advance... -- Tim Wescott Wescott Design Services http://www.wescottdesign.com Do you need to implement control loops in software? "Applied Control Theory for Embedded Systems" gives you just what it says. See details at http://www.wescottdesign.com/actfes/actfes.html
Kalman Filter Instability
Started by ●November 25, 2008
Reply by ●November 25, 20082008-11-25
On 25 Nov, 21:55, Tim Wescott <t...@seemywebsite.com> wrote:> First, some background: > > I've done some Kalman filters "for pretend" and they always worked out > just fine. > > Now I'm doing one for a client, and of course it's blowing up in my face > -- go figure....> I'm working out of Dan Simon's "Optimal State Estimation" book, and the > only thing he says about the Extended Kalman Filter is that "it can > sometimes be unstable and hard to tune", but he doesn't say _why_, or > how to figure out if yours is, or if there are any kluges or fixes that > can be applied.Check out section 6.3, page 158. There is a description of numerical issues you may or may not find familiar. There is also the discussion of the unscented filter (chapter 14) which is motivated by problems with the extended filter. Durbin and Koopman's "Time Series Analysis by State Space Methods" discusses various methods for initializing the filters in chapter 5. They suggest to start with an accurate method, to achieve rapid convergence, but simlify the update equations after convergence has been reached "before the filter starts diverging, as it eventually will" (can't easily find the exact reference). Rune
Reply by ●November 25, 20082008-11-25
Rune Allnor wrote:> On 25 Nov, 21:55, Tim Wescott <t...@seemywebsite.com> wrote: >> First, some background: >> >> I've done some Kalman filters "for pretend" and they always worked out >> just fine. >> >> Now I'm doing one for a client, and of course it's blowing up in my face >> -- go figure. > ... >> I'm working out of Dan Simon's "Optimal State Estimation" book, and the >> only thing he says about the Extended Kalman Filter is that "it can >> sometimes be unstable and hard to tune", but he doesn't say _why_, or >> how to figure out if yours is, or if there are any kluges or fixes that >> can be applied. > > Check out section 6.3, page 158. There is a description > of numerical issues you may or may not find familiar. > There is also the discussion of the unscented filter > (chapter 14) which is motivated by problems with the > extended filter. > > Durbin and Koopman's "Time Series Analysis by State Space > Methods" discusses various methods for initializing the > filters in chapter 5. They suggest to start with an > accurate method, to achieve rapid convergence, but simlify > the update equations after convergence has been reached > "before the filter starts diverging, as it eventually > will" (can't easily find the exact reference). >Thank you. Your note (plus a certain amount of desperation) has set me to studying, and I can see only two possibilities for my covariance matrix losing positive definiteness. One, I'm using a cheesy one-step numerical integration (of equation 13.32 in Simon's book). The equation states that dP/dt = AP + PA' + LQL'; I'm "cheating" this to get an update: P_n+1 = P_n + (AP_n + P_nA' + LQL')(dt) I don't see a guarantee that my AP + PA' is positive definite, so I may be losing it here. I can fix this by moving the cheesy integration to my (pretend) system, such that F = (I + A(dt)), and P_n+1 = F P_n F' + LQL'(dt) Sick sick sick, but barring numerical problems at least my eigenvalues should stay positive, right? If that doesn't do the trick, then I'll either play with my units to keep the matrix better conditioned, or I'll learn all about square root algorithms (it makes more sense to me to smooth the units out no matter what, then use square root algorithms if I have to, anyway). -- Tim Wescott Wescott Design Services http://www.wescottdesign.com Do you need to implement control loops in software? "Applied Control Theory for Embedded Systems" gives you just what it says. See details at http://www.wescottdesign.com/actfes/actfes.html
Reply by ●November 25, 20082008-11-25
On 25 Nov, 23:47, Tim Wescott <t...@seemywebsite.com> wrote:> Rune Allnor wrote: > > On 25 Nov, 21:55, Tim Wescott <t...@seemywebsite.com> wrote: > >> First, some background: > > >> I've done some Kalman filters "for pretend" and they always worked out > >> just fine. > > >> Now I'm doing one for a client, and of course it's blowing up in my face > >> -- go figure. > > ... > >> I'm working out of Dan Simon's "Optimal State Estimation" book, and the > >> only thing he says about the Extended Kalman Filter is that "it can > >> sometimes be unstable and hard to tune", but he doesn't say _why_, or > >> how to figure out if yours is, or if there are any kluges or fixes that > >> can be applied. > > > Check out section 6.3, page 158. There is a description > > of numerical issues you may or may not find familiar. > > There is also the discussion of the unscented filter > > (chapter 14) which is motivated by problems with the > > extended filter. > > > Durbin and Koopman's "Time Series Analysis by State Space > > Methods" discusses various methods for initializing the > > filters in chapter 5. They suggest to start with an > > accurate method, to achieve rapid convergence, but simlify > > the update equations after convergence has been reached > > "before the filter starts diverging, as it eventually > > will" (can't easily find the exact reference). > > Thank you. �Your note (plus a certain amount of desperation) has set me > to studying, and I can see only two possibilities for my covariance > matrix losing positive definiteness. > > One, I'm using a cheesy one-step numerical integration (of equation > 13.32 in Simon's book). �The equation states that > > dP/dt = AP + PA' + LQL'; > > I'm "cheating" this to get an update: > > P_n+1 = P_n + (AP_n + P_nA' + LQL')(dt) > > I don't see a guarantee that my AP + PA' is positive definite, so I may > be losing it here.There are no such guarantees if you integrate all terms straight out of the box. While (AP + AP') *theoretically* is symmetric, different numerical errors might creep in and break symmetry. So the Cholesky-based methods represent symmetric matrices as a product S = CC' and manipulate only one factor at C the time. There should be some benefit from that.>�I can fix this by moving the cheesy integration to > my (pretend) system, such that F = (I + A(dt)), and > > P_n+1 = F P_n F' + LQL'(dt) > > Sick sick sick, but barring numerical problems at least my eigenvalues > should stay positive, right?Yep. But those numerical problems tend to make a mess of things more often than I appreciate...> If that doesn't do the trick, then I'll either play with my units to > keep the matrix better conditioned, or I'll learn all about square root > algorithms (it makes more sense to me to smooth the units out no matter > what, then use square root algorithms if I have to, anyway).It seems you have a pretty clear idea what the problem might be. I'd ask in one of the avionics/navigation groups if these efforts don't work out. (I wouldn't mind if you cross-post any such questions here.) Rune
Reply by ●November 25, 20082008-11-25
Rune Allnor wrote:> On 25 Nov, 23:47, Tim Wescott <t...@seemywebsite.com> wrote: >> Rune Allnor wrote: >>> On 25 Nov, 21:55, Tim Wescott <t...@seemywebsite.com> wrote: >>>> First, some background: >>>> I've done some Kalman filters "for pretend" and they always worked out >>>> just fine. >>>> Now I'm doing one for a client, and of course it's blowing up in my face >>>> -- go figure. >>> ... >>>> I'm working out of Dan Simon's "Optimal State Estimation" book, and the >>>> only thing he says about the Extended Kalman Filter is that "it can >>>> sometimes be unstable and hard to tune", but he doesn't say _why_, or >>>> how to figure out if yours is, or if there are any kluges or fixes that >>>> can be applied. >>> Check out section 6.3, page 158. There is a description >>> of numerical issues you may or may not find familiar. >>> There is also the discussion of the unscented filter >>> (chapter 14) which is motivated by problems with the >>> extended filter. >>> Durbin and Koopman's "Time Series Analysis by State Space >>> Methods" discusses various methods for initializing the >>> filters in chapter 5. They suggest to start with an >>> accurate method, to achieve rapid convergence, but simlify >>> the update equations after convergence has been reached >>> "before the filter starts diverging, as it eventually >>> will" (can't easily find the exact reference). >> Thank you. Your note (plus a certain amount of desperation) has set me >> to studying, and I can see only two possibilities for my covariance >> matrix losing positive definiteness. >> >> One, I'm using a cheesy one-step numerical integration (of equation >> 13.32 in Simon's book). The equation states that >> >> dP/dt = AP + PA' + LQL'; >> >> I'm "cheating" this to get an update: >> >> P_n+1 = P_n + (AP_n + P_nA' + LQL')(dt) >> >> I don't see a guarantee that my AP + PA' is positive definite, so I may >> be losing it here. > > There are no such guarantees if you integrate all terms > straight out of the box. While (AP + AP') *theoretically* > is symmetric, different numerical errors might creep > in and break symmetry. > > So the Cholesky-based methods represent symmetric matrices > as a product S = CC' and manipulate only one factor at C > the time. There should be some benefit from that. > >> I can fix this by moving the cheesy integration to >> my (pretend) system, such that F = (I + A(dt)), and >> >> P_n+1 = F P_n F' + LQL'(dt) >> >> Sick sick sick, but barring numerical problems at least my eigenvalues >> should stay positive, right? > > Yep. But those numerical problems tend to make a mess > of things more often than I appreciate... > >> If that doesn't do the trick, then I'll either play with my units to >> keep the matrix better conditioned, or I'll learn all about square root >> algorithms (it makes more sense to me to smooth the units out no matter >> what, then use square root algorithms if I have to, anyway). > > It seems you have a pretty clear idea what the problem > might be. I'd ask in one of the avionics/navigation groups > if these efforts don't work out. (I wouldn't mind if you > cross-post any such questions here.) > > RuneAny suggestions for what a good group would be? alt.avionics.and.whackos wouldn't be a good choice, I assume. It turns out that going to the F = (I + A(dt)) form did the trick. I still have a very poorly conditioned matrix (10^11, in fact), I'm still not thrilled with the performance, and I still may have numerical problems. But it's now passing my initial test as a "fully functioning" Kalman filter, at least. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com Do you need to implement control loops in software? "Applied Control Theory for Embedded Systems" gives you just what it says. See details at http://www.wescottdesign.com/actfes/actfes.html
Reply by ●November 25, 20082008-11-25
On Nov 26, 9:55 am, Tim Wescott <t...@seemywebsite.com> wrote:> First, some background: > > I've done some Kalman filters "for pretend" and they always worked out > just fine. > > Now I'm doing one for a client, and of course it's blowing up in my face > -- go figure. > > What's happening is that the state covariance matrix is acquiring some > negative eigenvalues, followed shortly by the whole thing rapidly and > exponentially growing (bang). > > It's an extended Kalman filter, in which I'm doing some slightly > questionable (i.e. rectangular) numerical integration. I don't know if > that's a good candidate for the culprit, so I don't want to go to the > effort to fix it unless there's a good chance that it's the problem (or > one of them). > > The question: > > What sorts of things should I be looking for to see _why_ this dratted > thing is blowing up in my face? How likely is it that I'm seeing a > numerical instability vs. a real true problem with my formulation? > (I've got a pretty wide spread of state values -- from millions down to > hundredths, and variances that range from 100s to .001s). If it's a > problem with the formulation, are there any tools to tell? > > I'm working out of Dan Simon's "Optimal State Estimation" book, and the > only thing he says about the Extended Kalman Filter is that "it can > sometimes be unstable and hard to tune", but he doesn't say _why_, or > how to figure out if yours is, or if there are any kluges or fixes that > can be applied. > > And finally -- I used to frequent an applied math newsgroup that was > pretty good, but I can't figure out which one. Does anyone have any > recommendations about the right place to cross-post this question? > > Thanks in advance... > > -- > > Tim Wescott > Wescott Design Serviceshttp://www.wescottdesign.com > > Do you need to implement control loops in software? > "Applied Control Theory for Embedded Systems" gives you just what it says. > See details athttp://www.wescottdesign.com/actfes/actfes.htmlThe extended Kalman filter is not guaranteed to converge if I can remember all that time back! Hardy
