FFT--stretching time-domain data

Hello--

I'm reading a paper by Press and Rybicki on a "Fast Alhgorithm for
Spectral Analysis of Unevenly Sampled Data," found in The Astrophysical
Journal, 338: 277-280. Essentially what is being described in this
paper is an algorithm involving the FFT which is used to calculate the
Lomb-Scargle periodogram.

In one section of the paper, the authors make the following comment:

"A nice way to get transform values at frequencies 2*omega instead of
omega is to stretch the time-domain data by a factor of 2, and then wrap
it to double-cover the original length. (This trick goes back to Tukey.)"


What is really happening here? Am I to simply pad the dataset until I
get 2*N, or is there another way to stretch the time-domain data?

Thank you!

On Sep 4, 4:48*pm, Nicholas Kinar <n.ki...@usask.ca> wrote:
> Hello--
>
> I'm reading a paper by Press and Rybicki on a "Fast Alhgorithm for
> Spectral Analysis of Unevenly Sampled Data," found in The Astrophysical
> Journal, 338: 277-280. *Essentially what is being described in this
> paper is an algorithm involving the FFT which is used to calculate the
> Lomb-Scargle periodogram.
>
> In one section of the paper, the authors make the following comment:
>
> "A nice way to get transform values at frequencies 2*omega instead of
> omega is to stretch the time-domain data by a factor of 2, and then wrap
> it to double-cover the original length. (This trick goes back to Tukey.)"
>
> What is really happening here? *Am I to simply pad the dataset until I
> get 2*N, or is there another way to stretch the time-domain data?
>
> Thank you!

I don't fully understand this description.
Is it to suggest that you take x[n], say of length N, and then
making y[2n] = x[n], now of length 2N, but to then compute
the N-point DFT of y[n]? Is that what stretching means?

Or maybe you can explain the final result that you want.
x[n] <--> X[k] via the DFT. Now what do you want to change
from X[k]?

julius wrote:

> Is it to suggest that you take x[n], say of length N, and then
> making y[2n] = x[n], now of length 2N, but to then compute
> the N-point DFT of y[n]? Is that what stretching means?
>

This seems to be the most logical answer to what is being implied.
However, I'm not completely certain.

> Or maybe you can explain the final result that you want.
> x[n] <--> X[k] via the DFT. Now what do you want to change
> from X[k]?

The processing procedure given in the paper is to:

(1) Fill a vector A with ones. This would be an m x n identity matrix.

(2) Take the FFT of the vector to be able to calculate sum(
sin[2*omega*t_j]) and sum(cos[2*omega*t_j])

The authors say:

"A nice way to get transform values at frequencies 2*omega instead of
omega is to stretch the time-domain data by a factor of 2, and then wrap
it to double-cover the original length. (This trick goes back to Tukey.)
In the program, this appears as a modulo function."

The calculation of sum(sin[2*omega*t_j]) and sum(cos[2*omega*t_j]) is
said to be done "with some manipulation."

Are we looking at something involving the synthesis equations?

Thanks for your response, Julius.

Nicholas

On Sep 5, 10:46*am, Nicholas Kinar <n.ki...@usask.ca> wrote:
>
> This seems to be the most logical answer to what is being implied.
> However, I'm not completely certain.

Man, this is confusing :-). Why don't you think of what *you*
want to compute instead of what the paper is suggesting? :-)

> The processing procedure given in the paper is to:
>
> (1) Fill a vector A with ones. *This would be an m x n identity matrix.

A vector is an mxn identity matrix??

> (2) Take the FFT of the vector to be able to calculate sum(
> sin[2*omega*t_j]) and sum(cos[2*omega*t_j])
>
> The authors say:
>
> "A nice way to get transform values at frequencies 2*omega instead of
> omega is to stretch the time-domain data by a factor of 2, and then wrap
> it to double-cover the original length. (This trick goes back to Tukey.)
> * In the program, this appears as a modulo function."
>
> The calculation of sum(sin[2*omega*t_j]) and sum(cos[2*omega*t_j]) is
> said to be done "with some manipulation."
>
> Are we looking at something involving the synthesis equations?

Sounds to me that they are playing around with DFT identities.

Let's say that the original transform pair is:

x[n] <--> X[k], both vectors of length N

Then if I understand correctly, they say,

y[2n] = x[n], now y[n] is of length 2N

But then compute the N-point DFT of y[n], or in other words,
the N-point DFT of z[n] where:

z[n] = y[n] + y[n+N], and z[n] is of length N.

Does that help or should we continue to the derivation of
how Z[k] relates to X[k]?

Thanks again for your response, Julius!

>
> Man, this is confusing :-). Why don't you think of what *you*
> want to compute instead of what the paper is suggesting? :-)
>

I'm trying to plug the Lomb-Scargle periodogram into some of my own
research, which requires spectral analysis of unevenly sampled data.
I'm starting with the Lomb-Scargle periodogram.


> A vector is an mxn identity matrix??

When m = 1 or n = 1. Sorry, my typing mistake. What was I thinking ?!?


> Sounds to me that they are playing around with DFT identities.
>


> z[n] = y[n] + y[n+N], and z[n] is of length N.
>
> Does that help or should we continue to the derivation of
> how Z[k] relates to X[k]?

Should be linear, so Z[n] = Y[n] + Y[n+N]

So if I have some numbers in the time domain, what is happening here?
Suppose that I have a sequence x[n] = {3.5, 6.3, 9.9, 2.2, 3.4, 5.6,
3.4, 7.6}.

Do I simply place two of these sequences one after each other, and this
forms y[n]? So how do I construct y[n]?

> Do I simply place two of these sequences one after each other, and this
> forms y[n]? So how do I construct y[n]?
>

Wouldn't this simply be

Y[2N] = X[n] + X[n]

in the frequency domain?

On Sep 8, 1:24 pm, Nicholas Kinar <n.ki...@usask.ca> wrote:
> Thanks again for your response, Julius!
>
>
>
> > Man, this is confusing :-). Why don't you think of what *you*
> > want to compute instead of what the paper is suggesting? :-)
>
> I'm trying to plug the Lomb-Scargle periodogram into some of my own
> research, which requires spectral analysis of unevenly sampled data.
> I'm starting with the Lomb-Scargle periodogram.
[snip]

So I have no idea what a Lomb-Scargle periodogram is, I suspect
it's known by another name in mainstream DSP, but I googled
for it and found this MATLAB script:

http://www.mathworks.com/matlabcentr...bjectType=FILE

Does that help?

Julius

julius wrote:

> So I have no idea what a Lomb-Scargle periodogram is, I suspect
> it's known by another name in mainstream DSP, but I googled
> for it and found this MATLAB script:
>
> http://www.mathworks.com/matlabcentr...bjectType=FILE
>
> Does that help?
>
> Julius


Thanks for your help, Julius. This is greatly appreciated! There
probably is another name for the Lomb-Scargle in mainstream DSP, but I
do know that it originated in astronomy for analyzing unevenly-sampled
(non-continuous) datasets. DSP often has the advantage of evenly-spaced
datasets because signals are sampled with an ADC or some other type of
automatic method.

Thanks again, Julius! I'll take a look at the Matlab script, which will
help to provide insight into the implementation.

Nicholas