Re: Strange Discrete Fourier Transform question

Fred Marshall wrote:
<robert.w.adams@xxxxxxxxxxx> wrote in message news:1154260055.670375.100450@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

Suppose that I have a finite-length discrete-time signal that is not
necessarily sampled on a uniform time grid. I will characterize this
signal as a series of time-amplitude pairs with time = t_sub_k and
amplitude = a_sub_k, where k is an integer from 1 to N that selects a
particular time-amplitude pair.

It is easy to take the DFT of this sequence even though the time grid
may not be uniform.

FT(w) = SUM k=1 to N (a_sub_k*exp(-j*w*t_sub_k))


(snip)

You said a DFT was easy as:

FT(w) = SUM k=1 to N (a_sub_k*exp(-j*w*t_sub_k))

where the values of t_sub_k are apparently ordered but arbitrary.
I note that "w" isn't in any way discrete - ????

So, I think this isn't a DFT as we know it.

Start with a DFT definition with
N the number of samples
T the temporal epoch,
fs the sampling frequency
T/N = 1/fs the temporal sample interval
1/T = fs/N the frequency sample interval

And the DFT is:

F(n*fs/N) = sum k=1 to N a_sub_k*exp[-j*(nfs/N)*(kT/N)] ;n=0,N-1

Well, it would have been easier if it was stated that the samples
were of a periodic function. My claim for a finite duration
series is that it can be assumed periodic with a period greater
than or equal to the duration without loss of information.

If one considers a Fourier integral with delta functions at
the appropriate points, it seems to make some sense to me.

It transforms N sample values into N frequency values.
The question, then, is does the inverse transform, the sum
of the frequency components evaluated at the original positions,
give the original signal? (see below)

If you want to have arbitrary values of "w" then you have a continuous Fourier Transform of a discrete sequence:

F(w) = sum k=1 to N a_sub_k*exp(-j*w*kT/N) which almost looks like what you have above.

It's not discrete in frequency. Just to be clear. I don't see how that's "easy" to do using arrays of numbers in a computer - which seems to be where you're heading with this.

Then, if you want to make the sample times arbitrary then you would have what we started with:

F(w) = sum k=1 to N a_sub_k*exp(-j*w*t_sub_k)

It's still not discrete in frequency - which is what you need to get a finite sequence.

So, it's common to assume that the temporal sequence is periodic on T and the sum generating the transform is finite: If this is done you get something like:

F(n*fs/N) = sum k=1 to N a_sub_k*exp[-j*(nfs/N)*t_sub_k] ;n=0,N-1 !!!

The problem with this formulation is that the temporal resolution hasn't been defined on a regular grid and that's necessary for the Fourier Transform to be periodic instead of just infinite. If it's infinite then this formulation can't be inverse transformed because it's incomplete - not all the information is there.

I am not convinced.

If I have N samples amplitudes taken at N times, I want the N frequency
components such that when evaluated at the original N times I get the
original N amplitudes. I am not sure yet that the OP's transform does
that, and so far I think it doesn't.

It is possible, though unlikely, that the transform is singular, such
that it can't be inverted. It is more likely to be ill-conditioned,
which will happen if too many data points are too close together.
If the transform isn't singular then there is enough data.
The aliasing rules aren't simple, though. You can have any N frequencies, not necessarily the first N harmonics (starting
from zero).

The nice thing about the Fourier series is that orthogonality makes
the inverse easy. Without orthogonality one must compute the
inverse of the transform matrix.

Another "problem" to ponder here is that the times aren't (i.e. need not be) ordered - although in a Fourier Transform they are ordered. That must have some bearing, eh?

I don't think that matters much. It is just like exchanging rows or columns of a matrix which, if done right, doesn't affect the answer.
Consider and N equations and N unknowns problem. The answer doesn't
depend on the order I write the equations down.

-- glen

.

Relevant Pages

  • Re: Uncertainty principle, fourier transform
    ... different" orthonormal basis, in the sense that the norm of the inner ... The Fourier transform might be used to ... Fourier transform are intimately connected. ... the position/momentum uncertainty relation, via preservation of this ...
    (sci.physics)
  • Re: Uncertainty principle, fourier transform
    ... product of every pair of original and transformed basis vectors is the same. ... A discrete Fourier transform matrix is an orthonormal matrix all of whose ... uncertainty relation. ...
    (sci.physics)
  • Re: fourier transform of sin x / x
    ... solve the inverse Fourier transform of a rectangular ... Integrating over w ...
    (sci.math)
  • Re: Uncertainty principle, fourier transform
    ... product of every pair of original and transformed basis vectors is the same. ... A discrete Fourier transform matrix is an orthonormal matrix all of whose ...
    (sci.physics)
  • Re: Strange Discrete Fourier Transform question
    ... necessarily sampled on a uniform time grid. ... The question, then, is does the inverse transform, the sum ... Transform to be periodic instead of just infinite. ... be) ordered - although in a Fourier Transform they are ordered. ...
    (comp.dsp)