FFT windowing and deconvolution

I would like to get some feedback on this idea. Multiplying
a signal in the time domain by a window before computing its FFT
is equivalent to the convolution of the transform of the signal
with the transform of the window.
It seems therefore that one could "undo" the effect of a square
window (i.e. FFT with no windowing at all) by applying a complex
deconvolution algorithm in the frequency domain.
Has this idea ever been tried? I know that deconvolution has
many problems, so I'm just testing the waters...

thanks
-Arrigo

"Arrigo Benedetti" <arrigo@vision.caltech.edu> wrote in message
news:6fd18256.0405191702.22300396@posting.google.com...
> I would like to get some feedback on this idea. Multiplying
> a signal in the time domain by a window before computing its FFT
> is equivalent to the convolution of the transform of the signal
> with the transform of the window.
> It seems therefore that one could "undo" the effect of a square
> window (i.e. FFT with no windowing at all) by applying a complex
> deconvolution algorithm in the frequency domain.
> Has this idea ever been tried? I know that deconvolution has
> many problems, so I'm just testing the waters...

Arrigo,

Well, it seems to me that the rectangular window creates a type of
fundamental limit or at least a very basic point of departure.

Deconvolution in frequency is like dividing by a full-length record in the
time domain - so it's like a window except the operation is division instead
of multiplication. If the dividing function d(t) has zeros - that's a
problem!  If it doesn't have zeros then perhaps it can be effected with
multiplication by its reciprocal 1/d(t).  Not a big difference perhaps in
principle - only in implementation.

You want to divide the time sequence such that the frequency domain smearing
and leakage are reduced?  This is equivalent to turning the frequency domain
transform of the time window into a unit sample.
One way to approximate this over a limited region may be to use
"supergaining" - by distorting the frequency domain outside the "visible
region" as termed by the antenna specialists.  Google on "supergain".

You can find functions with large peaks outside a given range of frequency
that tend to look better and better inside that same range.  These peaks
outside the range can be used to adjust the function between +/-pi - so that
you get "better" response there.  Think of the overall function as a sum of
shifted sincs and you are adjusting the "middle" of the sum with the tails
of the outlying sinc functions.

Somehow having sampled data in both time and frequency makes this probably
not feasible.  Continuous time windows and frequency functions that go from
+ to - infinity are the thing...

Anyway, in a time function that's continuous and time-limited, the frquency
domain is infinite and not sampled.  What happens is that the supergained
time window gets very large at the edges - which corresponds with large
peaks at high frequency - and you start running into practical problems of
precision of arithmetic, etc.....

Fred

Arrigo Benedetti wrote:
> I would like to get some feedback on this idea. Multiplying
> a signal in the time domain by a window before computing its FFT
> is equivalent to the convolution of the transform of the signal
> with the transform of the window.
> It seems therefore that one could "undo" the effect of a square
> window (i.e. FFT with no windowing at all) by applying a complex
> deconvolution algorithm in the frequency domain.
> Has this idea ever been tried? I know that deconvolution has
> many problems, so I'm just testing the waters...
> 
> thanks
> -Arrigo

The problem with no windowing is that the FFT acts on the signal as if 
it were one cycle of a repeating signal (this is why you get discrete 
frequencies out of it, by the way).  If you have no windowing, and if 
your signal doesn't match up at the 0 and 2^n-1 points in every way 
(i.e. the data and it's 1st, 2nd, 3rd .. (n - 1)th derivative all 
match), then the resulting discontinuity comes through the FFT like a 
step function, even though your data doesn't really contain a step.

Contrast this with windowed data that _does_ contain a step, say in the 
middle: you deemphasize the ends of your data set, but the middle of the 
set has that whopping big step in it which shows up in your data in the 
frequency domain.

Since the FFT is completely reversible there ought to be a way to do the 
calculation after the fact -- but a simple convolution wouldn't have the 
effect that you're looking for, because it would treat the "real" steps 
the same way as the "artificial" ones.  It may turn out, in fact, that 
the most computationally efficient way to realize the calculation would 
be to do the inverse FFT, window the resulting data, then do the forward 
FFT again!

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

"Arrigo Benedetti" <arrigo@vision.caltech.edu> wrote in message
news:6fd18256.0405191702.22300396@posting.google.com...
> It seems therefore that one could "undo" the effect of a square
> window (i.e. FFT with no windowing at all) by applying a complex
> deconvolution algorithm in the frequency domain.
> Has this idea ever been tried? I know that deconvolution has
> many problems, so I'm just testing the waters...

It's the same as dividing the samples outside the window by 0.  All of those
deconvolution problems you've heard about are division-by-zero or
division-by-nearly-zero problems.

"Fred Marshall" <fmarshallx@remove_the_x.acm.org> wrote in message news:<v5udnczuOcZikjHdRVn-vg@centurytel.net>...
> "Arrigo Benedetti" <arrigo@vision.caltech.edu> wrote in message
> news:6fd18256.0405191702.22300396@posting.google.com...
> > I would like to get some feedback on this idea. Multiplying
> > a signal in the time domain by a window before computing its FFT
> > is equivalent to the convolution of the transform of the signal
> > with the transform of the window.
> > It seems therefore that one could "undo" the effect of a square
> > window (i.e. FFT with no windowing at all) by applying a complex
> > deconvolution algorithm in the frequency domain.
> > Has this idea ever been tried? I know that deconvolution has
> > many problems, so I'm just testing the waters...
> 
> Arrigo,
> 
> Well, it seems to me that the rectangular window creates a type of
> fundamental limit or at least a very basic point of departure.
> 
> Deconvolution in frequency is like dividing by a full-length record in the
> time domain - so it's like a window except the operation is division instead
> of multiplication. If the dividing function d(t) has zeros - that's a
> problem!  If it doesn't have zeros then perhaps it can be effected with
> multiplication by its reciprocal 1/d(t).  Not a big difference perhaps in
> principle - only in implementation.
> 
> You want to divide the time sequence such that the frequency domain smearing
> and leakage are reduced?

Exactly. I want to avoid using a tapering window in the time domain since
there might be useful features in the signal near the borders, and the
window would kill the energy of those features.

Thanks for your comments,

-Arrigo

"Arrigo Benedetti" <arrigo@vision.caltech.edu> wrote in message
news:6fd18256.0405192225.11833df6@posting.google.com...
> "Fred Marshall" <fmarshallx@remove_the_x.acm.org> wrote in message
news:<v5udnczuOcZikjHdRVn-vg@centurytel.net>...
> > "Arrigo Benedetti" <arrigo@vision.caltech.edu> wrote in message
> > news:6fd18256.0405191702.22300396@posting.google.com...
> > > I would like to get some feedback on this idea. Multiplying
> > > a signal in the time domain by a window before computing its FFT
> > > is equivalent to the convolution of the transform of the signal
> > > with the transform of the window.
> > > It seems therefore that one could "undo" the effect of a square
> > > window (i.e. FFT with no windowing at all) by applying a complex
> > > deconvolution algorithm in the frequency domain.
> > > Has this idea ever been tried? I know that deconvolution has
> > > many problems, so I'm just testing the waters...
> >
> > Arrigo,
> >
> > Well, it seems to me that the rectangular window creates a type of
> > fundamental limit or at least a very basic point of departure.
> >
> > Deconvolution in frequency is like dividing by a full-length record in
the
> > time domain - so it's like a window except the operation is division
instead
> > of multiplication. If the dividing function d(t) has zeros - that's a
> > problem!  If it doesn't have zeros then perhaps it can be effected with
> > multiplication by its reciprocal 1/d(t).  Not a big difference perhaps
in
> > principle - only in implementation.
> >
> > You want to divide the time sequence such that the frequency domain
smearing
> > and leakage are reduced?
>
> Exactly. I want to avoid using a tapering window in the time domain since
> there might be useful features in the signal near the borders, and the
> window would kill the energy of those features.
>
> Thanks for your comments,
>
> -Arrigo

Arrigo,

You should either make your window larger to incorporate those features you
want to see (so they're not at the edge of your window) or else use multiple
overlapping windows so that you can place those "edge" features in the
center of a new window.

The windowing is a *good* thing.  You're forced to use some kind of window
to do a finite FFT so you might as well choose it yourself.  Using "no"
window imposes a rectangle window which smears your frequencies around quite
a bit.

On Thu, 20 May 2004 13:42:42 GMT, "Brad Griffis"
<bradgriffis@hotmail.com> wrote:

>The windowing is a *good* thing.  You're forced to use some kind of window
>to do a finite FFT so you might as well choose it yourself.  Using "no"
>window imposes a rectangle window which smears your frequencies around quite
>a bit.

I have been using "no" windowing in a piano tuning application and I
find that the difference between windowing and no windowing is most
predominate in the lower frequencies.  If F is the sampling frequency,
then the spectrum from F/4 to F/2 seems to be largely unsmeared.


-Robert Scott
 Ypsilanti, Michigan
(Reply through this forum, not by direct e-mail to me, as automatic reply address is fake.)

Arrigo Benedetti wrote:

> I would like to get some feedback on this idea. Multiplying
> a signal in the time domain by a window before computing its FFT
> is equivalent to the convolution of the transform of the signal
> with the transform of the window.
> It seems therefore that one could "undo" the effect of a square
> window (i.e. FFT with no windowing at all) by applying a complex
> deconvolution algorithm in the frequency domain.
> Has this idea ever been tried? I know that deconvolution has
> many problems, so I'm just testing the waters...

There is a book, "Deconvolution of images and spectra" by Jansson,
(The first edition was called "Deconvolution: with applications to 
spectroscopy")

It covers very well both linear and non-linear deconvolution.

Consider that a power spectrum should never go negative,
and an absorption spectrum should stay between 0 and 1, yet
linear deconvolution algorithms don't restrict that.

-- glen