is FFT always approximate?

Ghostie wrote:
> "robert bristow-johnson" <rbj@audioimagination.com> wrote in
> news:1154406448.806363.135510@b28g2000cwb.googlegroups.com:
>
> snip....snip
>
> > Rune, the DFT doesn't know or care what the "true" data is.  it
>
> ship....snip
>
>
> It's data are, not data is.  Data is plural.  Datum is singular.  I would
> have thought that someone as anal retentive as yourself would have known
> that.

i;m a Enjunir.  i kin spel.

sorry to see Bob spoofing you, Gary.

r b-j

robert bristow-johnson skrev:
> another hash over an old topic and perenial dispute here.
>
> Rune Allnor wrote:
> ...
> > It depends on your "true" data.
>
> Rune, the DFT doesn't know or care what the "true" data is.  it
> crunches the numbers the same in any case.  it does not know if the N
> samples you pass it were N samples of some aperiodic sequence or if
> those happened to be N samples defining exactly one period of a
> periodic sequence.  it deals with it the same in either case and (this
> is what is inexplicably controversial here sometimes) assumes it is the
> latter.

I agree with that.

> > If your data is a finite length sample of
> > a process of infinite duration, then all sorts of things happen and you
> > need to be very careful about how you proceed.
>
> to that we agree.  but i continue to contend that the "bad stuff" (the
> effect of windowing) happens when you yank that finite length sample
> out of that process of infinite duration.  that's when the windowing
> happens. (before the DFT even sees the data.)

Agreed.

> then when you pass those samples to the DFT, it inherently periodically
> extends that.

I think this is the crux of our "disagreement", to what little extent
we do disagree at all. What I am concerned, the DFT is a well-defined
operation that takes a finite-length sequence as input and produces
a finite-length at the output. All these windowing and circular
convolution effects only happen when we yank the DFT to work
on subseries of what ought to be infinite series. Which, I hope
you agree, the DFT was never supposed to deal with. We use the
DFT since we by practical constraints only can make a computer
work on finite sequences.

> i know Rick and other often object to anthropomorphizing
> the DFT, but the DFT assumes the N samples passed to it are one period
> of a periodic sequence.

I disagree with this as being a fundamental property of the DFT.
I agree that this is a side effect when using the DFT to process
finite samples of infinite sequences.

>  whether it was originally (which the OP should
> try to insure) or not is not something the DFT knows about.  it still
> periodically extends that data inherently in its fundamental operation.
>
> > You *can* proceed
> > assuming that you happened to sample exactly one period of some
> > periodic process, which everybody understand is a ridiculous claim.
>
> with scaling and interpolation it need not be ridiculous.

I find it ridiculous to claim that any finite sub sequence of an
infinite
series happens to represent exactly one period of the infinite series.

> > However, that's just about the only way forward in this case.
> ...
> > > when you scale it, you want the period to be precisely N samples long
> > > where N is the size of the DFT ("FFT" *is* a DFT, just a fast method of
> > > doing it).  the DFT inherently periodically extends whatever data you
> > > give it (i.e. it assumes the N samples passed to it are representative
> > > of exactly one period).
> >
> > RBJ is right, PROVIDED you really use the (finite length) DFT to
> > analyse some infinite length sequence. This periodic/non-periodic
> > thing is NOT a property with the DFT itself
>
> here we disagree.  i may state it more stridently the Oppenhiem and
> Schafer, but the main property of the DFT is that it maps one periodic
> sequence of length N to another periodic sequence of length N (where in
> both cases, only N samples are used to represent either) according to
> the equations:
>
>            N-1
>     X[k] = SUM{ x[n] exp(-j*2*pi*n*k/N) }
>            n=0
>
>
>                N-1
>     x[n] = 1/N SUM{ X[k] exp(+j*2*pi*n*k/N) }
>                k=0
>
>
> in both cases x[n+N] = x[n] and X[k+N] = X[k]  for all n and k.
>
> that's a pretty fundamental property.

The maths above is correct. However, there is no requirement imposed
by the (I)DFT to extend the signal from the n = [0,...,N-1] range into
the
n = -infinite,...,infinite range. You as user of the DFT wants that,
since you by context is assumed to work with finite subseries
of infinite sequences. 

Rune

Rune Allnor wrote:
> robert bristow-johnson skrev:
...
> >   i may state it more stridently than Oppenhiem and
> > Schafer, but the main property of the DFT is that it maps one periodic
> > sequence of length N to another periodic sequence of length N (where in
> > both cases, only N samples are used to represent either) according to
> > the equations:
> >
> >            N-1
> >     X[k] = SUM{ x[n] exp(-j*2*pi*n*k/N) }
> >            n=0
> >
> >
> >                N-1
> >     x[n] = 1/N SUM{ X[k] exp(+j*2*pi*n*k/N) }
> >                k=0
> >
> >
> > in both cases x[n+N] = x[n] and X[k+N] = X[k]  for all n and k.
> >
> > that's a pretty fundamental property.
>
> The maths above is correct. However, there is no requirement imposed
> by the (I)DFT to extend the signal from the n = [0,...,N-1] range into
> the n = -infinite,...,infinite range.

there is no requirement, but if you do operations in one domain that
cause shifting in the other domain (namely delay or convolution) if you
do not (periodically) extend the signal naturally beyond the [0 .. N)
range you must always use the modulo N operator to be correct in
general.  i keep asserting that putting the modulo N operator in there
is operationally indistinguishable from periodic extension.

r b-j

robert bristow-johnson skrev:
> Rune Allnor wrote:
> > robert bristow-johnson skrev:
> ...
> > >   i may state it more stridently than Oppenhiem and
> > > Schafer, but the main property of the DFT is that it maps one periodic
> > > sequence of length N to another periodic sequence of length N (where in
> > > both cases, only N samples are used to represent either) according to
> > > the equations:
> > >
> > >            N-1
> > >     X[k] = SUM{ x[n] exp(-j*2*pi*n*k/N) }
> > >            n=0
> > >
> > >
> > >                N-1
> > >     x[n] = 1/N SUM{ X[k] exp(+j*2*pi*n*k/N) }
> > >                k=0
> > >
> > >
> > > in both cases x[n+N] = x[n] and X[k+N] = X[k]  for all n and k.
> > >
> > > that's a pretty fundamental property.
> >
> > The maths above is correct. However, there is no requirement imposed
> > by the (I)DFT to extend the signal from the n = [0,...,N-1] range into
> > the n = -infinite,...,infinite range.
>
> there is no requirement, but if you do operations in one domain that
> cause shifting in the other domain (namely delay or convolution) if you
> do not (periodically) extend the signal naturally beyond the [0 .. N)
> range you must always use the modulo N operator to be correct in
> general.  i keep asserting that putting the modulo N operator in there
> is operationally indistinguishable from periodic extension.

Agreed. Doing those sorts of operations only make sense when
you use the DFT as a tool for analyzing ought-to-be-infinite series,
though.

Rune

robert bristow-johnson wrote:
> the DFT doesn't know or care what the "true" data is.  it
> crunches the numbers the same in any case.  it does not know if the N
> samples you pass it were N samples of some aperiodic sequence or if
> those happened to be N samples defining exactly one period of a
> periodic sequence.

The above contradicts the following:

> it deals with it the same in either case and (this
> is what is inexplicably controversial here sometimes) assumes it is the
> latter.
...
> when you pass those samples to the DFT, it inherently periodically
> extends that.

If the DFT inherently does something, then it does know or care.
But it doesn't.

> i know Rick and other often object to anthropomorphizing
> the DFT,

Because the DFT doesn't make assumptions.  It just operates
on data.  You could feed it periodic data, infinitely non-periodic
data, or ASCII poetry, and it would still transform a segment of
that data into a different basis vector space.

People interpreting the results are the ones making assumptions,
not the DFT operator.  For many purposes, the assumption of
periodicity is obviously false and thus will produce incorrect
interpretations of the those DFT results.

The math using inifnite sinusoids would work equally well with
truncated sinusoids for many of the properties of the FFT/DFT,
although not for others.  One only needs to extend the truncated
sinusoids for uses which need those properties.


IMHO. YMMV.
-- 
rhn A.T nicholson d.0.t C-o-M

Ron N. skrev:
> The math using inifnite sinusoids would work equally well with
> truncated sinusoids for many of the properties of the FFT/DFT,
> although not for others.

The maths works equally well in the case of infinte-duration
conbtinuous-time functions. Which happens to be the farthest
one can get from the DFT. RBJ is right in drawing a very definite
separation line between the two.

> One only needs to extend the truncated
> sinusoids for uses which need those properties.

And handle sampling, Gibbs phenomenon and contionuous
spectra along the way, as RBJ has made very clear on a number
of occations.

Rune

Ron N. wrote:
> robert bristow-johnson wrote:
> > the DFT doesn't know or care what the "true" data is.  it
> > crunches the numbers the same in any case.  it does not know if the N
> > samples you pass it were N samples of some aperiodic sequence or if
> > those happened to be N samples defining exactly one period of a
> > periodic sequence.
>
> The above contradicts the following:
>
> > it deals with it the same in either case and (this
> > is what is inexplicably controversial here sometimes) assumes it is the
> > latter.
> ...
> > when you pass those samples to the DFT, it inherently periodically
> > extends that.
>
> If the DFT inherently does something, then it does know or care.
> But it doesn't.

the one ("it does know or care") does not follow the other ("the DFT
inherently does something").  large planets in space inherently become
spherical, but i doubt they have a consciousness that knows are cares
about it.  some inanimate things in reality have inherent properties.
i am saying (as does the math) that the DFT has an inherent property of
periodically extending the data passed to it.

> > i know Rick and other often object to anthropomorphizing
> > the DFT,

i do that, BTW, for the same reason some computer
scientists/programmers do when they describe how a complicated
algorithm might work.  do those Expert Systems with Artificial
Intelligence really think?  can we sometimes describe their operation
with anthropomorphisms?

> Because the DFT doesn't make assumptions.  It just operates
> on data.  You could feed it periodic data, infinitely non-periodic
> data, or ASCII poetry, and it would still transform a segment of
> that data into a different basis vector space.

what are the basis functions that are being fit to the input data?  the
DFT is, by its very definition, fitting a bunch of discrete and
periodic basis functions to the ordered set of data passed to it.  to
anthropomorphize again, it is saying "what linear combination of these
sinusoids fit this input data?"  all of those sinusoids are inherently
periodic with period N.  the linear combination of those sinusoids are
also.

>
> People interpreting the results are the ones making assumptions,
> not the DFT operator.  For many purposes, the assumption of
> periodicity is obviously false,

if you have more information (even informal or ad hoc information) that
says that the input data was not likely periodic with period N, fine.
if you have no such information, then how can you be sure?

> and thus will produce incorrect
> interpretations of the those DFT results.

the difference between a correct and incorrect interpretation is purely
dependent on what the assumptions we make about what the input looked
like outside of the segment of samples passed to the DFT.

> The math using inifnite sinusoids would work equally well with
> truncated sinusoids for many of the properties of the FFT/DFT,
> although not for others.

yet the math using infinite sinusoids works correctly with *every* one
of the properties of the DFT.  so why use the truncated sinusoid model
when it doesn't work with everything (namely shifting and convolution)?

>  One only needs to extend the truncated
> sinusoids for uses which need those properties.

why bother to have the truncated sinusoids in the first place that you
may need to extend?

for some reason, the message i get from you, Ron, is that the truncated
sinusoid model or definition is the "natural" one and that this is the
one to use until you come upon a need to periodically extend it (which
is what you would need to do for shifting and convolution).  where i
(and Oppenhiem and Schafer and some other texts) are trying to tell you
that there is no operational difference between the DFT and the
Discrete Fourier Series and that the natural definition is the one with
infinite length sinusoids and you never need to "extend" that model
because it is always valid.

r b-j

robert bristow-johnson wrote:
> Ron N. wrote:
> > robert bristow-johnson wrote:
> > > the DFT doesn't know or care what the "true" data is.  it
> > > crunches the numbers the same in any case.  it does not know if the N
> > > samples you pass it were N samples of some aperiodic sequence or if
> > > those happened to be N samples defining exactly one period of a
> > > periodic sequence.
> >
> > The above contradicts the following:
> >
> > > it deals with it the same in either case and (this
> > > is what is inexplicably controversial here sometimes) assumes it is the
> > > latter.
> > ...
> > > when you pass those samples to the DFT, it inherently periodically
> > > extends that.
> >
> > If the DFT inherently does something, then it does know or care.
> > But it doesn't.
>
> the one ("it does know or care") does not follow the other ("the DFT
> inherently does something").  large planets in space inherently become
> spherical, but i doubt they have a consciousness that knows are cares
> about it.  some inanimate things in reality have inherent properties.
> i am saying (as does the math) that the DFT has an inherent property of
> periodically extending the data passed to it.
>
> > > i know Rick and other often object to anthropomorphizing
> > > the DFT,
>
> i do that, BTW, for the same reason some computer
> scientists/programmers do when they describe how a complicated
> algorithm might work.  do those Expert Systems with Artificial
> Intelligence really think?  can we sometimes describe their operation
> with anthropomorphisms?
>
> > Because the DFT doesn't make assumptions.  It just operates
> > on data.  You could feed it periodic data, infinitely non-periodic
> > data, or ASCII poetry, and it would still transform a segment of
> > that data into a different basis vector space.
>
> what are the basis functions that are being fit to the input data?  the
> DFT is, by its very definition, fitting a bunch of discrete and
> periodic basis functions to the ordered set of data passed to it.  to
> anthropomorphize again, it is saying "what linear combination of these
> sinusoids fit this input data?"  all of those sinusoids are inherently
> periodic with period N.  the linear combination of those sinusoids are
> also.
>
> >
> > People interpreting the results are the ones making assumptions,
> > not the DFT operator.  For many purposes, the assumption of
> > periodicity is obviously false,
>
> if you have more information (even informal or ad hoc information) that
> says that the input data was not likely periodic with period N, fine.
> if you have no such information, then how can you be sure?

It's actually the other way around.  The probability that an aperature
on a random arbitrary function just happens to be an integer period
window on a periodic or circular function looks close to zero.  So the
periodic interpretation might be the exceptional one which requires
information.

> > and thus will produce incorrect
> > interpretations of the those DFT results.
>
> the difference between a correct and incorrect interpretation is purely
> dependent on what the assumptions we make about what the input looked
> like outside of the segment of samples passed to the DFT.
>
> > The math using inifnite sinusoids would work equally well with
> > truncated sinusoids for many of the properties of the FFT/DFT,
> > although not for others.
>
> yet the math using infinite sinusoids works correctly with *every* one
> of the properties of the DFT.  so why use the truncated sinusoid model
> when it doesn't work with everything (namely shifting and convolution)?
>
> >  One only needs to extend the truncated
> > sinusoids for uses which need those properties.
>
> why bother to have the truncated sinusoids in the first place that you
> may need to extend?

I agree.  If you need to extend them, then you shouldn't use them
in that particular analysis or operation.

> for some reason, the message i get from you, Ron, is that the truncated
> sinusoid model or definition is the "natural" one and that this is the
> one to use until you come upon a need to periodically extend it (which
> is what you would need to do for shifting and convolution).

Not at all.  The natural definition is the one which fits the
assumptions about the data and the analysis needed.
If you need to do shifting or circular convolution on data
which might be periodic, then one definition is most useful.
If it is highly improbable that the data is periodic, then
other assumptions about the basis might require less "undoing"
of properties which are inconsistant with the analysis desired.

> where i
> (and Oppenhiem and Schafer and some other texts) are trying to tell you
> that there is no operational difference between the DFT and the
> Discrete Fourier Series and that the natural definition is the one with
> infinite length sinusoids and you never need to "extend" that model
> because it is always valid.

The natural definition makes sense only if the interpretation that
the underlying data is periodic or circular also makes sense.
The DFT can be used that way (for convolution, etc.), but is
often not (usually for lack of a more appropriate tool anywhere
near as computationally efficient as the FFT), especially for
non-synchronous spectral analysis.

If I use a hammer to stir pasta, it's cleanliness and coefficient
of drag in viscous fluids are probably more relevant than it's swing
weight and impact resonance.


IMHO. YMMV.
-- 
rhn A.T nicholson d.0.t C-o-M

Ron N. wrote:
> robert bristow-johnson wrote:
> > Ron N. wrote:
> > >
> > > People interpreting the results are the ones making assumptions,
> > > not the DFT operator.  For many purposes, the assumption of
> > > periodicity is obviously false,
> >
> > if you have more information (even informal or ad hoc information) that
> > says that the input data was not likely periodic with period N, fine.
> > if you have no such information, then how can you be sure?
>
> It's actually the other way around.  The probability that an aperature
> on a random arbitrary function just happens to be an integer period
> window on a periodic or circular function looks close to zero.  So the
> periodic interpretation might be the exceptional one which requires
> information.

well that depends on what you're doing.  the OP seems to think that he
can time scale the input so that a period is whatever length he wants.

you and i have both done stuff in audio/music.  in wavetable synthesis
(very similar to NCO or DCO or DDS or whatever), the wavetable
represents precisely one cycle of the waveform.  pass that to your FFT
and you have your harmonic coefficients wrapped in a nice package (no
need to do peak picking, etc.).  not all use of the FFT is "spectral
analysis" in that sense.

> > > and thus will produce incorrect interpretations of the those DFT results.
> >
> > the difference between a correct and incorrect interpretation is purely
> > dependent on what the assumptions we make about what the input looked
> > like outside of the segment of samples passed to the DFT.
> >
> > > The math using inifnite sinusoids would work equally well with
> > > truncated sinusoids for many of the properties of the FFT/DFT,
> > > although not for others.
> >
> > yet the math using infinite sinusoids works correctly with *every* one
> > of the properties of the DFT.  so why use the truncated sinusoid model
> > when it doesn't work with everything (namely shifting and convolution)?
> >
> > >  One only needs to extend the truncated
> > > sinusoids for uses which need those properties.
> >
> > why bother to have the truncated sinusoids in the first place that you
> > may need to extend?
>
> I agree.  If you need to extend them, then you shouldn't use them
> in that particular analysis or operation.

again, my point is that you cannot find a situation where that periodic
extension gives you the wrong answer, but i can find plenty
(multiplying one domain by anything that results in shifting or
convolution in the other) where leaving the periodic extension out
*does* create an error.

> > for some reason, the message i get from you, Ron, is that the truncated
> > sinusoid model or definition is the "natural" one and that this is the
> > one to use until you come upon a need to periodically extend it (which
> > is what you would need to do for shifting and convolution).
>
> Not at all.  The natural definition is the one which fits the
> assumptions about the data and the analysis needed.
> If you need to do shifting or circular convolution on data
> which might be periodic, then one definition is most useful.
> If it is highly improbable that the data is periodic, then
> other assumptions about the basis might require less "undoing"
> of properties which are inconsistant with the analysis desired.

i disagree.  even if the N samples are drawn from something that is not
periodic (or periodic with period N), this periodic extension happens
anyway, whether you like it or not.  doesn't matter where you draw if
from, if after the DFT you multiply the data by something and IDFT, you
will get circular convolution as if the data was originally from a
periodic sequence of period N.  if you don't like it, then you need to
deal with it and put in a work around (which is precisely what the
overlap-add and overlap-save schemes to do fast convolution are about).

that's the problem:  people decide that their input data is not
periodic (that's fine) and then they send it to an FFT thinking that it
remains aperiodic (not fine) and start complaining when they see or
hear glitches in the output because their impulse response straddled
the boundary between x[N-1] and x[0].

the DFT *always*, always, always, always, always periodically extends
the data that is passed to it, and if you don't keep that in mind, you
can get burned.

> > where i
> > (and Oppenhiem and Schafer and some other texts) are trying to tell you
> > that there is no operational difference between the DFT and the
> > Discrete Fourier Series and that the natural definition is the one with
> > infinite length sinusoids and you never need to "extend" that model
> > because it is always valid.
>
> The natural definition makes sense only if the interpretation that
> the underlying data is periodic or circular also makes sense.

that interpretation (periodic or circular extension) is the only one
that makes sense in general.  there are times when you may not need it,
but i can't think of any where it doesn't have some effect.  even the
wrapping of those sinc-like tales in the spectrum do to windowing in
the time domain.  there is virtually always some place where you have
to  keep it in mind.

> The DFT can be used that way (for convolution, etc.), but is
> often not (usually for lack of a more appropriate tool anywhere
> near as computationally efficient as the FFT), especially for
> non-synchronous spectral analysis.

i don't get what you're saying.  besides speed (and numerical round-off
errors), what's the difference between the DFT and FFT?

> If I use a hammer to stir pasta, it's cleanliness and coefficient
> of drag in viscous fluids are probably more relevant than it's swing
> weight and impact resonance.

i don't get the analogy.

r b-j

robert bristow-johnson wrote:
> the DFT *always*, always, always, always, always periodically extends
> the data that is passed to it, and if you don't keep that in mind, you
> can get burned.

Funny.  Last DFT I calculated fit in finite memory.  Neither did it
change the incoming audio sample stream.

> that interpretation (periodic or circular extension) is the only one
> that makes sense in general.  there are times when you may not need it,
> but i can't think of any where it doesn't have some effect.  even the
> wrapping of those sinc-like tales in the spectrum do to windowing in
> the time domain.

There can be no sinc-like tails if the function is periodic in the
aperature, since under that assumption, only bin frequencies can
exist.  Sinc-like tails can only wrap around if you postulate the
existance of non-bin frequencies, which is inconsistant with the
assumption that the results must be interpreted as if the data
were periodically extended.

In normal use, the data or function outside any finite DFT can
be either periodic or not.  Thus the results, interpreted as some
sort of spectrum, are often underconstrained (except in many
special cases, such as your synchronous waveform synthesizer).


IMHO. YMMV.
-- 
rhn A.T nicholson d.0.t C-o-M