Jak pobrać FFT nierówno rozmieszczonych danych?

Fast Fourier Transform algorytm oblicza rozkładu Fouriera przy założeniu, że punkty wejściowe są równo rozłożone w dziedzinie czasu . Co jeśli nie są? Czy istnieje inny algorytm, którego mógłbym użyć, lub w jakiś sposób zmodyfikować FFT, aby uwzględnić efektywną zmienną częstotliwość próbkowania?$t_k = kT$

Jeśli rozwiązanie zależy od sposobu dystrybucji próbek, najbardziej interesują mnie dwie sytuacje:

• Stała częstotliwość próbkowania z fluktuacją: gdzie δ t k jest zmienną losową. Załóżmy, że można bezpiecznie powiedzieć | δ t k | < T / 2 .$t_k = kT + \delta t_k$$\delta t_k$$|\delta t_k| < T/2$
• Upuszczone próbki ze skądinąd stałej częstotliwości próbkowania: gdzie n k ∈ Z ≥ $t_k = n_k T$$n_k \in\mathbb{Z}\ge k$

Motywacja: po pierwsze, było to jedno z najczęściej głosowanych pytań dotyczących propozycji tej witryny. Ale dodatkowo jakiś czas temu włączyłem się w dyskusję na temat wykorzystania FFT (podpowiedź na pytanie o przepełnienie stosu ), w której pojawiły się niektóre dane wejściowe z nierównomiernie próbkowanymi punktami. Okazało się, że znaczniki czasu w danych były nieprawidłowe, ale przyszło mi do głowy, w jaki sposób można rozwiązać ten problem.

Istnieje wiele różnych technik niejednorodnego FFT, a najbardziej wydajne są przeznaczone dokładnie do Twojego przypadku: próbki quasi-jednolite. Podstawową ideą jest rozmazanie nierównomiernie próbkowanych źródeł na nieco drobniejszą („nadpróbkowaną”) jednolitą siatkę za pośrednictwem lokalnych zwojów przeciwko Gaussom. Standardową FFT można następnie uruchomić na jednolitej siatce z nadpróbkowanymi próbkami, a następnie można cofnąć splot przeciwko Gaussom. Dobre implementacje są czymś w rodzaju razy droższym niż standardowe FFT w wymiarach d , gdzie C jest bliskie 4 lub 5.$C^d$$d$$C$

Polecam lekturę Przyspieszenie szybkiej transformacji Fouriera Nonuniform autorstwa Greengarda i Lee.

$O(N^d \log N)$

Ważną kwestią jest to, że wszystkie powyższe techniki są przybliżeniami, które mogą być dowolnie dokładne kosztem dłuższych czasów wykonywania, podczas gdy standardowy algorytm FFT jest dokładny.

W przetwarzaniu sygnału unika się aliasingu , wysyłając sygnał przez filtr dolnoprzepustowy przed próbkowaniem. Jack Poulson wyjaśnił już jedną technikę nierównomiernego FFT przy użyciu skróconych Gaussów jako filtrów dolnoprzepustowych. Jedną z niewygodnych cech skróconych Gaussianów jest to, że nawet po podjęciu decyzji o odstępach siatki dla FFT (= częstotliwość próbkowania w przetwarzaniu sygnału), nadal masz dwa wolne parametry: szerokość Gaussa i promień obcięcia.

Dlatego wolę funkcję „hat” o szerokości dwóch komórek siatki jako filtr dolnoprzepustowy. Powoduje to, że zerowa kolejność Fouriera jest dokładna i że niższe rzędy Fouriera zbiegają się kwadratowo. Transformata Fouriera funkcji „hat” jest łatwa do obliczenia (jest kwadratem funkcji sinc), co upraszcza cofnięcie splotu po FFT. Zauważ, że funkcja „kapelusza” jest splotem charakterystycznej funkcji (wyśrodkowanej) komórki z samym sobą. Dowolną pożądaną szybkość konwergencji można osiągnąć, łącząc komórkę elementarną więcej niż jeden raz z sobą i używając wynikowej funkcji zamiast funkcji „kapelusza”.

Jeśli jesteś zainteresowany oprogramowaniem, mogę polecić bibliotekę NFFT (w C z interfejsem do MATLAB), którą można znaleźć tutaj . Zauważ, że istnieje również biblioteka PFFT do równoległego obliczania FFT, a nawet biblioteka PNFFT do równoległych, nierównomiernych FFT przez tych samych programistów .

Dodatek do zaakceptowanej odpowiedzi. Oto link do implementacji metody Greengarda i Lee w wersji open source: https://finufft.readthedocs.io/en/latest/ Ma opakowania dla C, fortran, MATLAB, oktawy i python. Wierzę, że FINUFFT jest napisany w C ++.

Jest utrzymywany i używany w NYU Courant Institute, SFU, Flatiron Institute (oczywiście), University of Texas Austin i Florida State University. Przynajmniej o tych wiem.

Sam używam starszej wersji, bo jestem leniwy. Zobacz: https://cims.nyu.edu/cmcl/nufft/nufft.html

Interesująca może być dyskretna transformata Fouriera z kompensacją daty:

Ferraz-Mello, S., 1981, Oszacowanie okresów z nierównomiernie rozłożonych obserwacji , The Astronomical Journal, 302: 757-763 .