Czy miara korelacji falkowej jest warta dodatkowego obciążenia obliczeniowego?

9

Użyłem zarówno korelacji, jak i koherencji jako miar korelacji między sygnałami. Myślałem, że podejście czasowo-częstotliwościowe da mi najlepsze z tych światów.

Moje pytanie brzmi, czy te dodatkowe dane dodają wystarczającej ilości do ogólnego obrazu sygnału, aby uzasadnić wzrost kosztów obliczeniowych związanych z wykonywaniem transformacji falkowej w ramach obliczeń?

Odniesienie: praca ArXiv : „Technika korelacji krzyżowej w domenie falkowej do wykrywania stochastycznych fal grawitacyjnych” S.Klimenko, G. Mitselmakher, A.Sazonov

jonsca
źródło
Ile dodatkowych kosztów obliczeniowych? Czy możesz to zrobić szybciej dzięki FFT lub FWT?
endolith,
@endolith Zakładając, że już włączyłem te algorytmy.
jonsca
1
Cóż, spójność i korelacja mogłyby używać zarówno FFT, czyli O (N log N), podczas gdy FWT to O (N), więc metoda falkowa może być rzeczywiście szybsza ? Nie mam jasnego zrozumienia tego, chociaż, mimo prośby dwukrotnie: math.stackexchange.com/questions/28581/... stackoverflow.com/questions/1787536/...
endolit
1
W każdym razie powinieneś użyć tego, który jest najbardziej odpowiedni do tego, co próbujesz zrobić. To trochę jak pytanie „co jest lepsze? Wkrętaki lub młotki?”
endolith,
1
@jonsca Twoja intuicja jest słuszna. Najwyraźniej transformacja DWT jest wariantem czasowym, a ta właściwość może prowadzić do pewnego wykorzystania. Właściwie robię dokładnie to samo dla projektu, nad którym pracuję. Celem jest oszacowanie TDOA (Time Delay of Arrival) między dwoma sygnałami, więc najpierw przekształciłem je za pomocą (ręcznie napisanego) DWT, a następnie skorelowałem je. Oto link do artykułu, który możesz przeczytać na ten temat z mojego publicznego dropboxa. ( dl.dropbox.com/u/4724281/waveletBasedTDOA.pdf )
Spacey

Odpowiedzi:

5

Po pierwsze, powinieneś użyć dowolnego narzędzia odpowiedniego dla danego zadania. Korelacja vs spójność vs korelacja falkowa to różne rzeczy, więc to pytanie jest trochę jak pytanie „co jest lepsze? Wkrętaki lub młotki?” Zależy to od tego, co próbujesz zrobić i od tego, czy zależy Ci na podobieństwie w czasie, widmach częstotliwości, czy obu.

Po drugie, mam minimalne zrozumienie falek, ale twoje założenie, że falki wymagają więcej obliczeń, może być błędne. Fast Fourier Transform wykonuje operacji , podczas gdy szybko WAVELET Transform wykonuje . Tak więc metoda falkowa może wymagać mniej obliczeń, w zależności od tego, czy możesz użyć uzyskanych z niej informacji.O(nlogn) O(n)

Empirycznie , wytwarzając n danych wyjściowych z n rzeczywistych danych wejściowych, wielopoziomowa transformacja falkowa w PyWavelets staje się szybsza niż FFT NumPy, gdy n jest większe niż około 4096.

wprowadź opis zdjęcia tutaj

jednak

  1. To jest Python, a dwie implementacje mogą być bardzo różnie wydajne. Nie wiem nawet, czy wavedec()można go uznać za szybką transformatę falkową. W swojej dokumentacji używają skrótu DWT . Czy Haar DWT i FWT to to samo?
  2. Czas zmienia się w zależności od zastosowanej falki. Fala Meyera zajmuje 6 razy więcej niż Daubechies, aby wygenerować taką samą ilość danych.
  3. Nadal nie rozumiem, w jaki sposób FWT układa płaszczyznę czasowo-częstotliwościową lub czy wytworzenie n wyjść jest wystarczające, aby uzyskać ten sam rodzaj pomiaru podobieństwa, jak n -punktowa okrągła korelacja krzyżowa za pomocą FFT. (Technicznie rzecz biorąc, jest to płaszczyzna czasu, a nie częstotliwość-czas, ale myślę, że są one takie same dla złożonej falki Morleta ?) FWT jest „krytycznym próbkowaniem” płaszczyzny i wytwarza taką samą ilość danych jak FFT, więc porównanie ich wydaje się słuszne.

Chodzi o to, że czas obliczeń jest co najmniej mniej więcej podobny dla obu, więc nie sądzę, że powinieneś się tym przejmować, decydując, którego użyć.

endolit
źródło
3

Jest bardzo późno, ale może i tak warto ...

Płaszczyzna skali czasu nie jest tym samym co płaszczyzna czasowo-częstotliwościowa, chociaż może być również przydatna. Sygnały w różnych miejscach na płaszczyźnie skali czasu są powiązane przez , gdzie przesuwa cię w górę (lub w dół) w skali, a przesuwa się z czasem. Ta sama transformacja w płaszczyźnie czasowo-częstotliwościowej to , gdzie to przesunięcie częstotliwości. Jeśli twój sygnał jest falą sinusoidalną, dwie transformacje są takie same.x(t)x(Δs(tΔt))ΔsΔtx(t)x(tΔt)eiΔωtΔωx(t)

DWT lub dyskretna transformata falkowa oblicza tylko dyskretne skale, podobnie jak FFT oblicza tylko dyskretne częstotliwości. A komentarz, który @Spacey napisał powyżej, że DWT nie jest niezmienny dla tłumaczenia, jest poprawny. Dzieje się tak, ponieważ na każdym etapie DWT sygnał jest dziesiątkowany przez dwa. To sprawia, że ​​DWT jest szybszy niż FFT, , ale także niszczy niezmienność translacji.O(N)

Zatem użycie DWT do zbadania płaszczyzny w czasie nie zaprowadzi cię daleko. Jest to szczególnie prawdziwe, ponieważ skale „odwiedzane” przez DWT są podzielone przez dwa czynniki i są znacznie mniej gęste niż zasięg, jaki można uzyskać w płaszczyźnie czasowo-częstotliwościowej za pomocą FFT. Musisz użyć transformaty falkowej, która jest niezmienna dla translacji, czasami nazywanej nieokreśloną transformatą falkową , wśród wielu innych nazw. Nawet wtedy nadal masz do czynienia z rzadkością próbek w skali obliczonej.

Ponadto często pożądane jest myślenie o miejscach na płaszczyźnie skali czasu o gęstości energii. Takie podejście jest ułatwione dzięki zastosowaniu falki analitycznej, takiej jak wspomniana wcześniej złożona falka Morleta. Jedną z metod równoważących niezmienność translacji i analityczność z czasem obliczeniowym jest złożona transformacja falkowa podwójnego drzewa . Wykonanie tego samego na płaszczyźnie czasowo-częstotliwościowej jest być może łatwiejsze: najpierw wykonaj przybliżoną transformację Hilberta na swoim sygnale, wykonując FFT, wyzerowując wszystkie ujemne częstotliwości, a następnie IFFT.

Jeśli intuicja, że ​​korelacja szuka podobieństwa w czasie, a spójność szuka podobieństwa w częstotliwości, jest prawidłowa, być może lepiej będzie trzymać się płaszczyzny czasowo-częstotliwościowej. Jest to z pewnością łatwiejsze do obliczenia i łatwo udoskonalić próbkowanie wzdłuż osi częstotliwości. Żadne z wyżej wymienionych podejść nie obejmuje bardziej gęstego próbkowania osi skali. Aby to zrobić, musisz przejść do ciągłej transformacji falkowej , chociaż może być coś jeszcze, czego nie jestem świadomy. Jeśli masz Matlab, kliknij powyższy link i skorzystaj z niego.

Cena Rodneya
źródło