System Identification Algorithm

I have two sensors (an accelerometer and a speedometer), and I want to 
know how their outputs relate (mostly how they are filtered and delayed 
with respect to one another).  I have some nice rich data sets that 
record the outputs of these sensors simultaneously.

If I knew the input function, this would be an easy system ID problem.  
But I don't.

I've never been the World's Best System ID guy -- what algorithms should 
I be looking at?  Books to read?  Web search terms?

(I tried 'armax' on Scilab; it blows up, probably because of the length 
of the data that I'm giving it, although possibly because I want to admit 
to the possibility of several tens of samples of delay.  I also just 
tried a best-fit of a delayed cascade of one against the other -- this 
gave nonsensical answers, until eventually I looked over a long enough 
interval that _Scilab_ blew up).

TIA...

-- 
http://www.wescottdesign.com

On 18 Feb, 00:24, Tim Wescott <t...@seemywebsite.com> wrote:
> I have two sensors (an accelerometer and a speedometer), and I want to
> know how their outputs relate (mostly how they are filtered and delayed
> with respect to one another). &#4294967295;I have some nice rich data sets that
> record the outputs of these sensors simultaneously.
>
> If I knew the input function, this would be an easy system ID problem. &#4294967295;
> But I don't.
>
> I've never been the World's Best System ID guy -- what algorithms should
> I be looking at? &#4294967295;Books to read? &#4294967295;Web search terms?
>
> (I tried 'armax' on Scilab; it blows up, probably because of the length
> of the data that I'm giving it, although possibly because I want to admit
> to the possibility of several tens of samples of delay. &#4294967295;I also just
> tried a best-fit of a delayed cascade of one against the other -- this
> gave nonsensical answers, until eventually I looked over a long enough
> interval that _Scilab_ blew up).

If you don't already have it, "Random Data" by Bendat and Piersol.
They twist and turn the relations between data every which way
they can; if there is a way to solve your problem there would be at
least traces and hints in that book.

Rune

On Feb 17, 3:58&#4294967295;pm, Rune Allnor <all...@tele.ntnu.no> wrote:
> On 18 Feb, 00:24, Tim Wescott <t...@seemywebsite.com> wrote:
>
>
>
> > I have two sensors (an accelerometer and a speedometer), and I want to
> > know how their outputs relate (mostly how they are filtered and delayed
> > with respect to one another). &#4294967295;I have some nice rich data sets that
> > record the outputs of these sensors simultaneously.
>
> > If I knew the input function, this would be an easy system ID problem. &#4294967295;
> > But I don't.
>
> > I've never been the World's Best System ID guy -- what algorithms should
> > I be looking at? &#4294967295;Books to read? &#4294967295;Web search terms?
>
> > (I tried 'armax' on Scilab; it blows up, probably because of the length
> > of the data that I'm giving it, although possibly because I want to admit
> > to the possibility of several tens of samples of delay. &#4294967295;I also just
> > tried a best-fit of a delayed cascade of one against the other -- this
> > gave nonsensical answers, until eventually I looked over a long enough
> > interval that _Scilab_ blew up).
>
> If you don't already have it, "Random Data" by Bendat and Piersol.
> They twist and turn the relations between data every which way
> they can; if there is a way to solve your problem there would be at
> least traces and hints in that book.
>
> Rune
You should have played along when we were having system id contest on
sci.engr.control.

Peter Nachtwey

"Tim Wescott" <tim@seemywebsite.com> wrote in message
news:eeqdnZTAePjd2gbUnZ2dnUVZ_sudnZ2d@web-ster.com...
> I have two sensors (an accelerometer and a speedometer), and I want to
> know how their outputs relate (mostly how they are filtered and delayed
> with respect to one another).  I have some nice rich data sets that
> record the outputs of these sensors simultaneously.
> If I knew the input function, this would be an easy system ID problem.
> But I don't.
> I've never been the World's Best System ID guy -- what algorithms should
> I be looking at?  Books to read?  Web search terms?

Quick and dirty way:  make a long FIR filter, run your data trough it and
train the filter by the basic gradient algorithm (LMS). After some magic
with the update gains, it should converge to a solution. You may have to try
different starting points to avoid getting stuck in the local minima.


> (I tried 'armax' on Scilab; it blows up, probably because of the length
> of the data that I'm giving it, although possibly because I want to admit
> to the possibility of several tens of samples of delay.  I also just
> tried a best-fit of a delayed cascade of one against the other -- this
> gave nonsensical answers, until eventually I looked over a long enough
> interval that _Scilab_ blew up).

Fie. Real men don't need matlabs and scilabs.

Vladimir Vassilevsky
DSP and Mixed Signal Consultant
www.abvolt.com

On Tue, 17 Feb 2009 20:24:07 -0600, Vladimir Vassilevsky wrote:

> "Tim Wescott" <tim@seemywebsite.com> wrote in message
> news:eeqdnZTAePjd2gbUnZ2dnUVZ_sudnZ2d@web-ster.com...
>> I have two sensors (an accelerometer and a speedometer), and I want to
>> know how their outputs relate (mostly how they are filtered and delayed
>> with respect to one another).  I have some nice rich data sets that
>> record the outputs of these sensors simultaneously. If I knew the input
>> function, this would be an easy system ID problem. But I don't.
>> I've never been the World's Best System ID guy -- what algorithms
>> should I be looking at?  Books to read?  Web search terms?
> 
> Quick and dirty way:  make a long FIR filter, run your data trough it
> and train the filter by the basic gradient algorithm (LMS). After some
> magic with the update gains, it should converge to a solution. You may
> have to try different starting points to avoid getting stuck in the
> local minima.
> 
> 
>> (I tried 'armax' on Scilab; it blows up, probably because of the length
>> of the data that I'm giving it, although possibly because I want to
>> admit to the possibility of several tens of samples of delay.  I also
>> just tried a best-fit of a delayed cascade of one against the other --
>> this gave nonsensical answers, until eventually I looked over a long
>> enough interval that _Scilab_ blew up).
> 
> Fie. Real men don't need matlabs and scilabs.
> 
Scilab makes it easy to key up that long FIR in a few keystrokes.  I 
never like the results I get from Scilab's armax -- probably because I 
don't know what the heck is going on under the hood.

-- 
http://www.wescottdesign.com

Tim Wescott wrote:
> I have two sensors (an accelerometer and a speedometer), and I want to
> know how their outputs relate (mostly how they are filtered and
> delayed with respect to one another).  I have some nice rich data
> sets that record the outputs of these sensors simultaneously.
>
> If I knew the input function, this would be an easy system ID problem.
> But I don't.
>

Tim,

I'm not a System ID expert either.  But, it seems to me that you might start 
by defining the problem a little better than in this post:

- it implies but doesn't state that the "output" that these sensors are 
attached to aren't the same "output".

- maybe it implies that each of the sensors have their own frequency 
response .. or not.

So, I'll stick my neck out and assert:

- the sensors have infinite bandwidth for all practical purposes here.

- the sensors are connected to the *same* output.  A model of this would be 
the wheel of a car (for the speedometer / tachometer) and the car body (for 
the accelerometer).  The accelerometer senses acceleration along the path of 
the car as does the speedometer.

If all of these simplifying assumptions are reasonable, then:

- integrate the accelerometer output to get derived speed.
- correlate the (zero mean) derived speed with the (zero mean) measured 
speed to estimate the delay between the two measurements .. if any.  I guess 
a speedometer would likely have a time constant, no?
- perhaps iterate to calibrate the initial derived speed using the 
speedometer data??

I don't understand Vladimir's approach.  Where does the input data come 
from?  If it's the data on hand then what is the filter output criterion? 
Well, I guess you might put the acceleromter data in the filter and optimize 
for zero difference with the speedometer at the output.  That would make the 
filter an integrator with the "right" frequency response and delay.  But, 
the filter would be computing the differential between the two outputs and 
not back to some presumed common input wouldn't it?

For simple system ID you need the input and the output, as you know.
Here it appears you may have 3 unknowns: the fundamental forcing function, 
the speedometer "filter" and the accelerometer "filter" and you have 2 
knowns: the two sensor outputs.  Not enough information if this is the case 
methinks.  Thjat's why I assumed there was no filter and only an important 
sensor response in one case.  This leaves: the fundamental input with an 
accelerometer on it and the speedometer output.  Then, if the speedometer is 
the system to be identified you drive it with the integrated accelerometer 
data.  One input, one output and one system to identify....

Otherwise you would have to:
Deconvolve the accelerometer data back to the fundamental forcing function. 
But what do you use to deconvolve and back to what input?
Deconvolve the speedometer data back to the fundamental forcing function. 
But what do you use to deconvolve and back to what input?  Adjust all 3 
until the fundamental forcing functions match - assuming a unique solution 
to this.
Once more ... too many variables.

I suppose you might assume a forcing function based on a reasonable guess - 
like the accelerometer isn't really filtered.
Then use system ID to determine the speedometer function.
But, I repeat myself......

Fred

On Tue, 17 Feb 2009 23:35:54 -0800, Fred Marshall wrote:

> Tim Wescott wrote:
>> I have two sensors (an accelerometer and a speedometer), and I want to
>> know how their outputs relate (mostly how they are filtered and delayed
>> with respect to one another).  I have some nice rich data sets that
>> record the outputs of these sensors simultaneously.
>>
>> If I knew the input function, this would be an easy system ID problem.
>> But I don't.
>>
>>
> Tim,
> 
> I'm not a System ID expert either.  But, it seems to me that you might
> start by defining the problem a little better than in this post:
> 
> - it implies but doesn't state that the "output" that these sensors are
> attached to aren't the same "output".
> 
> - maybe it implies that each of the sensors have their own frequency
> response .. or not.
> 
> So, I'll stick my neck out and assert:
> 
> - the sensors have infinite bandwidth for all practical purposes here.
> 
> - the sensors are connected to the *same* output.  A model of this would
> be the wheel of a car (for the speedometer / tachometer) and the car
> body (for the accelerometer).  The accelerometer senses acceleration
> along the path of the car as does the speedometer.
> 
> If all of these simplifying assumptions are reasonable, then:
> 
> - integrate the accelerometer output to get derived speed. - correlate
> the (zero mean) derived speed with the (zero mean) measured speed to
> estimate the delay between the two measurements .. if any.  I guess a
> speedometer would likely have a time constant, no? - perhaps iterate to
> calibrate the initial derived speed using the speedometer data??
> 
> I don't understand Vladimir's approach.  Where does the input data come
> from?  If it's the data on hand then what is the filter output
> criterion? Well, I guess you might put the acceleromter data in the
> filter and optimize for zero difference with the speedometer at the
> output.  That would make the filter an integrator with the "right"
> frequency response and delay.  But, the filter would be computing the
> differential between the two outputs and not back to some presumed
> common input wouldn't it?
> 
> For simple system ID you need the input and the output, as you know.
> Here it appears you may have 3 unknowns: the fundamental forcing
> function, the speedometer "filter" and the accelerometer "filter" and
> you have 2 knowns: the two sensor outputs.  Not enough information if
> this is the case methinks.  Thjat's why I assumed there was no filter
> and only an important sensor response in one case.  This leaves: the
> fundamental input with an accelerometer on it and the speedometer
> output.  Then, if the speedometer is the system to be identified you
> drive it with the integrated accelerometer data.  One input, one output
> and one system to identify....
> 
> Otherwise you would have to:
> Deconvolve the accelerometer data back to the fundamental forcing
> function. But what do you use to deconvolve and back to what input?
> Deconvolve the speedometer data back to the fundamental forcing
> function. But what do you use to deconvolve and back to what input? 
> Adjust all 3 until the fundamental forcing functions match - assuming a
> unique solution to this.
> Once more ... too many variables.
> 
> I suppose you might assume a forcing function based on a reasonable
> guess - like the accelerometer isn't really filtered. Then use system ID
> to determine the speedometer function. But, I repeat myself......
> 
> Fred

To elaborate:

The two sensors are sensing the same motion, so the accelerometer data is 
nominally the same as the velocity data.

The forcing function is unknown.

Each sensor output is of the form Y(z) = H(z) X(z) + N, i.e. it's a 
filtered version of the body motion plus noise.

The best I think I can ever hope for is an estimate of H_accel / H_vel -- 
as you stated, anything more would require knowledge of the forcing 
function, which I don't (currently) have.

But come to think of it, I may have (or be able to ask for) data that 
includes yet another sensor output that, when treated right, would indeed 
have good data that I could use to deduce a fairly accurate forcing 
function.  Hmm.  Hmm again.  Hmm thrice...

-- 
http://www.wescottdesign.com

Tim Wescott wrote:
> I have two sensors (an accelerometer and a speedometer), and I want to
> know how their outputs relate (mostly how they are filtered and delayed
> with respect to one another). �I have some nice rich data sets that
> record the outputs of these sensors simultaneously.
>
> If I knew the input function, this would be an easy system ID problem. �
> But I don't.

Even if you don't know the input to either sensor, it still is "an
easy system ID problem". You have two signals (output accelerometer
and output speedometer) and you want to know how the two outputs
relate to each other. So you have

output accelerometer ---> linear filter H1 ---> outupt speedometer

no? You might also try

output speedometer ---> linear filter H2 ---> outupt accelerometer,

both approaches have pros and cons (the one amplifies high frequency
noise, the other might suffer from lack of input signal to estimate
the system - consider the constant speed case). Obviously H1 = H2^-1,
so you might try both approaches under this condition to get a better
estimate. To check if your hypothesis really holds (ie. that the two
output signals are connected via a linear filter) you can look at the
coherence spectrum. This also shows you in which frequency bands noise
and lack of energy in the input will make your "easy" system ID
problem hard or impossible.

There are good reasons for looking at the coherence. Your model is

unknown input -----> speedometer sensor filter S ---> speedometer
output

+

unknown input -----> accelerometer sensor filter A ---> accelerometer
output

So the unknown filters that relate speedometer to accelerometer are

H1 = A^-1 S

and

H2 = S^-1 A

It might well be possible that either S or A or both are not or only
critically invertible (at least in some bands). Then you have a
problem estimating H1 or H2 in that particular band. Whether your
problem really is easy or not depends on A, S, the unkown input signal
and finally the amount of measurement noise (which is hopefully
white).


Regards,
Andor

Fred Marshall wrote:

> Tim Wescott wrote:
> 
>>I have two sensors (an accelerometer and a speedometer), and I want to
>>know how their outputs relate
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^


> I don't understand Vladimir's approach.  Where does the input data come 
> from?  If it's the data on hand then what is the filter output criterion?
> Well, I guess you might put the acceleromter data in the filter and optimize 
> for zero difference with the speedometer at the output.  That would make the 
> filter an integrator with the "right" frequency response and delay.  But, 
> the filter would be computing the differential between the two outputs and 
> not back to some presumed common input wouldn't it?

Of course. A filter can make the accelerometer data from the speedometer 
data (or vice versa), but there is not enough information to recover the 
original input.

Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com

Andor wrote:
> Tim Wescott wrote:
>> I have two sensors (an accelerometer and a speedometer), and I want
>> to know how their outputs relate (mostly how they are filtered and
>> delayed with respect to one another). I have some nice rich data
>> sets that record the outputs of these sensors simultaneously.
>>
>> If I knew the input function, this would be an easy system ID
>> problem. But I don't.
>
> Even if you don't know the input to either sensor, it still is "an
> easy system ID problem". You have two signals (output accelerometer
> and output speedometer) and you want to know how the two outputs
> relate to each other. So you have
>
> output accelerometer ---> linear filter H1 ---> outupt speedometer
>
> no? You might also try
>
> output speedometer ---> linear filter H2 ---> outupt accelerometer,
>
> both approaches have pros and cons (the one amplifies high frequency
> noise, the other might suffer from lack of input signal to estimate
> the system - consider the constant speed case). Obviously H1 = H2^-1,
> so you might try both approaches under this condition to get a better
> estimate. To check if your hypothesis really holds (ie. that the two
> output signals are connected via a linear filter) you can look at the
> coherence spectrum. This also shows you in which frequency bands noise
> and lack of energy in the input will make your "easy" system ID
> problem hard or impossible.
>
> There are good reasons for looking at the coherence. Your model is
>
> unknown input -----> speedometer sensor filter S ---> speedometer
> output
>
> +
>
> unknown input -----> accelerometer sensor filter A ---> accelerometer
> output
>
> So the unknown filters that relate speedometer to accelerometer are
>
> H1 = A^-1 S
>
> and
>
> H2 = S^-1 A
>
> It might well be possible that either S or A or both are not or only
> critically invertible (at least in some bands). Then you have a
> problem estimating H1 or H2 in that particular band. Whether your
> problem really is easy or not depends on A, S, the unkown input signal
> and finally the amount of measurement noise (which is hopefully
> white).
>
>
> Regards,
> Andor

This is good.  I think you also get some mileage out of the fact that 
velocity is the integral of acceleration - which is certainly strongly 
implied by Andor's descriptions of quality sorts of things.

What I'm thinking is that there has to be a 1/S term in the speedometer 
compared to the accelerometer.  And, maybe that's all save a scale 
factor????

Why do you think there's much filtering at all?  Could you simplify by 
assuming none for starters?

Fred