en>Jason Quinn: sp fix "containing"

2012-07-30T23:21:34Z

sp fix "containing"

New page

'''Prony analysis''' ('''Prony's method''') was developed by [[Gaspard Riche de Prony]] in 1795. However, practical use of the method awaited the digital computer.<ref>Hauer, J.F. et al. (1990). "Initial Results in Prony Analysis of Power System Response Signals". ''IEEE Transactions on Power Systems'', 5, 1, 80-89.</ref> Similar to the [[Fourier transform]], Prony's method extracts valuable information from a uniformly sampled signal and builds a series of damped complex exponentials or sinusoids. This allows for the estimation of frequency, amplitude, phase and damping components of a signal.

== The method ==

Let <math>f(t)</math> be a signal consisting of <math>N</math> evenly spaced samples. Prony's method fits a function
:<math>\hat{f}(t) = \sum_{i=1}^{N} A_i e^{\sigma_i t} \cos(2\pi f_i t + \phi_i)</math>

to the observed <math>f(t)</math>. After some manipulation utilizing [[Euler's formula]], the following result is obtained. This allows more direct computation of terms.
:<math>\begin{align}
\hat{f}(t) &= \sum_{i=1}^{N} A_i e^{\sigma_i t} \cos(2\pi f_i t + \phi_i) \\
&= \sum_{i=1}^{N} \frac{1}{2} A_i e^{\pm j\phi_i}e^{\lambda_i t}
\end{align}</math>

where:
*<math>\lambda_i = \sigma_i \pm j \omega_i</math> are the eigenvalues of the system,
*<math>\sigma_i</math> are the damping components,
*<math>\phi_i</math> are the phase components,
*<math>f_i</math> are the frequency components,
*<math>A_i</math> are the amplitude components of the series, and
*<math>j</math> is the [[imaginary unit]] (<math>j^2 = -1</math>).

== Representations ==

Prony's method is essentially a decomposition of a signal with <math>M</math> complex exponentials via the following process:

Regularly sample <math>\hat{f}(t)</math> so that the <math>n</math>-th of <math>N</math> samples may be written as
:<math>F_n = \hat{f}(\Delta_t n) = \sum_{m=1}^{M} \Beta_m e^{\lambda_m \Delta_t n}.</math>

If <math>\hat{f}(t)</math> happens to consist of damped sinusoids, then there will be pairs of complex exponentials such that
:<math>\begin{align}
\Beta_a &= \frac{1}{2} A_i e^{ \phi_i j}, \\
\Beta_b &= \frac{1}{2} A_i e^{-\phi_i j}, \\
\lambda_a &= \sigma_i + j \omega_i, \\
\lambda_b &= \sigma_i - j \omega_i,
\end{align}</math>
where
:<math>\begin{align}
\Beta_a e^{\lambda_a t} + \Beta_b e^{\lambda_b t}
&= \frac{1}{2} A_i e^{\phi_i j} e^{(\sigma_i + j \omega_i) t} +
\frac{1}{2}A_i e^{-\phi_i j} e^{(\sigma_i - j \omega_i) t} \\
&= A_i e^{\sigma_i t} \cos(\omega_i t + \phi_i).
\end{align}</math>

Because the summation of complex exponentials is the homogeneous solution to a linear [[difference equation]], the following difference equation will exist:
:<math>\hat{f}(\Delta_t n) = -\sum_{m=1}^{M} \hat{f}[\Delta_t (n - m)] P_m.</math>

The key to Prony's Method is that the coefficients in the difference equation are related to the following polynomial:
:<math> \sum_{m = 1}^{M + 1} P_m x^{m - 1} = \prod_{m=1}^{M} \left(x - e^{\lambda_m}\right).</math>

These facts lead to the following three steps to Prony's Method:

1) Construct and solve the matrix equation for the <math>P_m</math> values:
:<math>
\begin{bmatrix}
F_N \\
\vdots \\
F_{2N-1}
\end{bmatrix}
=
-\begin{bmatrix}
F_{N-1} & \dots & F_{0} \\
\vdots & \ddots & \vdots \\
F_{2N-2} & \dots & F_{N-1}
\end{bmatrix}
\begin{bmatrix}
P_1 \\
\vdots \\
P_M
\end{bmatrix}.
</math>

Note that if <math>N \ne M</math>, a generalized matrix inverse may be needed to find the values <math>P_m</math>.

2) After finding the <math>P_m</math> values find the roots (numerically if necessary) of the polynomial
:<math> x^M + \sum_{m = 1}^{M} P_m x^{m - 1}.</math>

The <math>m</math>-th root of this polynomial will be equal to <math>e^{\lambda_m}</math>.

3) With the <math>e^{\lambda_m}</math> values the <math>F_n</math> values are part of a system of linear equations that may be used to solve for the <math>\Beta_m</math> values:
:<math>
\begin{bmatrix}
F_{k_1} \\
\vdots \\
F_{k_M}
\end{bmatrix}
=
\begin{bmatrix}
(e^{\lambda_1})^{k_1} & \dots & (e^{\lambda_M})^{k_1} \\
\vdots & \ddots & \vdots \\
(e^{\lambda_1})^{k_M} & \dots & (e^{\lambda_M})^{k_M}
\end{bmatrix}
\begin{bmatrix}
\Beta_1 \\
\vdots \\
\Beta_M
\end{bmatrix},
</math>
where <math>M</math> unique values <math>k_i</math> are used. It is possible to use a generalized matrix inverse if more than <math>M</math> samples are used.

Note that solving for <math>\lambda_m</math> will yield ambiguities, since only <math>e^{\lambda_m}</math> was solved for, and <math>e^{\lambda_m} = e^{\lambda_m \,+\, q 2 \pi j}</math> for an integer <math>q</math>. This leads to the same Nyquist sampling criteria that discrete Fourier transforms are subject to:
:<math> \left|Im(\lambda_m)\right| = \left|\omega_m\right| < \frac{1}{2 \Delta_t}.</math>

== Example ==

[[Image:Prony2.jpg]]

== Notes ==
{{reflist}}

== References ==
{{refbegin}}
* Rob Carriere and Randolph L. Moses, "High Resolution Radar Target Modeling Using a Modified Prony Estimator", IEEE Trans. Antennas Propogat., vol.40, pp. 13–18, January 1992.
{{refend}}

[[Category:Signal processing]]

Excluded point topology - Revision history

en>Jason Quinn: sp fix "containing"