Prony's method

☆ Save On Wikipedia ↗
Prony analysis of a time-domain signal

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 damped sinusoids. This allows the estimation of frequency, amplitude, phase and damping components of a signal.

The method

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

f ^ ( t ) = ∑ i = 1 N A i e σ i t cos ⁡ ( ω i t + ϕ i ) {\displaystyle {\hat {f}}(t)=\sum _{i=1}^{N}A_{i}e^{\sigma _{i}t}\cos(\omega _{i}t+\phi _{i})} {\displaystyle {\hat {f}}(t)=\sum _{i=1}^{N}A_{i}e^{\sigma _{i}t}\cos(\omega _{i}t+\phi _{i})}

to the observed f ( t ) {\displaystyle f(t)} {\displaystyle f(t)}. After some manipulation utilizing Euler's formula, the following result is obtained, which allows more direct computation of terms:

f ^ ( t ) = ∑ i = 1 N 1 2 A i ( e j ϕ i e λ i + t + e − j ϕ i e λ i − t ) , {\displaystyle {\begin{aligned}{\hat {f}}(t)=\sum _{i=1}^{N}{\tfrac {1}{2}}A_{i}\left(e^{j\phi _{i}}e^{\lambda _{i}^{+}t}+e^{-j\phi _{i}}e^{\lambda _{i}^{-}t}\right),\end{aligned}}} {\displaystyle {\begin{aligned}{\hat {f}}(t)=\sum _{i=1}^{N}{\tfrac {1}{2}}A_{i}\left(e^{j\phi _{i}}e^{\lambda _{i}^{+}t}+e^{-j\phi _{i}}e^{\lambda _{i}^{-}t}\right),\end{aligned}}}

where

λ i ± = σ i ± j ω i {\displaystyle \lambda _{i}^{\pm }=\sigma _{i}\pm j\omega _{i}} {\displaystyle \lambda _{i}^{\pm }=\sigma _{i}\pm j\omega _{i}} are the eigenvalues of the system,
σ i = − ω 0 , i ξ i {\displaystyle \sigma _{i}=-\omega _{0,i}\xi _{i}} {\displaystyle \sigma _{i}=-\omega _{0,i}\xi _{i}} are the damping components,
ω i = ω 0 , i 1 − ξ i 2 {\displaystyle \omega _{i}=\omega _{0,i}{\sqrt {1-\xi _{i}^{2}}}} {\displaystyle \omega _{i}=\omega _{0,i}{\sqrt {1-\xi _{i}^{2}}}} are the angular-frequency components,
ϕ i {\displaystyle \phi _{i}} {\displaystyle \phi _{i}} are the phase components,
A i {\displaystyle A_{i}} {\displaystyle A_{i}} are the amplitude components of the series,
j {\displaystyle j} {\displaystyle j} is the imaginary unit ( j 2 = − 1 {\displaystyle j^{2}=-1} {\displaystyle j^{2}=-1}).

Representations

Prony's method is essentially a decomposition of a signal with M {\displaystyle M} {\displaystyle M} complex exponentials via the following process:

Regularly sample f ^ ( t ) {\displaystyle {\hat {f}}(t)} {\displaystyle {\hat {f}}(t)} so that the n {\displaystyle n} {\displaystyle n}-th of N {\displaystyle N} {\displaystyle N} samples may be written as

F n = f ^ ( Δ t n ) = ∑ m = 1 M B m e λ m Δ t n , n = 0 , … , N − 1. {\displaystyle F_{n}={\hat {f}}(\Delta _{t}n)=\sum _{m=1}^{M}\mathrm {B} _{m}e^{\lambda _{m}\Delta _{t}n},\quad n=0,\dots ,N-1.} {\displaystyle F_{n}={\hat {f}}(\Delta _{t}n)=\sum _{m=1}^{M}\mathrm {B} _{m}e^{\lambda _{m}\Delta _{t}n},\quad n=0,\dots ,N-1.}

If f ^ ( t ) {\displaystyle {\hat {f}}(t)} {\displaystyle {\hat {f}}(t)} happens to consist of damped sinusoids, then there will be pairs of complex exponentials such that

B i ( 1 ) = 1 2 A i e ϕ i j , B i ( 2 ) = 1 2 A i e − ϕ i j , λ i ( 1 ) = σ i + j ω i , λ i ( 2 ) = σ i − j ω i , {\displaystyle {\begin{aligned}\mathrm {B} _{i}^{(1)}&={\tfrac {1}{2}}A_{i}e^{\phi _{i}j},\\\mathrm {B} _{i}^{(2)}&={\tfrac {1}{2}}A_{i}e^{-\phi _{i}j},\\\lambda _{i}^{(1)}&=\sigma _{i}+j\omega _{i},\\\lambda _{i}^{(2)}&=\sigma _{i}-j\omega _{i},\end{aligned}}} {\displaystyle {\begin{aligned}\mathrm {B} _{i}^{(1)}&={\tfrac {1}{2}}A_{i}e^{\phi _{i}j},\\\mathrm {B} _{i}^{(2)}&={\tfrac {1}{2}}A_{i}e^{-\phi _{i}j},\\\lambda _{i}^{(1)}&=\sigma _{i}+j\omega _{i},\\\lambda _{i}^{(2)}&=\sigma _{i}-j\omega _{i},\end{aligned}}}

where

B i ( 1 ) e λ i ( 1 ) t + B i ( 2 ) e λ i ( 2 ) t = 1 2 A i e ϕ i j e ( σ i + j ω i ) t + 1 2 A i e − ϕ i j e ( σ i − j ω i ) t = A i e σ i t cos ⁡ ( ω i t + ϕ i ) . {\displaystyle {\begin{aligned}\mathrm {B} _{i}^{(1)}e^{\lambda _{i}^{(1)}t}+\mathrm {B} _{i}^{(2)}e^{\lambda _{i}^{(2)}t}&={\tfrac {1}{2}}A_{i}e^{\phi _{i}j}e^{(\sigma _{i}+j\omega _{i})t}+{\tfrac {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{aligned}}} {\displaystyle {\begin{aligned}\mathrm {B} _{i}^{(1)}e^{\lambda _{i}^{(1)}t}+\mathrm {B} _{i}^{(2)}e^{\lambda _{i}^{(2)}t}&={\tfrac {1}{2}}A_{i}e^{\phi _{i}j}e^{(\sigma _{i}+j\omega _{i})t}+{\tfrac {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{aligned}}}

Because the summation of complex exponentials is the homogeneous solution to a linear difference equation, the following difference equation will exist:

f ^ ( Δ t n ) = ∑ m = 1 M f ^ [ Δ t ( n − m ) ] P m , n = M , … , N − 1. {\displaystyle {\hat {f}}(\Delta _{t}n)=\sum _{m=1}^{M}{\hat {f}}[\Delta _{t}(n-m)]P_{m},\quad n=M,\dots ,N-1.} {\displaystyle {\hat {f}}(\Delta _{t}n)=\sum _{m=1}^{M}{\hat {f}}[\Delta _{t}(n-m)]P_{m},\quad n=M,\dots ,N-1.}

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

z M − P 1 z M − 1 − ⋯ − P M = ∏ m = 1 M ( z − e λ m ) . {\displaystyle z^{M}-P_{1}z^{M-1}-\dots -P_{M}=\prod _{m=1}^{M}\left(z-e^{\lambda _{m}}\right).} {\displaystyle z^{M}-P_{1}z^{M-1}-\dots -P_{M}=\prod _{m=1}^{M}\left(z-e^{\lambda _{m}}\right).}

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

1) Construct and solve the matrix equation for the P m {\displaystyle P_{m}} {\displaystyle P_{m}} values:

[ F M ⋮ F N − 1 ] = [ F M − 1 … F 0 ⋮ ⋱ ⋮ F N − 2 … F N − M − 1 ] [ P 1 ⋮ P M ] . {\displaystyle {\begin{bmatrix}F_{M}\\\vdots \\F_{N-1}\end{bmatrix}}={\begin{bmatrix}F_{M-1}&\dots &F_{0}\\\vdots &\ddots &\vdots \\F_{N-2}&\dots &F_{N-M-1}\end{bmatrix}}{\begin{bmatrix}P_{1}\\\vdots \\P_{M}\end{bmatrix}}.} {\displaystyle {\begin{bmatrix}F_{M}\\\vdots \\F_{N-1}\end{bmatrix}}={\begin{bmatrix}F_{M-1}&\dots &F_{0}\\\vdots &\ddots &\vdots \\F_{N-2}&\dots &F_{N-M-1}\end{bmatrix}}{\begin{bmatrix}P_{1}\\\vdots \\P_{M}\end{bmatrix}}.}

Note that if N ≠ 2 M {\displaystyle N\neq 2M} {\displaystyle N\neq 2M}, a generalized matrix inverse may be needed to find the values P m {\displaystyle P_{m}} {\displaystyle P_{m}}.

2) After finding the P m {\displaystyle P_{m}} {\displaystyle P_{m}} values, find the roots (numerically if necessary) of the polynomial

z M − P 1 z M − 1 − ⋯ − P M . {\displaystyle z^{M}-P_{1}z^{M-1}-\dots -P_{M}.} {\displaystyle z^{M}-P_{1}z^{M-1}-\dots -P_{M}.}

The m {\displaystyle m} {\displaystyle m}-th root of this polynomial will be equal to e λ m {\displaystyle e^{\lambda _{m}}} {\displaystyle e^{\lambda _{m}}}.

3) With the e λ m {\displaystyle e^{\lambda _{m}}} {\displaystyle e^{\lambda _{m}}} values, the F n {\displaystyle F_{n}} {\displaystyle F_{n}} values are part of a system of linear equations that may be used to solve for the B m {\displaystyle \mathrm {B} _{m}} {\displaystyle \mathrm {B} _{m}} values:

[ F k 1 ⋮ F k M ] = [ ( e λ 1 ) k 1 … ( e λ M ) k 1 ⋮ ⋱ ⋮ ( e λ 1 ) k M … ( e λ M ) k M ] [ B 1 ⋮ B M ] , {\displaystyle {\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}\mathrm {B} _{1}\\\vdots \\\mathrm {B} _{M}\end{bmatrix}},} {\displaystyle {\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}\mathrm {B} _{1}\\\vdots \\\mathrm {B} _{M}\end{bmatrix}},}

where M {\displaystyle M} {\displaystyle M} unique values k i {\displaystyle k_{i}} {\displaystyle k_{i}} are used. It is possible to use a generalized matrix inverse if more than M {\displaystyle M} {\displaystyle M} samples are used.

Note that solving for λ m {\displaystyle \lambda _{m}} {\displaystyle \lambda _{m}} will yield ambiguities, since only e λ m {\displaystyle e^{\lambda _{m}}} {\displaystyle e^{\lambda _{m}}} was solved for, and e λ m = e λ m + q 2 π j {\displaystyle e^{\lambda _{m}}=e^{\lambda _{m}\,+\,q2\pi j}} {\displaystyle e^{\lambda _{m}}=e^{\lambda _{m}\,+\,q2\pi j}} for an integer q {\displaystyle q} {\displaystyle q}. This leads to the same Nyquist sampling criterion to which discrete Fourier transforms are subject

| Im ⁡ ( λ m ) | = | ω m | < π Δ t . {\displaystyle \left|\operatorname {Im} (\lambda _{m})\right|=\left|\omega _{m}\right|<{\frac {\pi }{\Delta _{t}}}.} {\displaystyle \left|\operatorname {Im} (\lambda _{m})\right|=\left|\omega _{m}\right|<{\frac {\pi }{\Delta _{t}}}.}

See also

Notes

  1. Hauer, J. F.; Demeure, C. J.; Scharf, L. L. (1990). "Initial results in Prony analysis of power system response signals". IEEE Transactions on Power Systems. 5 (1): 80–89. Bibcode:1990ITPSy...5...80H. doi:10.1109/59.49090. hdl:10217/753.

References