Prony's method

From Wikipedia, the free encyclopedia

Prony analysis (Prony's method) was developed by Gaspard Riche de Prony in 1795. However, practical use of the method awaited the digital computer [1]. 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.

1 The method
2 Example
3 References
4 How to

[edit] The method

Let $f (t)$ be a signal consisting of $N$ evenly spaced samples. Prony's method fits a function

$\hat{f}(t) = \sum_{i=1}^{N} A_i e^{\sigma_i t} cos(2\pi f_i t + \phi_i)$

to the observed $f (t)$ . After some manipulation utilizing Euler's formula, the following result is obtained. This allows for more direct computation of terms.

$\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^{\phi_i j}e^{\lambda_i t}$

to the observed $f (t)$ . where:

$\lambda_i = (-\sigma_i \pm j \omega_i )t$ are the eigenvalues of the system,

σ i

are the damping components,

φ i

are the phase components,

f i

are the frequency components,

A i

are the amplitude components of the series, and $j=\sqrt{-1}$ .

[edit] Example

[edit] References

[1] 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.

[edit] How to

Prony's Method is essentially a decomposition of a signal with $M$ complex exponentials via the following process:

Regularly sample $\hat{f}(t)$ so that the $n t h$ of $N$ samples may be written as follows:

$F_n=\hat{f}(\Delta_t n) = \sum_{m=1}^{M} \Beta_m e^{\Lambda_m t}$

If $\hat{f}(t)$ happens to be consist of dampened sinusiods then there will be pairs of complex exponentials such that

$\Beta_a = \frac{1}{2} A_i e^{\phi_i j}$

$\Beta_b = \frac{1}{2} A_i e^{-\phi_i j}$

Λ a = σ i + j ω i

Λ b = σ i - j ω i

where

$\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)$

??Because the sumation of complex exponentials is the homogeneous solution to a linear differential equatinon the following difference equation will exist??:

$\hat{f}(\Delta_t n) = -\sum_{m=1}^{M} \hat{f}(\Delta_t (n-m)) P_m$

The key to Prony's Method is that the coeficients in the difference equation are related to the following polynomial

$\sum_{m=1}^{M+1} P_m x^{m-1} = \prod_{m=1}^{M} ( x - e^{\Lambda_m} )$

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

1) Construct and solve the matrix equation for the $P m$ values:

$\begin{bmatrix} F_N \\ : \\ F_{2N-1} \end{bmatrix} = -\begin{bmatrix} F_{N-1} & .. & F_{0} \\ : & . & : \\ F_{2N-2} & .. & F_{N-1} \end{bmatrix} \begin{bmatrix} P_1 \\ : \\ P_M\end{bmatrix}$

Note that if $N$ ≠ $M$ a generalized matrix inverse may be needed to find the values $P m$

2) After finding the $P m$ values find the roots (numericaly if necessary) of the polynomial

$\sum_{m=1}^{M+1} P_m x^{m-1}$

The $m t h$ root of this polynomial will be equal to $e^{\Lambda_m}$ .

3) With the $e^{\Lambda_m}$ values the $F n$ values are part of a system of linear equations which may be used to solve for the $Β m$ values:

$\begin{bmatrix} F_{k_1} \\ : \\ F_{k_M} \end{bmatrix} = \begin{bmatrix} (e^{\Lambda_1})^{k_1} & .. & (e^{\Lambda_M})^{k_1} \\ : & . & : \\ (e^{\Lambda_1})^{k_M} & .. & (e^{\Lambda_M})^{k_M} \end{bmatrix} \begin{bmatrix} \Beta_1 \\ : \\ \Beta_M\end{bmatrix}$

where $M$ unique values $k i$ are used. It is possible to use a generalized matrix inverse if more than $M$ samples are used.

Note that solving for $Λ m$ will yield ambiguities since only $e^{\Lambda_m}$ was solved for, and $e^{\Lambda_m}=e^{\Lambda_m+q 2 \pi j}$ for and integer $q$ . This leads to the same nyquist sampling criteria that discrete fourier transforms are subject to:

$|Im(\Lambda_m)|=|\omega_m|<\frac{1}{2 \Delta_t}$

reference: 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.

Retrieved from "http://en.wikipedia.org../../../p/r/o/Prony%27s_method.html"

Category: Signal processing