Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Prony's method
open-in-new
<h2 id="the-method">The method</h2> <p>Let f ( t ) {\displaystyle f(t)} be a signal consisting of N {\displaystyle N} evenly spaced samples. Prony's method fits a function </p> 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})} <p>to the observed f ( t ) {\displaystyle f(t)} . After some manipulation utilizing <a href="/facts/Euler%27s_formula/Wq7VXIV0">Euler's formula</a>, the following result is obtained, which allows more direct computation of terms: </p> 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}}} <p>where </p> λ i ± = σ i ± j ω 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}} are the damping components, ω i = ω 0 , i 1 − ξ i 2 {\displaystyle \omega _{i}=\omega _{0,i}{\sqrt {1-\xi _{i}^{2}}}} are the angular-frequency components, ϕ i {\displaystyle \phi _{i}} are the phase components, A i {\displaystyle A_{i}} are the amplitude components of the series, j {\displaystyle j} is the <a href="/facts/Imaginary_unit/1SCllQlU">imaginary unit</a> ( j 2 = − 1 {\displaystyle j^{2}=-1} ). <h2 id="representations">Representations</h2> <p>Prony's method is essentially a decomposition of a signal with M {\displaystyle M} complex exponentials via the following process: </p><p>Regularly sample f ^ ( t ) {\displaystyle {\hat {f}}(t)} so that the n {\displaystyle n} -th of N {\displaystyle N} samples may be written as </p> 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.} <p>If f ^ ( t ) {\displaystyle {\hat {f}}(t)} happens to consist of damped sinusoids, then there will be pairs of complex exponentials such that </p> 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}}} <p>where </p> 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}}} <p>Because the summation of complex exponentials is the homogeneous solution to a linear <a href="/facts/Difference_equation/JolXC71M">difference equation</a>, the following difference equation will exist: </p> 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.} <p>The key to Prony's Method is that the coefficients in the difference equation are related to the following polynomial: </p> 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).} <p>These facts lead to the following three steps within Prony's method: </p><p>1) Construct and solve the matrix equation for the P m {\displaystyle P_{m}} values: </p> [ 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}}.} <p>Note that if N ≠ 2 M {\displaystyle N\neq 2M} , a <a href="/facts/Generalized_inverse/4xVKDIAp">generalized matrix inverse</a> may be needed to find the values P m {\displaystyle P_{m}} . </p><p>2) After finding the P m {\displaystyle P_{m}} values, find the roots (numerically if necessary) of the polynomial </p> z M − P 1 z M − 1 − ⋯ − P M . {\displaystyle z^{M}-P_{1}z^{M-1}-\dots -P_{M}.} <p>The m {\displaystyle m} -th root of this polynomial will be equal to e λ m {\displaystyle e^{\lambda _{m}}} . </p><p>3) With the e λ m {\displaystyle e^{\lambda _{m}}} values, the 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}} values: </p> [ 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}},} <p>where M {\displaystyle M} unique values k i {\displaystyle k_{i}} are used. It is possible to use a generalized matrix inverse if more than M {\displaystyle M} samples are used. </p><p>Note that solving for λ m {\displaystyle \lambda _{m}} will yield ambiguities, since only e λ 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}} for an integer q {\displaystyle q} . This leads to the same Nyquist sampling criteria that discrete Fourier transforms are subject to </p> | Im ( λ m ) | = | ω m | < π Δ t . {\displaystyle \left|\operatorname {Im} (\lambda _{m})\right|=\left|\omega _{m}\right|<{\frac {\pi }{\Delta _{t}}}.} <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Generalized_pencil-of-function_method/mychwUb6">Generalized pencil-of-function method</a></li> <li>Computation of Prony decomposition using <a href="/facts/Digital_signal_processing/PEG7azr8">Autoregression analysis</a></li> <li>Application of Prony decomposition in <a href="/facts/Digital_signal_processing/PEG7azr8">Time-frequency analysis</a></li></ul> <h2 id="notes">Notes</h2> <ul><li>Carriere, R.; Moses, R. L. (1992). "High resolution radar target modeling using a modified Prony estimator". <i>IEEE Transactions on Antennas and Propagation</i>. 40: 13–18. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1109%2F8.123348">10.1109/8.123348</a>.</li> <li>Slyusar, V. I. (1998). <a href="http://slyusar.kiev.ua/en/IZV_1998_1.pdf">"Interpretation of the Proni method for solving long-range problems"</a> (PDF). <i>Radioelectronics and Communications Systems</i>. 41 (1): 35–39.</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>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. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> </ol>