Symbolic Methods in Transfer Fct - Get Diff Eqn from Data

	Suppose I have data in and data out, so I do Fourier
transforms and divide them to get the transfer function numerically
and then invert back into time domain. But what I really want is given
data, get the Difference Equation, as I would if I solved the system
using Z-Transforms. I know this would be leading-edge, but given the
advanced state of symbolic computation, I don't see why this doesn't
exist yet.




				- = -
    Vasos-Peter John Panagiotopoulos II, Columbia'81+, Bio$trategist
       http://ourworld.compuserve.com/homepages/vjp2/vasos.htm
  ---{Nothing herein constitutes advice.  Everything fully disclaimed.}---

vjp2@BioStrategist.com wrote in message news:<c6hn15$aja$2@reader2.panix.com>...
> Suppose I have data in and data out, so I do Fourier
> transforms and divide them to get the transfer function numerically
> and then invert back into time domain. But what I really want is given
> data, get the Difference Equation, as I would if I solved the system
> using Z-Transforms. I know this would be leading-edge, but given the
> advanced state of symbolic computation, I don't see why this doesn't
> exist yet.
> 
> 				- = -
>     Vasos-Peter John Panagiotopoulos II, Columbia'81+, Bio$trategist
>        http://ourworld.compuserve.com/homepages/vjp2/vasos.htm
>   ---{Nothing herein constitutes advice.  Everything fully disclaimed.}---


If the recurrence sought is linear then it might be found by null
space computations. Below I show mathematica code for this. We
iterate, incrementing the length of the putative recurrence at each
step.

findLinearRecurrence[vals_List, func_, n_, tol_:0] := Module[
  {v2=Reverse[vals], nulls={}, res, j=0},
  While[nulls=={},
    j++;
	nulls = NullSpace[Partition[v2,j,1], Tolerance->tol];
	If [Length[nulls]>0,
      res = First[nulls];
      res = -Rest[res] / First[res];
      Return[func[n] == res . Map[func[n-#]&, Range[Length[res]]]]
      ];
    ];
  ]

We'll test with some Fibonacci values.

In[13]:= findLinearRecurrence[Fibonacci[Range[7]], f, n]
Out[13]= f[n] == f[-2 + n] + f[-1 + n]

For another test we define a recurrence and recover it from
several contiguous values.

func[n_] /; n>4 := func[n] =
  func[n-1]-3*func[n-2]-5*func[n-3]+7*func[n-4]
{func[1],func[2],func[3],func[4]} = {-2,3,4,1};

vals = Table[func[j], {j,8,15}];

In[17]:= findLinearRecurrence[vals, g, k]
Out[17]= g[k] == 7 g[-4 + k] - 5 g[-3 + k] - 3 g[-2 + k] + g[-1 + k]

The tests above were not too difficult insofar as they involve exact
recurrences recovered from exact data. Presumably for numeric data you
would want to adjust tolerance to be fairly low.


Daniel Lichtblau
Wolfram Research

vjp2@BioStrategist.com wrote:

> 	Suppose I have data in and data out, so I do Fourier
> transforms and divide them to get the transfer function numerically
> and then invert back into time domain. But what I really want is given
> data, get the Difference Equation, as I would if I solved the system
> using Z-Transforms. I know this would be leading-edge, but given the
> advanced state of symbolic computation, I don't see why this doesn't
> exist yet.
> 
> 
> 
> 
> 				- = -
>     Vasos-Peter John Panagiotopoulos II, Columbia'81+, Bio$trategist
>        http://ourworld.compuserve.com/homepages/vjp2/vasos.htm
>   ---{Nothing herein constitutes advice.  Everything fully disclaimed.}---

Actually it's not that leading-edge.  Assuming that the data set is rich 
enough, the system linear, and you guess the order for your transfer 
function then you can get these numbers more or less directly using 
least-squares fit techniques.

The general field that you're interested in is "system identification". 
  The place where I've seen this technique detailed is in the adaptive 
control literature, specifically "Adaptive Control" by Karl Johan �str�m 
& Bj�rn Wittenmark, Addison-Wesley.  I've got the 2nd edition, (C) 1995, 
ISBN 0-201-55866-1.  They do a good job of clearly explaining the 
algorithm without leaving out the theoretical fundamentals.

You'll also find this sort of thing in adaptive channel equalizer 
literature, but those texts assume that the input data is constrained to 
the protocol being used and that it is unavailable to you until you've 
decoded _some_ data -- it'll be of interest to you, but I think the 
adaptive control book would be better (or just go to the well and look 
up system identification).

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com