Re: System Identification

On 1 Jul, 14:24, Andor <andor.bari...@xxxxxxxxx> wrote:

Prony's method did not propose to use least-squares solutions for the
linear problems in his three step programme to find amplitudes,
damping factors, frequencies and phases of sums of sinusoids. It is a
really neat algorithm that works perfectly under ideal (=noise free)
conditions.

There are lots of variations. The basic Prony's method
formulation says that the data set contains N samples and
the sum-of-sines contains N/2 (complex) sinusoidals.

I don't remember the details off the top of my head, but
there is also an 'extended Prony's method' and a 'modified
Prony's method.' One takes into account that there are
more samples than sinusoidal (e.g. dealing with over-
determined systems) and the other accounts for the fact
that the exact number of sinusoidals usually is not known,
and thus introduces a 'model mismatch' term.

And then we can start discussing exactly what terms are
included in the model; frequency, amplitude, phase,
damping...

Many people believe that Prony's method is in fact only
the first step of his algorithm. The first step is the AR modeling,
which essentially computes the linear prediction coefficients from the
impulse response (or any other finite excitation).

Careful. There is a trick here if you deal with the standard
sum-of-sines models. In order to make the maths work, one
needs to use the modified covariance equations, not the usual
covariance equations (details in the 1982 Proc IEEE paper by
Kay and Marple). This has a number of consequences:

- The covariance matrix is no longer Toeplitz
- The covariance matrix is no longer unconditionally stable
- The method can be used for spectrum line estimation

Prony's approach
can easily be generalized to include least-squares solutions for the
linear parts (AR coefficient estimation and phase/amplitude
estimation). The major drawback is that even the extend Prony's method
is super-ultra-sensitive to additive measurement noise

Correct.

(this comes
from the polynomial factoring part of the algorithm).

Wrong. There was a different approach suggested in 1982 by
Tufts and Kumaresan. They used the same signal model as the
'usual' variations of Prony's method, but they chose a
different strategy for solving for the *coefficients*, not
roots, of the predictor polynomials. I tested the T&K
method against one of Marple's routines in my PhD thesis.
The T&K methods stil worked at SNRs 20dB lower than
where the Marple method had given in. The only difference
is how they compute the coefficients of the predictor
polynomial from the data. Everything else is the same.

Interestingly, with Vladimir's data the situation was
the oposite: The results from T&K made no sense whereas
the Marple algorithm apparently hit quite close to home.

Sometimes, this
is compensated with over-modelling (hint for Vlad) - however, use this
with caution (what happens to the predictor polynomial?).

That's where the art lies; choosing the correct model orders.
That single step makes or brakes the analysis. With Vladimir's
data there are no problems, but in some applications the
number of data samples impose very limiting bounds on what
model orders can be chosen.

Rune
.

Relevant Pages

  • Re: Calculating two free axes
    ... You can permuate the coordinates if vn is zero to get ... On paper you solve systems of linear equations easily. ... generate a set of linearly independent vectors huh? ... algorithm to do this while I have. ...
    (comp.graphics.algorithms)
  • Re: Regression analysis -- how-to?
    ... > were it not for the fact that, the last time I asked an algorithm ... Do you want to learn about regression? ... > (linear, quadratic, logarithmic, exponential, power and inverse) and at ... > least two types of linear correlation coefficient (rank and product ...
    (comp.lang.pascal.delphi.misc)
  • Re: Paper & pencil password algorithm
    ... You should find the definition of linear on the internet and look at ... of the digits with an additional one added in on the leftmost digit. ... addition and non-linear substitution ... You asked me about the timing of the individual parts of the algorithm. ...
    (sci.crypt)
  • Re: find the largest 1000 values
    ... Worst case, the algorithm could be Oif you were startlingly unlucky and constructed a sequence such that the partition always managed to find the minimum element at the middle of the sequence, where M is the number of items you're selecting. ... Because most partition algorithms choose the middle element to partition around, a collection that has previously had nth_element run on it with the same comparison operator will approach linear performance as described earlier. ... and we only apply the algorithm to the half that our nth element is in, ...
    (microsoft.public.vc.language)
  • Re: Iterative subspace decomposition
    ... Ryan Mitchley wrote: ... I have successfully implemented the PASTd algorithm (based on ... complex-valued) sinusoidals, the algorithm breaks down. ... the autocorrelation matrix directly, and add noise on top of that. ...
    (sci.math.num-analysis)
Loading