Question on how to use FINUFFT with a real-time data stream

[journeytosilius]

Hi, I have been redirected to this interesting project because I had a question that I could not resolve:

I can not FFT a non-uniform, real-time data stream. I mean, I can, but I can't extract frequency and magnitude on a meaningful way.

In my experiment I simply create a vector buffer that is filled with real-time data, and set a max size so to create a sequence, then as the data comes in I fill it and remove first position when it reaches it max capacity value, so it always maintains its max size and keeps on being filled with new data.

int M = 1e7;                                   // number of nonuniform points
vector<double> x(M);
vector<complex<double> > c(M);
complex<double> I = complex<double>(0.0,1.0);  // the imaginary unit

I assume M is the actual size of the buffer in my case ?

What is c exactly ?

What is the imaginary unit used for in this case ? Is it the missing "sampling" unit ?

int N = 1e6;                                   // number of output modes
vector<complex<double> > F(N);

How do I know the number of output nodes I want ?

Thank you very much

[ahbarnett]

Dear chromafunk. I think you need to read up on the formulae in the FFT and NUFFT (eg our docs) before you can proceed. To meaningfully get the spectrum of nonuniformly sampled data at times t_j you will need some quadrature weights w_j., and then perform a nufft1d1 with the c vector being your data (call it y_j) elementwise product with the w_j. As a crude choice the wj could just be the mean sample spacing (t{j+1} t{j-1})/2. You will also want to window, as with the usual FFT, to remove artifacts due to nonperiodicity. The number of output modes N is up to you, but shouldn't be larger than about reciprocal of your max spacing. I can write a tutorial about this if you request it. Best, Alex

On Mon, Oct 11, 2021 at 11:05 AM chromafunk @.***> wrote:

Hi, I have been redirected to this interesting project because I had a question that I could not resolve:

I can not FFT a non-uniform, real-time data stream. I mean, I can, but I can't extract frequency and magnitude on a meaningful way.

In my experiment I simply create a vector buffer that is filled with real-time data, and set a max size so to create a sequence, then as the data comes in I fill it and remove first position when it reaches it max capacity value, so it always maintains its max size.

int M = 1e7; // number of nonuniform points vector x(M); vector<complex > c(M); complex I = complex(0.0,1.0); // the imaginary unit

I assume M is the actual size of the buffer in my case ?

What is c exactly ?

What is the imaginary unit used for in this case ? Is it the missing "sampling" unit ?

int N = 1e6; // number of output modes vector<complex > F(N);

How do I know the number of output nodes I want ?

Thank you very much

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/flatironinstitute/finufft/issues/197, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACNZRST7YOULCI2AS47K5D3UGL4L7ANCNFSM5FYOPFUA . Triage notifications on the go with GitHub Mobile for iOS https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675 or Android https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub.

-- *---------------------------------------------------------------------~^`^~._.~' |\ Alex H. Barnett Center for Computational Mathematics, Flatiron Institute | \ http://users.flatironinstitute.org/~ahb 646-876-5942

[ahbarnett]

Eg, "imaginary unit" means i = sqrt(-1), just as in the FFT, etc.

On Mon, Oct 11, 2021 at 12:09 PM Alex Barnett < @.***> wrote:

Dear chromafunk. I think you need to read up on the formulae in the FFT and NUFFT (eg our docs) before you can proceed. To meaningfully get the spectrum of nonuniformly sampled data at times t_j you will need some quadrature weights w_j., and then perform a nufft1d1 with the c vector being your data (call it y_j) elementwise product with the w_j. As a crude choice the wj could just be the mean sample spacing (t{j+1} t{j-1})/2. You will also want to window, as with the usual FFT, to remove artifacts due to nonperiodicity. The number of output modes N is up to you, but shouldn't be larger than about reciprocal of your max spacing. I can write a tutorial about this if you request it. Best, Alex

On Mon, Oct 11, 2021 at 11:05 AM chromafunk @.***> wrote:

Hi, I have been redirected to this interesting project because I had a question that I could not resolve:

I can not FFT a non-uniform, real-time data stream. I mean, I can, but I can't extract frequency and magnitude on a meaningful way.

In my experiment I simply create a vector buffer that is filled with real-time data, and set a max size so to create a sequence, then as the data comes in I fill it and remove first position when it reaches it max capacity value, so it always maintains its max size.

int M = 1e7; // number of nonuniform points vector x(M); vector<complex > c(M); complex I = complex(0.0,1.0); // the imaginary unit

I assume M is the actual size of the buffer in my case ?

What is c exactly ?

What is the imaginary unit used for in this case ? Is it the missing "sampling" unit ?

int N = 1e6; // number of output modes vector<complex > F(N);

How do I know the number of output nodes I want ?

Thank you very much

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/flatironinstitute/finufft/issues/197, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACNZRST7YOULCI2AS47K5D3UGL4L7ANCNFSM5FYOPFUA . Triage notifications on the go with GitHub Mobile for iOS https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675 or Android https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub.

--

*---------------------------------------------------------------------~^`^~._.~' |\ Alex H. Barnett Center for Computational Mathematics, Flatiron Institute | \ http://users.flatironinstitute.org/~ahb 646-876-5942

-- *---------------------------------------------------------------------~^`^~._.~' |\ Alex H. Barnett Center for Computational Mathematics, Flatiron Institute | \ http://users.flatironinstitute.org/~ahb 646-876-5942

[journeytosilius]

Hi Alex, thank you for responding so quick. I kind of understand it better now, at least enough to try and make some tests by myself. But it would really be amazing if you could put up a quick tutorial / example for this use case. The main problem comes at interpreting the values set to work with the program-generated data on the examples. Since most of the FFT material online is based on basically pre-recorded audio files, it can be a little tedious to understand these other examples for someone who wants to experiment with this type of algorithm coming from a non-math background. Thank you very much

[ahbarnett]

Hi - it woudl really be useful to know "how nonuniform" your sample spacing is. Are there large gaps t_{j+1} - t_j, or is only slightly nonuniform? Best, ALex

On Mon, Oct 11, 2021 at 1:10 PM chromafunk @.***> wrote:

Hi Alex, thank you for responding so quick. I kind of understand it better now, at least enough to try and make some tests by myself. But it would really be amazing if you could put up a quick tutorial / example for this use case. The main problem comes at interpreting the values set to work with the program-generated data on the examples. Since most of the FFT material online is based on basically pre-recorded audio files, it can be a little tedious to understand these other examples for someone who wants to experiment with this type of algorithm coming from a non-math background. Thank you very much

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/flatironinstitute/finufft/issues/197#issuecomment-940205498, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACNZRSTPKTK43TMPSKKA5J3UGMK77ANCNFSM5FYOPFUA . Triage notifications on the go with GitHub Mobile for iOS https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675 or Android https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub.

-- *---------------------------------------------------------------------~^`^~._.~' |\ Alex H. Barnett Center for Computational Mathematics, Flatiron Institute | \ http://users.flatironinstitute.org/~ahb 646-876-5942

[journeytosilius]

Hi Alex, it's normally slightly non-uniform. When an event happens on the server, data is sent to the client and it's a "living" system so there are events continuously. Sometimes the frequency is higher, sometimes lower. It fluctuates and that's why I'm interested on measuring it :)

[carlos-pereyra]

@ahbarnett

nonuniformly sampled data at times t_j you will need some quadrature

Did you have a chance to write this example? I am working with non-uniform time-series data that does have fairly large gaps, the signal is a set of N real points.

I am curious about defining the weighted quadrature points for such an instance mentioned above. First I am testing the Type-1 algorithm, which seems to only deal with discrete frequency modes, but do the concentrations c_j need to be determined with quadrature before the nufft1d1 operation?

Thanks again!

Edit: I think I figured this one out. Type 1, doesn't require quadrature weights. Here's a modified look at the simple1d1.py example except rather than deal with a noisy signal, I wanted to verify the result by looking at a single input frequency. The following will generate a spectra with a singular peak corresponding to omega_0.

# input nonuniform points
x = 2 * np.pi * np.random.uniform(size=M)
x = np.sort(x)

# test signa
omega0=100.0
s = np.sin(omega0*x)
c = (s + 1J * 0)

...
f = finufft.nufft1d1(x, c, N, eps=1e-9)

...
# calculate the fourier modes (frequency)
modes=np.zeros([N], dtype=np.int32)
if N%2:
    # odd
    modes=np.arange(-(N-1)/2.,(N-1)/2)
else:
    # even
    modes=np.arange(-N/2.,N/2)

plot(modes, np.abs(f))

if the full example is requested, I can send it as a gist or pr or whatevers

[k-a-mendoza]

I'd be interested in a writeup on how to get frequency bin centers. I'm not quite sure how to apply the math to my own data to get frequency bin centers. @carlos-pereyra

[ahbarnett]

Hi Kevin, not sure what you mean. You need to supply the time and frequency grid points (either uniform or nonuniform), then FINUFFT does the transform.

Inversion is harder, but a standard way to start is to give each point a quadrature weight equal to the gap between the midpooints to the points to left and right. (Ie Voronoi weighting). Then apply the Euler-Fourier formula for the inverse FT with that quadrature approx. Best Alex

On Mon, Apr 24, 2023 at 1:56 PM Kevin Mendoza @.***> wrote:

I'd be interested in a writeup on how to get frequency bin centers. I'm not quite sure how to apply the math to my own data to get frequency bin centers. @carlos-pereyra https://github.com/carlos-pereyra

— Reply to this email directly, view it on GitHub https://github.com/flatironinstitute/finufft/issues/197#issuecomment-1520594528, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACNZRSQERWYMXCHZSZ5KMLLXC25ENANCNFSM5FYOPFUA . You are receiving this because you were mentioned.Message ID: @.***>

-- *-------------------------------------------------------------------~^`^~._.~' |\ Alex Barnett Center for Computational Mathematics, Flatiron Institute | \ http://users.flatironinstitute.org/~ahb 646-876-5942