shift theorem

I don't get it.

Let v be a vector in a n-dimensional Hilbert space V.  Assume {e_1, ...
, e_n} is a basis for V, and {v_1, ... , v_n} be the representation of
v in that basis. Now let D be a unitary map from V to itself, and w :=
D v = {w_1, ... , w_n} be the image of v under D.

Where on earth do you get the idea that anything such as w_k for k not
in {1,2,...,n} should be defined?

Regards,
Andor

Andor wrote:
> I don't get it.
> 
> Let v be a vector in a n-dimensional Hilbert space V.  Assume {e_1, ...
> , e_n} is a basis for V, and {v_1, ... , v_n} be the representation of
> v in that basis. Now let D be a unitary map from V to itself, and w :=
> D v = {w_1, ... , w_n} be the image of v under D.
> 
> Where on earth do you get the idea that anything such as w_k for k not
> in {1,2,...,n} should be defined?
> 
> Regards,
> Andor

Context, please. Who wrote that?

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

robert bristow-johnson wrote:
> 
> in article 424766d4$1_2@127.0.0.1, jim at "N0sp"@m.sjedging@mwt.net wrote on
> 03/27/2005 21:06:
> 
> > robert bristow-johnson wrote:
> >
> >>
> >> in the discussion of interpolation of discrete-time (or discrete-whatever)
> >> sequences, i am willing to entertain a k that is not an integer.  but in
> >> simply the discussion of discrete-time sequences, and particularly with the
> >> DFT, i am not.
> >
> > And that was my point exactly. And no need to go on and on about "n is
> > an integer" that was already agreed.
> 
> "n" is a symbol.  i don't give much of a rat's ass about the symbol.  so, to
> remove it from the discussion, do you agree or not, that in a discrete-time
> sequence, that whatever the stuff that goes in between the little square
> brackets of y[..] is an integer?  if i refer to some discrete-time sequence
> "y[n]", then "n" is an integer.  if we're talking about y[n-k], then n-k is
> an integer.  if n is already restricted to be an integer (for some reason),
> what does that say about k?

Let's revue:} I originally stated that you  would not allow for k (the
shift value) being a non-integer. You stated that yes, you cannot accept
k being a non-integer (in the context of performing a DFT). Hence, we
agree, there's nothing to argue about. 
	The reason I mentioned it was that the periodicity of the DFT is an
artifact of that particular condition which you have assumed. It doesn't
matter how many people share your assumption - It is you (and others)
that have imposed the conditions that results in a DFT with a certain
periodicity. It is not DFT that is making the assumptions.  


> 
> > Now why is it inconceivable to shift the frame of reference for a DFT
> > by some non-integer amount?
> 
> not inconceivable, but for a discrete-time or discrete-frequency sequence,
> there is no definition of a non-integer shift because there is no definition
> of what either y[..] or Y[..] for non-integer indices.
> 
> jim, i'm being very careful to not get sucked into a dispute of
> contradiction that happens here when we're not extremely careful about
> terminology and notation.  if you want to talk about the subject of
> interpolation, fine, but let's call it what it is (a definition of a
> continous-whatever function from discrete-whatever samples).  if you want to
> talk about issues regarding the Discrete-Time Fourier Transform (DCFT),
> fine, but let's call it what it is (not the DFT).
> 
> in the meantime, would you please commit to an answer, without evasion, that
> i asked you from the outset.  here it is again:
> 
> >>
> >>                                       N-1
> >> let     Y[m] =def  DFT{ y[n] }  =def  SUM{ y[n] * exp(-j*2*pi*n*m/N) }
> >>                                       n=0
> >>
> >> then, if it is true that
> >>
> >>         DFT{ y[n-k] }  =  exp(-j*2*pi*k*m/N) * Y[m]
> >>
> >> which (except for a missing "-m" which i presume is a typo of the OP's) is
> >> what the OP postulated, then i ask you, jim, what must y[n] be for  n<0 ,
> >> (which must have *some* definition if k>0) ?  in order for that statement
> >> to be true for an arbitrary y[n] and k and m, what must y[n] be for n<0?
> 

Y[n] represents a series of numbers. Beyond that I don't get what you
are asking. If the question is can we use negative numbers to index the
series I guess the answer is it depends whether we allow the enumeration
of y using negative numbers. If you don't then no we can't.

-jim

----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----

in article DtCdnYnFgqgc8NXfRVn-rg@rcn.net, Jerry Avins at jya@ieee.org wrote
on 03/28/2005 15:47:

> Andor wrote:

>> I don't get it.
>> 
>> Let v be a vector in a n-dimensional Hilbert space V.  Assume {e_1, ...
>> , e_n} is a basis for V, and {v_1, ... , v_n} be the representation of
>> v in that basis. Now let D be a unitary map from V to itself, and w :=
>> D v = {w_1, ... , w_n} be the image of v under D.
>> 
>> Where on earth do you get the idea that anything such as w_k for k not
>> in {1,2,...,n} should be defined?
...
> 
> Context, please. Who wrote that?

it's an interpretation (a valid one, IMO) of what Jim is saying.  i'm gonna
change the semantics back to the most conventional in the DSP lit (which
also changes the symbols slightly from porterboy76@yahoo.com, th OP):


DFT:
                                        N-1
     DFT{ x[n] }  =def   X[k]  =def     SUM{ x[n] * exp(-j*2*pi*n*k/N) }
                                        n=0


iDFT:
                                        N-1
    iDFT{ X[k] }  =def   x[n]  =  1/N * SUM{ X[k] * exp(+j*2*pi*n*k/N) }
                                        k=0


" =def " means "equal by definition" or "defined as" or whatever it is they
mean with 3 horizontal lines or a little triangle above the = sign.  the
last equal sign is not a definition, it is a result.  if you define X[k] in
terms of x[n] the way it is above, then you are not free to define x[n] in
terms of X[k], you have to solve for it.

now, after correcting a little mistake and fixing symbols, the OP said that

         DFT{ x[n-d] }  =  exp(-j*2*pi*k*d/N) * X[k]

where it is implied that x[n] and X[k] are defined and related as per above.
the OP then qualified this by saying (with substitution of symbols) "This
assumes that x[n] is periodic."  and i said "such an assumption should be
implicit with DFT, although there are deniers" which i know brings us back
to an old and recurring debate here about whether or not the DFT inherently
periodically extends the data passed to it, of which it is likely commonly
known that i am a proponent of such (and also claim that it is a
non-controversial position of DSP textbooks such as Oppenheim & Schafer).

people might remember that Bob Cain and Adrian Hey took exception to this
(ca. August 2002) and we had a big tiff about it.  Rick Lyons (Sep 24 2004)
seems to take the same position (" ... leads to confusion.  It causes smart
people to make the incorrect comment of: 'The DFT assumes that its input
sequence is periodic' ") and Jim (May 19 2004) calls it "brain dead dogma".
so that, Jerry, is the context.

now in saying that

         DFT{ x[n-d] }  =  exp(-j*2*pi*k*d/N) * X[k]

then x[n] has to have *some* definition for n<0 if d is greater than 0
because the argument of x[m] (m = n-d) going into the DFT is not in the
range of 0 <= m < N, and i am asking Jim what x[m] must be for m equal to,
say, -1 or -2 (if d is as big as 2), for the above statement to be true.  as
you can see in his latest post, he's still not answering the question.

so i'll answer it:  for 0 < d < N, x[n-d] must be the same as x[n-d+N] which
is defined from the original x[n] since 0 <= n-d+N < N.  what this, plus the
convolution theorem and moreover the very *definition* of the DFT (and the
iDFT), is that the N values of x[n] (or X[k]) are taken as N contiguous
samples of a periodic sequence (which i would still just call "x[n]") of
period N and transforms that to another periodic sequence of period N (which
is X[k]).  the iDFT takes N contiguous samples of a periodic sequence (X[k])
of period N and transforms that to another periodic sequence of period N
(which is x[n]).  it has a few useful properties, NONE of which are violated
by the periodic extension of either x[n] and X[k] and SOME of which (the
shifting and convolution properties) _require_ the periodic extension of
x[n] or X[k].  so i am at a loss as to why the inherent nature of the DFT to
"assume" (if Rick allows me to anthropomorphize a bit) that the N samples
supplied to it are N contiguous samples of a periodic sequence of period
equal to N.

Jim is trying to distract the issue to dealing with "d" being a non-integer.
if d is a non-integer and "n" *is* an integer, then n-d is not an integer,
and, from the perspective of the DFT x[n-d] is not defined.  so Jim asks (i
think) "what does multiplication of exp(-j*2*pi*k*d/N) to X[k] do to the
result of an iDFT when d is not an integer?"  and i don't have a good answer
for the DFT (because it doesn't make sense for the DFT as x[n-d] is not
defined), but i could come up with an answer regarding the DTFT.  but when
you convert that back to samples, there are assumptions that need to be made
to have an unambiguous inverse DTFT conversion to back to some x[n].  that
is why i'm dancing around his question until he can frame it in language
that has clear meaning.  then we can get answers and mathematical certainty
and maybe stop arguing about this.


-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

in article 42489e70$1_2@127.0.0.1, jim at "N0sp"@m.sjedging@mwt.net wrote on
03/28/2005 19:16:


> The reason I mentioned it was that the periodicity of the DFT is an
> artifact of that particular condition which you have assumed.

what particular condition is that?  and don't say "periodicity" because that
will make a portion of your statement a tautology, which is true, i guess,
but it doesn't really say anything and i don't wanna argue over a tautology.
if is true (and a tautology) that an artifact of periodicity results from a
condition of periodicity.

but i am saying that the periodicity of the DFT:

1.  results from the very definitions of the DFT and inverse DFT

and

2.  is a required condition for the shifting theorem and convolution
    theorem to work correctly

and

3.  does not violate any other theorem or property of the DFT and iDFT.


to be clear, i am saying that the N input samples into the DFT are taken as
N contiguous samples of a periodic sequence of period N and the DFT maps
that periodic sequence x[n] to another periodic sequence X[k] of the same
period N (and the iDFT maps it back essentially the same way).  if those N
samples came from another sequence that was possibly not periodic the DFT
neither knows or cares about that (sorry, i have to anthropomorphize, i
cannot think of a better way to say it).  the DFT takes your N numbers and
periodically extends it to a periodic sequence of period N.  yanking those N
numbers out of some other sequence is an action of windowing, and any
artifact resulting from that is to be blamed on the windowing, not the DFT.

> It doesn't matter how many people share your assumption -

i agree (except that it's not an assumption).  it is true because of
mathematical justification, not because of any popularity or lack thereof.
now i *will* say, that in some other circles (such as any O&S, Papoulis, and
any other text that i have read that deals with this rigorously) this
concept of the inherent periodic extension of x[n] that is done by the DFT
is non-controversial.  that is when i'll appeal to what someone else says,
but i am comfortable supporting this with proof of mathematics and will not
appeal to any "proof" by association of authority.

> It is you (and others) that have imposed the conditions that results in
> a DFT with a certain periodicity.

and, pray tell, what conditions are those, that i (or "others") have
imposed?  what assumptions do you claim we make that results in the DFT
periodically extending its input?

>It is not DFT that is making the assumptions.
> 
> 
>> 
>>> Now why is it inconceivable to shift the frame of reference for a DFT
>>> by some non-integer amount?
>> 
>> not inconceivable, but for a discrete-time or discrete-frequency sequence,
>> there is no definition of a non-integer shift because there is no definition
>> of what either y[..] or Y[..] for non-integer indices.
>> 
>> jim, i'm being very careful to not get sucked into a dispute of
>> contradiction that happens here when we're not extremely careful about
>> terminology and notation.  if you want to talk about the subject of
>> interpolation, fine, but let's call it what it is (a definition of a
>> continous-whatever function from discrete-whatever samples).  if you want to
>> talk about issues regarding the Discrete-Time Fourier Transform (DCFT),
>> fine, but let's call it what it is (not the DFT).
>> 
>> in the meantime, would you please commit to an answer, without evasion, that
>> i asked you from the outset.  here it is again:
>> 
>>>> 
>>>>                                       N-1
>>>> let     Y[m] =def  DFT{ y[n] }  =def  SUM{ y[n] * exp(-j*2*pi*n*m/N) }
>>>>                                       n=0
>>>> 
>>>> then, if it is true that
>>>> 
>>>>         DFT{ y[n-k] }  =  exp(-j*2*pi*k*m/N) * Y[m]
>>>> 
>>>> which (except for a missing "-m" which i presume is a typo of the OP's) is
>>>> what the OP postulated, then i ask you, jim, what must y[n] be for  n<0 ,
>>>> (which must have *some* definition if k>0) ?  in order for that statement
>>>> to be true for an arbitrary y[n] and k and m, what must y[n] be for n<0?
>> 
> 
> Y[n] represents a series of numbers.

i think you meant a small "y".  no?  (that's the 'y' i'm talking about.)

> Beyond that I don't get what you are asking.

the answer is below and in my previous post.

> If the question is can we use negative numbers to index the
> series I guess the answer is it depends whether we allow the enumeration
> of y using negative numbers. If you don't then no we can't.

i'm saying we have to.  we MUST define y[n-k] for the cases where n-k < 0 or
n-k >= N  to make the shifting theorem have definition and have the result
stated above.

if, by definition,        DFT{ y[n] }    =  Y[m]

then                      DFT{ y[n-k] }  =  exp(-j*2*pi*k*m/N) * Y[m]

is ONLY true for arbitrary y[n] (originally defined for 0 <= n < N), and
arbitrary integer m and k, IF y[n+N] = y[n] for all n.  i am making no
assumption about that.  it is a fact or a theorem that is proved.

now it *is* my observation that this fact, in addition to the convolution
theorem and the very definitions of the DFT and iDFT, mean that the DFT (and
iDFT) periodically extends the data that is passed to it.  and that is not
only my observation which is why i do not understand its controversy in the
present context.

-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

Robert,
	You have no idea how mind-numbingly stupid your position is. My
contention is that the definitions are what produce the periodic result
in the DFT. Your response is to spew chapter and verse citing all the
definitions and proving the periodic nature of the DFT. That's Dogma -
when you are completely oblivious to the fact that different choices
could have been made when things were defined. It's as if you believe
these definitions were handed down by God almighty on tablets of stone. 
	And no I'm not suggesting that the definitions be changed, that was not
my point. So don't worry I'm not pulling at the pillars - the Temple is
not going to collapse. My point was that all the assumptions have been
made by humans - the DFT is not making any of the assumptions.

-jim 
	 

robert bristow-johnson wrote:
> 
> in article DtCdnYnFgqgc8NXfRVn-rg@rcn.net, Jerry Avins at jya@ieee.org wrote
> on 03/28/2005 15:47:
> 
> > Andor wrote:
> 
> >> I don't get it.
> >>
> >> Let v be a vector in a n-dimensional Hilbert space V.  Assume {e_1, ...
> >> , e_n} is a basis for V, and {v_1, ... , v_n} be the representation of
> >> v in that basis. Now let D be a unitary map from V to itself, and w :=
> >> D v = {w_1, ... , w_n} be the image of v under D.
> >>
> >> Where on earth do you get the idea that anything such as w_k for k not
> >> in {1,2,...,n} should be defined?
> ...
> >
> > Context, please. Who wrote that?
> 
> it's an interpretation (a valid one, IMO) of what Jim is saying.  i'm gonna
> change the semantics back to the most conventional in the DSP lit (which
> also changes the symbols slightly from porterboy76@yahoo.com, th OP):
> 
> DFT:
>                                         N-1
>      DFT{ x[n] }  =def   X[k]  =def     SUM{ x[n] * exp(-j*2*pi*n*k/N) }
>                                         n=0
> 
> iDFT:
>                                         N-1
>     iDFT{ X[k] }  =def   x[n]  =  1/N * SUM{ X[k] * exp(+j*2*pi*n*k/N) }
>                                         k=0
> 
> " =def " means "equal by definition" or "defined as" or whatever it is they
> mean with 3 horizontal lines or a little triangle above the = sign.  the
> last equal sign is not a definition, it is a result.  if you define X[k] in
> terms of x[n] the way it is above, then you are not free to define x[n] in
> terms of X[k], you have to solve for it.
> 
> now, after correcting a little mistake and fixing symbols, the OP said that
> 
>          DFT{ x[n-d] }  =  exp(-j*2*pi*k*d/N) * X[k]
> 
> where it is implied that x[n] and X[k] are defined and related as per above.
> the OP then qualified this by saying (with substitution of symbols) "This
> assumes that x[n] is periodic."  and i said "such an assumption should be
> implicit with DFT, although there are deniers" which i know brings us back
> to an old and recurring debate here about whether or not the DFT inherently
> periodically extends the data passed to it, of which it is likely commonly
> known that i am a proponent of such (and also claim that it is a
> non-controversial position of DSP textbooks such as Oppenheim & Schafer).
> 
> people might remember that Bob Cain and Adrian Hey took exception to this
> (ca. August 2002) and we had a big tiff about it.  Rick Lyons (Sep 24 2004)
> seems to take the same position (" ... leads to confusion.  It causes smart
> people to make the incorrect comment of: 'The DFT assumes that its input
> sequence is periodic' ") and Jim (May 19 2004) calls it "brain dead dogma".
> so that, Jerry, is the context.
> 
> now in saying that
> 
>          DFT{ x[n-d] }  =  exp(-j*2*pi*k*d/N) * X[k]
> 
> then x[n] has to have *some* definition for n<0 if d is greater than 0
> because the argument of x[m] (m = n-d) going into the DFT is not in the
> range of 0 <= m < N, and i am asking Jim what x[m] must be for m equal to,
> say, -1 or -2 (if d is as big as 2), for the above statement to be true.  as
> you can see in his latest post, he's still not answering the question.
> 
> so i'll answer it:  for 0 < d < N, x[n-d] must be the same as x[n-d+N] which
> is defined from the original x[n] since 0 <= n-d+N < N.  what this, plus the
> convolution theorem and moreover the very *definition* of the DFT (and the
> iDFT), is that the N values of x[n] (or X[k]) are taken as N contiguous
> samples of a periodic sequence (which i would still just call "x[n]") of
> period N and transforms that to another periodic sequence of period N (which
> is X[k]).  the iDFT takes N contiguous samples of a periodic sequence (X[k])
> of period N and transforms that to another periodic sequence of period N
> (which is x[n]).  it has a few useful properties, NONE of which are violated
> by the periodic extension of either x[n] and X[k] and SOME of which (the
> shifting and convolution properties) _require_ the periodic extension of
> x[n] or X[k].  so i am at a loss as to why the inherent nature of the DFT to
> "assume" (if Rick allows me to anthropomorphize a bit) that the N samples
> supplied to it are N contiguous samples of a periodic sequence of period
> equal to N.
> 
> Jim is trying to distract the issue to dealing with "d" being a non-integer.
> if d is a non-integer and "n" *is* an integer, then n-d is not an integer,
> and, from the perspective of the DFT x[n-d] is not defined.  so Jim asks (i
> think) "what does multiplication of exp(-j*2*pi*k*d/N) to X[k] do to the
> result of an iDFT when d is not an integer?"  and i don't have a good answer
> for the DFT (because it doesn't make sense for the DFT as x[n-d] is not
> defined), but i could come up with an answer regarding the DTFT.  but when
> you convert that back to samples, there are assumptions that need to be made
> to have an unambiguous inverse DTFT conversion to back to some x[n].  that
> is why i'm dancing around his question until he can frame it in language
> that has clear meaning.  then we can get answers and mathematical certainty
> and maybe stop arguing about this.
> 
> --
> 
> r b-j                  rbj@audioimagination.com
> 
> "Imagination is more important than knowledge."

----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----

robert bristow-johnson wrote:
> 
> in article 42489e70$1_2@127.0.0.1, jim at "N0sp"@m.sjedging@mwt.net wrote on
> 03/28/2005 19:16:
> 
> > The reason I mentioned it was that the periodicity of the DFT is an
> > artifact of that particular condition which you have assumed.
> 
> what particular condition is that?  and don't say "periodicity" because that
> will make a portion of your statement a tautology, which is true, i guess,
> but it doesn't really say anything and i don't wanna argue over a tautology.
> if is true (and a tautology) that an artifact of periodicity results from a
> condition of periodicity.
> 
> but i am saying that the periodicity of the DFT:
> 
> 1.  results from the very definitions of the DFT and inverse DFT
> 
> and
> 

I know that's what you are saying - that is what I have been saying you
are saying.

-jim

----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----

robert bristow-johnson wrote:

> people might remember that Bob Cain and Adrian Hey took exception to this
> (ca. August 2002) and we had a big tiff about it.  

Aw, Robert, I wouldn't call it a tiff.  Rather, I'd call it 
a civilized and hard fought argument (that we each think we 
won) which brought to light a good deal about the DFT in the 
process.  Usefull if inconclusive.

Looks like bigger guns than I are making the same points but 
with much better formality so I'll just be watching this 
one.  :-)


Peace,

Bob
-- 

"Things should be described as simply as possible, but no 
simpler."

                                              A. Einstein

robert bristow-johnson wrote:
> > Andor wrote:
> >> Let v be a vector in a n-dimensional Hilbert space V.  Assume
{e_1, ...
> >> , e_n} is a basis for V, and {v_1, ... , v_n} be the
representation of
> >> v in that basis. Now let D be a unitary map from V to itself, and
w :=
> >> D v = {w_1, ... , w_n} be the image of v under D.
> >>
> >> Where on earth do you get the idea that anything such as w_k for k
not
> >> in {1,2,...,n} should be defined?

...

> it's an interpretation (a valid one, IMO) of what Jim is saying.

[snipping DFT formalisms]

Ah robert, to be honest, I'm at issue with both of your points. Jim
mentioned non-integer indeces, and you mention negative indeces. If you
take the linear algebra view (after all, the DFT is just another
unitary transform, as I wrote above), then a vector has indeces ranging
from 1 to n (or 0 to n-1 :-), all other indeces are not applicable.

One very nice property of the DFT is that it diagonlizes the shift
operator (which cyclically rotates the elements in a vector) --- no
periodic sequences are required to state the shift theorem.

However, a periodic extension of a vector into an infinite sequence
holds exactly the same information as the view of cyclically rotating
its elements, therefore it is a valid view, albeit one that requires
introducing new objects (infinitely long periodic sequences) which are
not ammenable to linear algebra, in contrast to introducing the shift
operator. I prefer to work with vectors in a vector space. It seems you
prefer periodic sequences. It doesn't matter.

Regards,
Andor

jim wrote:

>
> I know that's what you are saying - that is what I have been saying
> you are saying.
> 

Say what?

Ciao,

Peter K.