Hi, highenergystar-ga:
Thanks for the clarification above. I think the most expeditious way
to proceed is to say back to you, in my words, what I understand about
your request. That way you can correct any misunderstanding and fill
in certain gaps. I will avoid for now the temptation to comment on
the last item, about approximating a convolution on the Fourier
transform side, because it seems we have already a very shaky platform
of building blocks (assumptions) to nail down.
Let's alter your notation a bit. You have a continuous funtion f(t)
whose range is [-1,+1]. You don't describe the domain (in time)
although this is critical for what one might mean by the Fourier
transform of f(t), which I prefer to label F(x) to avoid confusion.
You say that F(x) is "continuous" but this is not the usual situation.
One ordinarily supposes that f(t) is defined on some finite time
interval and by "wrapping around" makes f(t) into a periodic function
(with period equal to the length of that interval). The Fourier
transform is then a "discrete" sequence of coefficients for the
sinusoidal "components" of f(t). In other words the function f(t) is
expressed as a trigonometric series using the terms of the "sequence"
defined by F(x) as coefficients.
On the other hand it is reasonable, if we make certain assumptions
about f(t), to define a Fourier transform on the entire real line
(-oo,+oo) as the domain of f(t). In particular one can do this if
f(t) has compact support, ie. is identically zero except on some
finite interval [a,b].
Adding to the confusion are your references to "fft" which is an
abbreviation for "fast Fourier transform". A fast Fourier transform
is inherently a mapping from discrete data to discrete data (usually,
but not invariably, when the number of nodes is a power of 2).
While awaiting your clarification about the nature of the function's
domain and the kind of Fourier transform intended, let me continue
with some remarks that are applicable to more or less any sort of
Fourier transform that might be used.
The Fourier transform should certainly be a linear mapping. That is,
given two continuous functions f(t) and g(t) in the time domain, their
linear combination:
c f(t) + d g(t)
for constants c,d will have Fourier transform:
c F(x) + d G(x)
provided F(x),G(x) are the respective Fourier transforms of f(t),g(t).
It very much seems that you have an "approximation scheme" for f(t) in
which you introduce a "step function" that I will call h(t), rather
than f(d), to emphasize that the function is defined for all the same
values of time t as f(t) is. What is different is that h(t) takes on
discrete values, presumably jumping by some equal increments, between
-1 and +1. I must admit your description of a "pulse function" placed
"when the integral [under f(t)] reaches 1" is not fully consistent
with this interpretation. However if taken literally it would be
quite possible to have functions varying back and further between -1
and +1 so that the integral of f(t) never reaches either +1 or -1, so
would presumably be mapped to a zero function.
In any case there seems to be nothing "sacred" about the particular
method used to initial compute h(t), because you will immediately
raise the concern about how best to modify h(t) to some other discrete
approximation. It is here that we need to be especially careful in
formulation.
Apparently you are not directly concerned with how well h(t)
approximates f(t), but more with how well the Fourier transform H(x)
approximates F(x). If that is indeed the goal, then we should
probably tackle the problem directly in the "frequency" domain.
Given the linearity of the Fourier transform and some other well known
properties, such as the effect of translation h(t-a) on the Fourier
transform (a special case of the convolution theorem), it is possible
to pass from the formulation of the approximation on the time domain
side of things to the approximation on the frequency domain side.
However the approximation problem itself appears to be a nonlinear
one. This is because (to recall a statement from your original
question) exactly N pulse functions are to be used, each of some
prescribed height (presumably chosen either positive or negative as
best suits the function) but of _unknown_ location. In other words
you wish to approximate f(t) by h(t) of the form:
h(t) = SUM s_i j(t - a_i) FOR i = 1 to N
where j(t) is a "standard" jump function (or step function if you
prefer), and the quantities s_i are "signs" limited to {-1,+1} while
the a_i's are "locations" for the jumps.
The goal is to minimize (in a sense that needs to be made more
precise, such as "by a least squares criterion") the Fourier transform
of f(t) - h(t). [Note: By linearity this is equivalent to minimizing
the difference of the Fourier transforms.]
Because it is a nonlinear problem, it is quite possible that the best
available algorithm will be some sort of iterative process close, at
least in spirit, to the "wiggling" described by your clarification.
However an iterative process need not be "brute force", and at least a
super-linear convergence should be expected with the right algorithm.
With a clear statement of the "objective" function (the quantity to be
minimized) it is even possible that an explicit solution is available.
Many times one is happy to have a proof that the solution obtained by
a numerical approach has an error that is no worse than some
prescribed constant times the best possible error, and it is even more
likely that such "near optimal" solutions can be easily (i.e.
"quickly") found.
In this connection I'll make one final observation, namely that the
Fourier mapping from square integrable functions on the real line to
square integrable functions on the real line can be shown to be
bounded and have bounded inverse. That is, the least squares error on
the time domain side can be used to estimate the least squares error
on the frequency domain side and conversely. In fact with a certain
amount of fiddling with the metrics, the mapping is an isometry
(Plancherel theorem), meaning that the "size" of a function and of its
Fourier transform (in a modified least squares sense) are equal.
The point of this is to indicate that for "near optimal"
approximations in the least squares sense, one has the choice of
working either in the time domain or the frequency domain, whichever
is convenient.
best wishes,
mathtalk-ga |
