Re: [math-fun] Fourier transforms
Henry writes: << Fourier analysis can easily separate out the various sinusoidal frequencies in a waveform. Is there an analogous analysis that can separate out various real exponentials in a real waveform? I.e., if a signal is the sum of various real exponentials (i.e., no sinusoidal components), is there a simple analysis that will pull out the coefficients & exponents? Is there a "fast" version analogous to the FFT for this procedure? I recall studying Laplace transforms, but can't recall whether they solve this particular problem.
It would indeed seem that the Laplace transform is what you're looking for; see < http://en.wikipedia.org/wiki/Laplace_transform >. Since the (bilateral) Laplace transform is equivalent to the Fourier transform under a change of variables (real <-> imaginary), there by rights should be a corresponding fast [or finite] Laplace transform. (Cf. V. Rokhlin, "A fast algorithm for the discrete Laplace transform", J. Complexity, v. 4, 1988.) In simple discrete cases -- say where you already know f(x) == sum_{n=-oo to oo} c_n exp(nx) then integrating f(x)*exp(-n_0 x) over the imaginary interval [0, 2pi*i] will equal 2pi*i c_n (modulo technical details). --Dan
[Henry Baker:]
Is there an analogous analysis that can separate out various real exponentials in a real waveform?
I.e., if a signal is the sum of various real exponentials (i.e., no sinusoidal components), is there a simple analysis that will pull out the coefficients & exponents? Is there a "fast" version analogous to the FFT for this procedure? ...
[Dan Asimov:]
It would indeed seem that the Laplace transform is what you're looking for; see < http://en.wikipedia.org/wiki/Laplace_transform >. Since the (bilateral) Laplace transform is equivalent to the Fourier transform under a change of variables (real <-> imaginary), there by rights should be a corresponding fast [or finite] Laplace transform. (Cf. V. Rokhlin, "A fast algorithm for the discrete Laplace transform", J. Complexity, v. 4, 1988.)
In simple discrete cases -- say where you already know
f(x) == sum_{n=-oo to oo} c_n exp(nx)
then integrating f(x)*exp(-n_0 x) over the imaginary interval [0, 2pi*i] will equal 2pi*i c_n (modulo technical details).
That's not going to help much if what Henry has is an empirically obtained signal for real values of x only... Parameter estimation for linear combinations of decaying exponentials is notoriously ill-conditioned, so I'd be a bit pessimistic about the chances of any algorithm doing what Henry wants at all well in the presence of noise. -- g
I wasn't aware of the ill-conditioned nature of this problem. References? Perhaps I should try a semilog transformation? At 08:48 AM 4/28/2007, Gareth McCaughan wrote:
[Henry Baker:]
Is there an analogous analysis that can separate out various real exponentials in a real waveform?
I.e., if a signal is the sum of various real exponentials (i.e., no sinusoidal components), is there a simple analysis that will pull out the coefficients & exponents? Is there a "fast" version analogous to the FFT for this procedure? ...
Parameter estimation for linear combinations of decaying exponentials is notoriously ill-conditioned, so I'd be a bit pessimistic about the chances of any algorithm doing what Henry wants at all well in the presence of noise.
-- g
On Saturday 28 April 2007 20:17, Henry Baker wrote:
I wasn't aware of the ill-conditioned nature of this problem. References?
I'm far from an expert in the field, so here's a not-terribly-highbrow reference, from Forman Acton's charming book "Numerical methods that (usually) work". This is from a brief rant in the middle entitled "What not to compute", under the heading "Exponential fitting". | One of the perennial problems that plagues, among others, | the analyzers of isotope decay is the fitting of data | by a series of exponential functions. How much of A and | how much of B, decaying at known rates a and b, are in | the sample whose activity was sampled several times | in the historic past? This question is quite tractable. [...] | Unfortunately there is a companion problem that looks | only slightly more complicated -- until you try it! | We again have {t_i,y_i} readings from a radioactive sample, | but the decaying materials are not known, hence the decay rates | a and b must also be fitted. [...] For it is well known | that an exponential equation of this type in which all four | parameters are to be fitted is extremely ill conditioned. | That is, there are many combinations of {a,b,A,B} that will | fit most exact data quite well indeed (will you believe four | significant figures?) and when experimental noise is thrown | into the pot, the entire operation becomes hopeless. -- g
Date: Sat, 28 Apr 2007 12:17:57 -0700 From: Henry Baker <hbaker1@pipeline.com>
I wasn't aware of the ill-conditioned nature of this problem. References? Perhaps I should try a semilog transformation?
Strangely, and somewhat embarassingly, there's an appendix in my old thesis on approximately this problem. It was on the numerical stability of fitting gaussians instead of exponentials, but the root of the problem is the same: fitting log data means any error from the fit eventually get exponentiated. Exponentially growing error is the signature of this particular numerical disaster. I ended up supplying an initial guess for the parameters by other means, expanding in a power series around that guess, and fitting the first correction term of that series. Seemed to work ok. Even more embarassingly, MIT has put a lot of old theses online. If can stand to watch huffing and puffing by a near-insanely frustrated and pedantic grad student, look at: http://dspace.mit.edu/handle/1721.1/26852 http://hdl.handle.net/1721.1/26852 (dunno why there are 2) The gaussian fitting stuff is in Appendix C, pp. 255-261. -- Steve Rowley <sgr@alum.mit.edu> http://alum.mit.edu/www/sgr/ Skype: sgr000
participants (5)
-
Daniel Asimov -
Gareth McCaughan -
Henry Baker -
Jason Holt -
Steve Rowley