Symbolic Methods in Transfer Fct - Get Diff Eqn from Data

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

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).