Appendix A: Types of Fourier Transforms

On Jan 18, 4:11 pm, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:
> ...
> But note that this is specifically due to using the DFT.  The DCT,
> which doesn't have periodic boundary conditions, doesn't have that.
> ...

Could you give a definition of what the 'periodic boundary condition'
of a transform is, that refers to aspects only of the transform and
not to any application?

> The DFT can also be used in non-periodic problems, as long as one
> stays away from the ends.  If you extend the signal on both ends,
> slowly going toward zero, that removes much of the problem.
>
> -- glen

What does 'stay away from the ends' specifically mean? And what
'problem' ? Is the  'problem' the characteristic of an application?

Dale B.Dalrymple

On Wed, 19 Jan 2011 00:11:25 +0000 (UTC), glen herrmannsfeldt
<gah@ugcs.caltech.edu> wrote:

>dbd <dbd@ieee.org> wrote:
>(snip, I wrote)
>
>>> Yes, but now consider a low-pass filter. &#4294967295;You know that high
>>> frequencies are required for any discontinuity (or fast
>>> transitions) in the signal. &#4294967295;The DFT also requires high
>>> frequency components for discontinuities between the end
>>> and the beginning.
> 
>> DFTs don't 'require' anything.I think that the anthropomorphic
>> language blurs the issues of what characteristics are part of the
>> signal, the transform and the user's application.
>
>The DFT has periodic boundary conditions, it doesn't "require"
>them.  Now, if one uses the transform-filter-inverse transform
>method, then the inverse transform "requires" the high frequency
>components to generate a discontinuity between the beginning
>and the end.  That is the sense of "require" that I meant.
> 
>> There is ambiguity about whether the discontinuity comes from the
>> signal being analyzed or the window inherent in the calculation of a
>> DFT As usual with the DFT, you can't tell from the information in the
>> vector operated on by the DFT or the vector output by the DFT. It's
>> all about specific applications, the signals and the assumptions of
>> the application. In the real world there are often opportunities to
>> perform additional DFTs using additional samples or even examining the
>> additional samples themselves to resolve ambiguity.
>
>But note that this is specifically due to using the DFT.  The DCT,
>which doesn't have periodic boundary conditions, doesn't have that.
> 
>(snip)
>
>>> Cows don't have periodic boundary conditions.
> 
>> Don't mathematicians usually approach this issue by assuming a
>> spherical cow?
>
>Yes, but spherical cows also don't have periodic boundary conditions.
>
>In the story I remember, it was the physicist that used the
>spherical approximation to the cow.    As I previously mentioned,
>solid-state physics does use periodic boundary conditions in
>situations that aren't periodic.  For the inside of a crystal,
>and not too close to the surface, it is a very good approximation.
>
>The DFT can also be used in non-periodic problems, as long as one
>stays away from the ends.  If you extend the signal on both ends,
>slowly going toward zero, that removes much of the problem.

Because you've added a taper to the rectangular window.  ;)

You're pointing out the utility of using the periodic interpretation.
If that adds value to you and helps your understanding, great.   If it
helps you convey concepts to other people, great.  I agree, it is
useful.  Much of the same concepts are consistent with the rectangular
window viewpoint.


Eric Jacobsen
Minister of Algorithms
Abineau Communications
http://www.abineau.com

On Jan 18, 9:19 pm, eric.jacob...@ieee.org (Eric Jacobsen) wrote:
>
> You're pointing out the utility of using the periodic interpretation.
> If that adds value to you and helps your understanding, great.   If it
> helps you convey concepts to other people, great.  I agree, it is
> useful.  Much of the same concepts are consistent with the rectangular
> window viewpoint.

Just to be clear, is this the rectangular viewpoint:

                   N-1
    x[n] = (1/N) * SUM{ X[k] e^(i*2*pi*n*k/N) }
                   k=0

          for   0 <= n < N,  zero otherwise (or undefined)


            N-1
    X[k] =  SUM{ x[n] e^(-i*2*pi*n*k/N) }
            n=0

          for   0 <= k < N,  zero otherwise (or undefined)

?


If that is the case, then what is the inverse DFT of


     Y[k]  =  X[k] * e^(-i*2*pi*k*m/N)

     m = integer
     (of course, this need be defined only for 0 <= k < N)
?


Either

(A) you have to accept the periodic extension done to x[n] by the DFT:

      y[n]  =  x[n-m]

      and  x[n+N] = x[n]   for all n

or

(B) you have to use modulo-N arithmetic for the index of x[n].

      y[n]  =  x[(n-m)mod_N]

      x[n] is not defined outside   0 <= n < N


You have to do one of the two.  Other than some klunky notational
issue with option (B), what is the operational difference between the
two?

"Much of the same concepts are consistent" between (A) and (B), but
not all.  not really.  are they, Eric?

you can say we have basis functions defined as

     e^(i*2*pi*k*n/N) * (u[n] - u[n-N])  (u[n] is unit step)

but what does that get you?  what possible use is it to truncate the
basis functions?


r b-j

>
> The repeating sequence point of view does provide some insights, and
> is certainly valid, but is not the only way of looking at it. �One
> doesn't really know what color the other side of the cow is if it
> isn't observed. �For certain breeds (i.e., a restricted or narrowed
> interpretation), like black angus or something, there's a high
> probability that observing one side of the cow tells you about the
> other side, but assuming it to be true for all cows would be
> inappropriate.
>

I'm glad my bringing up the old "cow observation story" has brought
some discussion to the problem.

Certainly for some breeds with solid color, the assumptions are pretty
good (e.g. black and red angus). Even a two color Galloway Belted
(looks like an Oreo cookie - from head to tail -> black - white -
black.) has simlar looking sides.  But like you say not all cows
exhibit lateral color symmetry. For example Holsteins and Guernseys
have two colors broken up into large patches which are almays always
dissimilar laterally.


For something OT, many mammalian coat patterns result from a simple
activator-inhibitor model. I.e., the DNA doesn't have to code for the
complex pattern on a tiger or a giraffe in terms of the detail of the
spots and stripes. The color centers form (noisey seeds) in the fetus
and sometimes the color centers wrap around the body (a boundary
condition perhaps?) and merge into a larger spot. This forming when
the fetus is rather small is why you have spotted animals with striped
tails but not striped animals with spotted tails. The fetal tails may
be either conical or cylindrical.  Somtimes the color centers can be
large or small so we have mammals with just one "spot" - like an all
brown cow. Or we may just get two spots of color like a Galois goat -
half black and half white. Or three spots like the Galloway belted cow
etc. I thought you'll might find this interesting. It is amazing that
such a simple model can result in many complex patterns. Nature's form
of data compression - instead of coding the pattern, she codes the
model's parameters.

Clay

On Tue, 18 Jan 2011 21:25:28 -0800 (PST), robert bristow-johnson
<rbj@audioimagination.com> wrote:

>On Jan 18, 9:19 pm, eric.jacob...@ieee.org (Eric Jacobsen) wrote:
>>
>> You're pointing out the utility of using the periodic interpretation.
>> If that adds value to you and helps your understanding, great.   If it
>> helps you convey concepts to other people, great.  I agree, it is
>> useful.  Much of the same concepts are consistent with the rectangular
>> window viewpoint.
>
>Just to be clear, is this the rectangular viewpoint:
>
>                   N-1
>    x[n] = (1/N) * SUM{ X[k] e^(i*2*pi*n*k/N) }
>                   k=0
>
>          for   0 <= n < N,  zero otherwise (or undefined)
>
>
>            N-1
>    X[k] =  SUM{ x[n] e^(-i*2*pi*n*k/N) }
>            n=0
>
>          for   0 <= k < N,  zero otherwise (or undefined)
>
>?
>
>
>If that is the case, then what is the inverse DFT of
>
>
>     Y[k]  =  X[k] * e^(-i*2*pi*k*m/N)
>
>     m = integer
>     (of course, this need be defined only for 0 <= k < N)
>?
>
>
>Either
>
>(A) you have to accept the periodic extension done to x[n] by the DFT:
>
>      y[n]  =  x[n-m]
>
>      and  x[n+N] = x[n]   for all n
>
>or
>
>(B) you have to use modulo-N arithmetic for the index of x[n].
>
>      y[n]  =  x[(n-m)mod_N]
>
>      x[n] is not defined outside   0 <= n < N
>
>
>You have to do one of the two.  Other than some klunky notational
>issue with option (B), what is the operational difference between the
>two?

I think that's a good example of how understanding the "periodic"
point of view helps to understand what's happening, but I don't see
how it excludes the "rectangular window" point of view.

Swapping domains for a moment (because they're really only relevant to
where the data came from):

     y[k]  =  x[k] * e^(-i*2*pi*k*m/N)

just mixes (frequency shifts) the signal x(k) by the frequency of the
complex sinusoid.    It will be a periodic shift because for sampled
data the supported spectrum is repeated infinitely in both directions,
so whatever frequencies shift off one end shift back in the other.
This can be done with the simple mixing operation described above; a
DFT is not necessary to demonstrate the effect. So a periodic
interpretation of the process isn't necessary with a simple domain
shift (which I think is arbitrary for the purposes of this
discussion).

Alternatively, recognizing that interpreting from the other domain, as
you proposed, i.e., 

     Y[k]  =  X[k] * e^(-i*2*pi*k*m/N)

is convolution in the time domain with an impulse at an arbitrary
location.   Only the reference function has to be periodically
extended to produce circular convolution, so even from a
theoretic/academic point of view the output will be circular even if
the input data has a rectangular window and is not periodic.   This
will produce the same result produced by multiplication in the
frequency domain with a complex sinusoid.


>"Much of the same concepts are consistent" between (A) and (B), but
>not all.  not really.  are they, Eric?

I don't know, I can't think of any that aren't consistent, but I left
the door open by saying "much" instead of "all".

>you can say we have basis functions defined as
>
>     e^(i*2*pi*k*n/N) * (u[n] - u[n-N])  (u[n] is unit step)
>
>but what does that get you?  what possible use is it to truncate the
>basis functions?

I don't know, but there may be some utility to it.   My comments have
been about the viewpoint that the data is not periodic, but merely
some sequence x that existed during the aperture of interest.


Eric Jacobsen
Minister of Algorithms
Abineau Communications
http://www.abineau.com

On Jan 19, 3:09 pm, eric.jacob...@ieee.org (Eric Jacobsen) wrote:
> On Tue, 18 Jan 2011 21:25:28 -0800 (PST), robert bristow-johnson
>
>
>
> <r...@audioimagination.com> wrote:
> >On Jan 18, 9:19 pm, eric.jacob...@ieee.org (Eric Jacobsen) wrote:
>
> >> You're pointing out the utility of using the periodic interpretation.
> >> If that adds value to you and helps your understanding, great.   If it
> >> helps you convey concepts to other people, great.  I agree, it is
> >> useful.  Much of the same concepts are consistent with the rectangular
> >> window viewpoint.
>
> >Just to be clear, is this the rectangular viewpoint:
>
> >                   N-1
> >    x[n] = (1/N) * SUM{ X[k] e^(i*2*pi*n*k/N) }
> >                   k=0
>
> >          for   0 <= n < N,  zero otherwise (or undefined)
>
> >            N-1
> >    X[k] =  SUM{ x[n] e^(-i*2*pi*n*k/N) }
> >            n=0
>
> >          for   0 <= k < N,  zero otherwise (or undefined)
>
> >?
>
> >If that is the case, then what is the inverse DFT of
>
> >     Y[k]  =  X[k] * e^(-i*2*pi*k*m/N)
>
> >     m = integer
> >     (of course, this need be defined only for 0 <= k < N)
> >?
>
> >Either
>
> >(A) you have to accept the periodic extension done to x[n] by the DFT:
>
> >      y[n]  =  x[n-m]
>
> >      and  x[n+N] = x[n]   for all n
>
> >or
>
> >(B) you have to use modulo-N arithmetic for the index of x[n].
>
> >      y[n]  =  x[(n-m)mod_N]
>
> >      x[n] is not defined outside   0 <= n < N
>
> >You have to do one of the two.  Other than some klunky notational
> >issue with option (B), what is the operational difference between the
> >two?
>
> I think that's a good example of how understanding the "periodic"
> point of view helps to understand what's happening, but I don't see
> how it excludes the "rectangular window" point of view.
>
> Swapping domains for a moment (because they're really only relevant to
> where the data came from):
>
>      y[k]  =  x[k] * e^(-i*2*pi*k*m/N)
>
> just mixes (frequency shifts) the signal x(k) by the frequency of the
> complex sinusoid.    It will be a periodic shift because for sampled
> data the supported spectrum is repeated infinitely in both directions,
> so whatever frequencies shift off one end shift back in the other.
> This can be done with the simple mixing operation described above; a
> DFT is not necessary to demonstrate the effect. So a periodic
> interpretation of the process isn't necessary with a simple domain
> shift (which I think is arbitrary for the purposes of this
> discussion).
>
> Alternatively, recognizing that interpreting from the other domain, as
> you proposed, i.e.,
>
>      Y[k]  =  X[k] * e^(-i*2*pi*k*m/N)
>
> is convolution in the time domain with an impulse at an arbitrary
> location.   Only the reference function has to be periodically
> extended to produce circular convolution,

what's a "reference function"?  is it x[n]?

> so even from a
> theoretic/academic point of view the output will be circular even if
> the input data has a rectangular window and is not periodic.

so you mean that you pass the DFT a finite (and rectangularly
windowed) set of data and what did the DFT do to it?  might the DFT
have periodically extended the data you tossed to it?

>   This will produce the same result produced by multiplication
> in the frequency domain with a complex sinusoid.

okay, sorry to be blunt, Eric;  let

            N-1
   x[n]  =  SUM{ X[k] * b_k[n] }
            k=0

so is it this basis function

   b_k[n]  =  (1/N) * e^(i*2*pi*k*n/N) * (u[n] - u[n-N])

or is it this basis function

   b_k[n]  =  (!/N) * e^(i*2*pi*k*n/N)

that is getting shifted by m samples?

which is it?

> >you can say we have basis functions defined as
>
> >     e^(i*2*pi*k*n/N) * (u[n] - u[n-N])  (u[n] is unit step)
>
> >but what does that get you?  what possible use is it to truncate the
> >basis functions?
>
> I don't know, but there may be some utility to it.

i'd like to know what utility there may be.

>  My comments have
> been about the viewpoint that the data is not periodic, but merely
> some sequence x that existed during the aperture of interest.

sure.  this takes us back to our old 1995 discussion.  applying an
"aperture of interest" is the same as yanking N adjacent samples out
from a stream.  that's applying a window.  if you want, you can window
it further with a Hann or Hamming or Kaiser or whatever.  that has the
effect of windowing on your data (the convolution in the frequency
domain).

THEN you pass it to the DFT.  that periodically extends whatever the
finite data is at that point.  the DFT is not applying the window, but
the DFT *does* periodically extend the data.

i *still* haven't the foggiest what is controversial.  even if i say
"the DFT and DFS are one-and-the-same", i *still* don't get what
problem people have with that.

r b-j

On Wed, 19 Jan 2011 17:44:47 -0800 (PST), robert bristow-johnson
<rbj@audioimagination.com> wrote:

>On Jan 19, 3:09 pm, eric.jacob...@ieee.org (Eric Jacobsen) wrote:
>> On Tue, 18 Jan 2011 21:25:28 -0800 (PST), robert bristow-johnson
>>
>>
>>
>> <r...@audioimagination.com> wrote:
>> >On Jan 18, 9:19 pm, eric.jacob...@ieee.org (Eric Jacobsen) wrote:
>>
>> >> You're pointing out the utility of using the periodic interpretation.
>> >> If that adds value to you and helps your understanding, great.   If it
>> >> helps you convey concepts to other people, great.  I agree, it is
>> >> useful.  Much of the same concepts are consistent with the rectangular
>> >> window viewpoint.
>>
>> >Just to be clear, is this the rectangular viewpoint:
>>
>> >                   N-1
>> >    x[n] = (1/N) * SUM{ X[k] e^(i*2*pi*n*k/N) }
>> >                   k=0
>>
>> >          for   0 <= n < N,  zero otherwise (or undefined)
>>
>> >            N-1
>> >    X[k] =  SUM{ x[n] e^(-i*2*pi*n*k/N) }
>> >            n=0
>>
>> >          for   0 <= k < N,  zero otherwise (or undefined)
>>
>> >?
>>
>> >If that is the case, then what is the inverse DFT of
>>
>> >     Y[k]  =  X[k] * e^(-i*2*pi*k*m/N)
>>
>> >     m = integer
>> >     (of course, this need be defined only for 0 <= k < N)
>> >?
>>
>> >Either
>>
>> >(A) you have to accept the periodic extension done to x[n] by the DFT:
>>
>> >      y[n]  =  x[n-m]
>>
>> >      and  x[n+N] = x[n]   for all n
>>
>> >or
>>
>> >(B) you have to use modulo-N arithmetic for the index of x[n].
>>
>> >      y[n]  =  x[(n-m)mod_N]
>>
>> >      x[n] is not defined outside   0 <= n < N
>>
>> >You have to do one of the two.  Other than some klunky notational
>> >issue with option (B), what is the operational difference between the
>> >two?
>>
>> I think that's a good example of how understanding the "periodic"
>> point of view helps to understand what's happening, but I don't see
>> how it excludes the "rectangular window" point of view.
>>
>> Swapping domains for a moment (because they're really only relevant to
>> where the data came from):
>>
>>      y[k]  =  x[k] * e^(-i*2*pi*k*m/N)
>>
>> just mixes (frequency shifts) the signal x(k) by the frequency of the
>> complex sinusoid.    It will be a periodic shift because for sampled
>> data the supported spectrum is repeated infinitely in both directions,
>> so whatever frequencies shift off one end shift back in the other.
>> This can be done with the simple mixing operation described above; a
>> DFT is not necessary to demonstrate the effect. So a periodic
>> interpretation of the process isn't necessary with a simple domain
>> shift (which I think is arbitrary for the purposes of this
>> discussion).
>>
>> Alternatively, recognizing that interpreting from the other domain, as
>> you proposed, i.e.,
>>
>>      Y[k]  =  X[k] * e^(-i*2*pi*k*m/N)
>>
>> is convolution in the time domain with an impulse at an arbitrary
>> location.   Only the reference function has to be periodically
>> extended to produce circular convolution,
>
>what's a "reference function"?  is it x[n]?

Sorry, for correlation or convolution I call one of the input vectors
the "reference function" if it's the template that's being matched or
convolved.    In this case it'd be the impulse function convolved with
x(n).

>
>> so even from a
>> theoretic/academic point of view the output will be circular even if
>> the input data has a rectangular window and is not periodic.
>
>so you mean that you pass the DFT a finite (and rectangularly
>windowed) set of data and what did the DFT do to it?  might the DFT
>have periodically extended the data you tossed to it?

It might have if you assign it those kinds of properties in how you
think of it.  My point is just that you don't have to make that
assumption.  As has been previously pointed out, it's just a linear
algebra equation.   It doesn't really do anything outside the vectors
of interest.

>>   This will produce the same result produced by multiplication
>> in the frequency domain with a complex sinusoid.
>
>okay, sorry to be blunt, Eric;  let
>
>            N-1
>   x[n]  =  SUM{ X[k] * b_k[n] }
>            k=0
>
>so is it this basis function
>
>   b_k[n]  =  (1/N) * e^(i*2*pi*k*n/N) * (u[n] - u[n-N])
>
>or is it this basis function
>
>   b_k[n]  =  (!/N) * e^(i*2*pi*k*n/N)
>
>that is getting shifted by m samples?
>
>which is it?

You lost me.   I don't think I mentioned shifting any basis functions
anywhere.

>> >you can say we have basis functions defined as
>>
>> >     e^(i*2*pi*k*n/N) * (u[n] - u[n-N])  (u[n] is unit step)
>>
>> >but what does that get you?  what possible use is it to truncate the
>> >basis functions?
>>
>> I don't know, but there may be some utility to it.
>
>i'd like to know what utility there may be.

Again, the basis functions in the matrix in the linear algebra
equation are most finite length.   Whether you think of that as
truncated periodic functions or reference vectors for a correlator
bank or some other viewpoint, they're finite length.

>>  My comments have
>> been about the viewpoint that the data is not periodic, but merely
>> some sequence x that existed during the aperture of interest.
>
>sure.  this takes us back to our old 1995 discussion.  applying an
>"aperture of interest" is the same as yanking N adjacent samples out
>from a stream.  that's applying a window.  if you want, you can window
>it further with a Hann or Hamming or Kaiser or whatever.  that has the
>effect of windowing on your data (the convolution in the frequency
>domain).
>
>THEN you pass it to the DFT.  that periodically extends whatever the
>finite data is at that point.  the DFT is not applying the window, but
>the DFT *does* periodically extend the data.

Where does it do that?  I suggest it's only in the minds of those who
like to think of it that way, which seems to be a very useful thing
for those so inclined.   There is no arithmetic operation in the DFT
associated with extending the input vector or the basis functions.

>i *still* haven't the foggiest what is controversial.  even if i say
>"the DFT and DFS are one-and-the-same", i *still* don't get what
>problem people have with that.
>
>r b-j

I don't have a problem with it.   My point of view is that there is
not one single point of view that must be observed to the exclusion of
other valid points of view.


Eric Jacobsen
Minister of Algorithms
Abineau Communications
http://www.abineau.com

okay, Eric, i asked this question:

> >> > .... what is the inverse DFT of
> >> >
> >> >     Y[k]  =  X[k] * e^(-i*2*pi*k*m/N)
> >> >
> >> >     m = integer
> >> >     (of course, this need be defined only for 0 <= k < N)
> >> > ?

i even provided a two-choice multiple choice answer (is it A or is it
B?).  then i reformed the two-choices to this:

> > ... &#4294967295;let
> >
> > &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295;N-1
> > &#4294967295; x[n] &#4294967295;= &#4294967295;SUM{ X[k] * b_k[n] }
> > &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295;k=0
> >
> > so is it this basis function
> >
> > &#4294967295; b_k[n] &#4294967295;= &#4294967295;(1/N) * e^(i*2*pi*k*n/N) * (u[n] - u[n-N])
> >
> > or is it this basis function
> >
> > &#4294967295; b_k[n] &#4294967295;= &#4294967295;(!/N) * e^(i*2*pi*k*n/N)
> >
> > that is getting shifted by m samples?
> >
> > which is it?
>
> You lost me. &#4294967295;

have i found you by this point?

> I don't think I mentioned shifting any basis functions anywhere.

you didn't.  to try to get a clear and unambiguous answer to my
question, i reformed the A and B answers.  if both A and B are wrong,
i invite you to come up with a C answer.  but i would like a clear
answer to my question.

i'll ask it as clearly and completely as i can:

Let the DFT of x[n] be defined as:

            N-1
    X[k] =  SUM{ x[n] e^(-i*2*pi*n*k/N) }
            n=0

I don't care whether or not you want to define X[k] for integers k
outside of the interval 0 <= k < N .  Maybe X[k] exists out there or
maybe not.  So ...

Given x[n], with its DFT of X[k], what is y[n], the inverse DFT of

     Y[k]  =  X[k] * e^(-i*2*pi*k*m/N)

where m is an integer?

Is it

(A)  y[n]  =  x[n-m]

where

            N-1
   x[n]  =  SUM{ X[k] * b_k[n] }
            k=0

and  b_k[n]  =  (1/N) * e^(i*2*pi*k*n/N)  ?



Or is it

(B)  y[n]  =  x[n-m]

where

            N-1
   x[n]  =  SUM{ X[k] * b_k[n] }
            k=0

and  b_k[n]  =  (1/N) * e^(i*2*pi*k*n/N) * (u[n]-u[n-N])

and where u[n] = 1 for n >=0  and  0 otherwise ?


Or is it

(C)  y[n]  =  x[ (n-m)mod_N ]

where

            N-1
   x[n]  =  SUM{ X[k] * b_k[n] }
            k=0

and  b_k[n]  =  (1/N) * e^(i*2*pi*k*n/N) * (u[n]-u[n-N])

and where  (n)mod_N = n - N*floor(n/N)

and floor(v) is the largest integer not exceeding the real number v?


Or is it

(D)  none of the above ?


can i nail you down with an answer to this question?




> >> > you can say we have basis functions defined as
> >> >
> >> > &#4294967295; &#4294967295; e^(i*2*pi*k*n/N) * (u[n] - u[n-N]) &#4294967295;(u[n] is unit step)
> >> >
> >> > but what does that get you? &#4294967295;what possible use is it to truncate
> >> > the basis functions?
> >>
> >> I don't know, but there may be some utility to it.
> >
> > i'd like to know what utility there may be.
>

i'm still waiting to know what the utility is of considering the basis
functions to be

  b_k[n]  =  (1/N) * e^(i*2*pi*k*n/N) * (u[n]-u[n-N]) .

what good is that?  specifically, what good is the rectangular window
(u[n]-u[n-N]) for?  what does it do for us?  what possible use is it?


> Again, the basis functions in the matrix in the linear algebra
> equation are most finite length. &#4294967295; Whether you think of that as
> truncated periodic functions or reference vectors for a correlator
> bank or some other viewpoint, they're finite length.

it's a finite set of data.  but once you're inside the DFT, once
you've sent this finite-length sequence to the DFT, that finite set of
data no longer has meaning of being finite in length.  that DFT thinks
that this finite set of data represents one period of an infinite and
periodic sequence, just as the DFS does (with more explicit language).

that does not alter the possibility that this finite set of data had
original meaning that was non-periodic or was extracted from something
non-periodic.  that property can be attached to that finite set of
data UNTIL the DFT gets a hold of it.  after the DFT gets it, the
property of being a finite-length, non-periodic sequence of values is
lost.

> >> &#4294967295;My comments have
> >> been about the viewpoint that the data is not periodic, but merely
> >> some sequence x that existed during the aperture of interest.
> >
> > sure. &#4294967295;this takes us back to our old 1995 discussion. &#4294967295;applying an
> > "aperture of interest" is the same as yanking N adjacent samples out
> > from a stream. &#4294967295;that's applying a window. &#4294967295;if you want, you can window
> > it further with a Hann or Hamming or Kaiser or whatever. &#4294967295;that has the
> > effect of windowing on your data (the convolution in the frequency
> > domain).
> >
> > THEN you pass it to the DFT. &#4294967295;that periodically extends whatever the
> > finite data is at that point. &#4294967295;the DFT is not applying the window, but
> > the DFT *does* periodically extend the data.
>
> Where does it do that? &#4294967295;I suggest it's only in the minds of those who
> like to think of it that way, which seems to be a very useful thing
> for those so inclined.

I'm maintaining (and I think that Glen H is also) that "it does that"
when it is fitting a linear combination of these periodic basis
functions to the finite set of data in the "aperture of interest".
That's what the DFT does.  It's fitting those basis functions that I
am calling "b_k[n]" above to x[n].  It is maybe only looking at the
fit for 0 <= n < N (because that is only where x[n] was defined when
passed to the DFT), but in making that fit, it essentially
periodically extends x[n] outward in both directions to infinity.

> There is no arithmetic operation in the DFT
> associated with extending the input vector or the basis functions.

YES THERE IS!!  And i spelled it out with my multiple-choice question
above.

r b-j

Eric Jacobsen <eric.jacobsen@ieee.org> wrote:
(snip)

> Again, the basis functions in the matrix in the linear algebra
> equation are most finite length.   Whether you think of that as
> truncated periodic functions or reference vectors for a correlator
> bank or some other viewpoint, they're finite length.

(and someone previously wrote)

>>THEN you pass it to the DFT.  that periodically extends whatever the
>>finite data is at that point.  the DFT is not applying the window, but
>>the DFT *does* periodically extend the data.
> 
> Where does it do that?  I suggest it's only in the minds of those who
> like to think of it that way, which seems to be a very useful thing
> for those so inclined.   There is no arithmetic operation in the DFT
> associated with extending the input vector or the basis functions.

OK, lets say it doesn't.  But do note that all the basis functions
are periodic with period equal to the transform length.  The sum
of such functions will also have that period.

Now, note that is NOT the case for DST or DCT, even though the basis 
functions are also periodic in those transforms.  For those, the
basis functions are periodic with period twice the transform length,
and so not necessarily over the transform length.

It wasn't so long that I was wondering why all the interest in DCT,
and then read the description in Numerical Recipes.  I recommend
reading their explanation.

-- glen

>
> but what does that get you? �what possible use is it to truncate the
> basis functions?
>

Robert,


The utility is in the negative. By this mean if you get a chunk of
data like the daily closing price of gold and stick that into a DFT
and then use the DFT's coefs with periodically extended basis
functions to make preditions, your prediction for future gold prices
will likely be very poor. The finite length basis functions are
complete and the inverse DFT will recreate the original data so we
know the DFT didn't leave anything out. The problem lies with what was
not used in the calculation.

The fact that the values outside of the interval take no part in the
DFT's result should be a warning that some other information is needed
before you can just blindly extend the basis functions beyond their
finite interval as used for the analysis and expect good results for
extrapolated functions. Of course there are many examples where the
periodic extension is justified. But not all are justifiable. That's
what I'm saying.

Clay