Czym jest rzadka transformata Fouriera?

46

MIT ostatnio trochę hałasuje na temat nowego algorytmu reklamowanego jako szybsza transformacja Fouriera, która działa na określonych rodzajach sygnałów, na przykład: „ Szybsza transformacja Fouriera nazwana jedną z najważniejszych nowych technologii na świecie ”. Magazyn MIT Technology Review mówi :

Dzięki nowemu algorytmowi, zwanemu rzadką transformacją Fouriera (SFT), strumienie danych mogą być przetwarzane od 10 do 100 razy szybciej niż było to możliwe w przypadku FFT. Przyspieszenie może nastąpić, ponieważ informacje, na których nam najbardziej zależy, mają dużą strukturę: muzyka nie jest przypadkowym hałasem. Te znaczące sygnały zwykle mają tylko ułamek możliwych wartości, które może przyjąć sygnał; technicznym terminem jest to, że informacje są „rzadkie”. Ponieważ algorytm SFT nie jest przeznaczony do pracy ze wszystkimi możliwymi strumieniami danych, może on przyjmować pewne skróty, które w innym przypadku nie byłyby dostępne. Teoretycznie algorytm, który może obsłużyć tylko rzadkie sygnały, jest znacznie bardziej ograniczony niż FFT. Ale „rzadkość jest wszędzie”, zauważa współtwórca Katabi, profesor elektrotechniki i informatyki. „Jest w naturze; to” s w sygnałach wideo; jest w sygnałach audio ”.

Czy ktoś mógłby tu podać bardziej techniczne wyjaśnienie, czym właściwie jest algorytm i gdzie może być zastosowany?

EDYCJA: Niektóre linki:

nibot
źródło

Odpowiedzi:

40

Idea algorytmu jest następująca: załóżmy, że masz sygnał długości , który jest rzadki w dziedzinie częstotliwości. Oznacza to, że gdyby obliczyć jego dyskretną transformatę Fouriera , byłaby niewielka liczba wyjść które są niezerowe; inne są nieistotne. Jednym ze sposobów uzyskania wyników jest użycie FFT w całej sekwencji, a następnie wybranie niezerowych wartości.NkNNkkk

Przedstawiony tutaj algorytm rzadkiej transformaty Fouriera jest techniką obliczania tych wyników o mniejszej złożoności niż metoda oparta na FFT. Zasadniczo, ponieważ wyniki są zerowe, można zaoszczędzić trochę wysiłku, wprowadzając skróty w algorytmie, aby nawet nie generować tych wartości wyników. Podczas gdy FFT ma złożoność , algorytm rzadki ma potencjalnie niższą złożoność w przypadku widma rzadkiego.kNkO(nlogn)O(klogn)

Na bardziej ogólnym przypadku, gdy widmo jest „rodzajem sparse” ale istnieje więcej niż wartości niezerowych (np szeregu dźwięków wbudowanego w hałasie), stanowią one zmianę algorytmu, który szacuje się największe wyjść z złożoność czasowa , która może być również mniej złożona niż FFT.kkO(klognlognk)

Zgodnie z jednym wykresem ich wyników (przedstawionym na poniższym obrazku) punkt podziału dla lepszej wydajności w odniesieniu do FFTW (zoptymalizowanej biblioteki FFT, stworzonej przez innych ludzi z MIT) znajduje się w pobliżu punktu, w którym tylko -te do -te spośród współczynników transformacji wyjściowej są niezerowe. Ponadto w tej prezentacji wskazują, że rzadki algorytm zapewnia lepszą wydajność, gdy .12111210Nk[2000,106]

wprowadź opis zdjęcia tutaj

Warunki te ograniczają możliwość zastosowania algorytmu do przypadków, w których wiadomo, że prawdopodobnie będzie kilka znacząco dużych pików w spektrum sygnału. Jednym z przykładów, które cytują na swojej stronie internetowej, jest to, że średnio 8 na 8 bloków pikseli często używanych w kompresji obrazu i wideo ma prawie 90% rzadkości w dziedzinie częstotliwości, a zatem może skorzystać z algorytmu wykorzystującego tę właściwość. Ten poziom rzadkości nie wydaje się odpowiadać przestrzeni aplikacji dla tego konkretnego algorytmu, więc może to być tylko przykład ilustrujący.

Muszę jeszcze trochę przeczytać literaturę, aby lepiej zrozumieć, jak praktyczna jest taka technika do rozwiązywania rzeczywistych problemów, ale w przypadku niektórych klas zastosowań może być odpowiednia.

Jason R.
źródło
2
Więc to w zasadzie strata FFT? Jak koder MP3?
endolith
3
@endolith: Nie jestem pewien, czy powiedziałbym to w ten sposób. Być może bardziej analogiczny do przyciętego algorytmu FFT, który oblicza tylko podzbiór danych wyjściowych. Twierdzenie jest takie, że jeśli sygnał wejściowy jest rzadki, to wyjść jest obliczane dokładnie. kk
Jason R
Zastanawiam się, jak wypada to w porównaniu z algorytmem Goertzela (lub ich rodziną). Wydaje się, że jedyną różnicą jest to, że w Goertzel wiesz, czego szukasz na początek.
Spacey
5
@endolith: Kompresja MP3 jest stratna, ponieważ współczynniki są kwantowane; nie dlatego, że zachowane są tylko najwyższe współczynniki k. Rzadkie FFT = "jaka jest reprezentacja współczynników k minimalizujących różnicę z sygnałem wejściowym". Kodowanie ramki mp3 = „jakie są skwantowane współczynniki i poziomy kwantyzacji, które minimalizują błąd (percepcyjny), biorąc pod uwagę budżet N bitów na przechowywanie współczynników i współczynników skali”.
pikenety
1
Gdy zostaną wyrzucone, jest to efekt uboczny kwantyzacji (wartość jest zaokrąglana do 0)
pikenety
7

Nie czytałem artykułu na temat sFFT, ale mam wrażenie, że pomysł na załatwienie FFT polega na wykorzystaniu przeważności k-sparsity. Dlatego nie trzeba obliczać wszystkich wpisów współczynników FFT, a jedynie obliczać k z nich. Dlatego właśnie dla sygnału k-rzadkiego złożoność wynosi O (klog n) zamiast O (nlog n) dla konwencjonalnego FFT.

W jakikolwiek sposób, w odniesieniu do komentarzy @rcmpton, mówiąc: „Idea skompresowanego wykrywania polega na tym, że możesz odzyskiwać rzadkie dane z rzadkich losowych próbek pobranych z innej domeny (np. Odzyskiwać rzadkie obrazy z losowych rzadkich danych częstotliwości (tj. MRI)) . ” Pytanie brzmi: „rzadkie losowe próbki”? Myślę, że mogą to być próbki zebrane przez losowe rzutowanie rzadkich danych do niższej podprzestrzeni (pomiarowej).

I, jak zrozumiałem, teoretyczne ramy wykrywania kompresyjnego składają się głównie z 3 zagadnień, rzadkości, pomiaru i odzyskiwania. Przez rzadkość dotyczy poszukiwania rzadkich reprezentacji dla pewnej klasy sygnałów, co jest zadaniem uczenia się słownika. Przez pomiar odnosi się do poszukiwania skutecznego sposobu (wydajności obliczeniowej i odzysku) do pomiaru danych (lub rzutowania danych do niższej przestrzeni pomiarowej), co jest zadaniem zaprojektowania macierzy pomiarowej, takiej jak losowa macierz Gaussa, strukturalna macierz losowa,. ... A przez odzyskanie jest rzadkie problemy z regularną inwersją liniową, l0, l1, l1-l2, lp, grupa l, blabla ..., a uzyskane algorytmy są różne, Dopasowywanie pościgu, miękkie progowanie, twarde progowanie, pościg, bayesian, ....

Prawdą jest, że „cs to minimalizacja normy L1”, a norma L1 jest podstawową zasadą dla cs, ale cs to nie tylko minimalizacja normy L1. Poza powyższymi 3 częściami istnieją również rozszerzenia, takie jak strukturalne wykrywanie kompresji (grupowe lub modelowe), w których wykorzystywana jest również strukturalna rzadkość, i udowodniono, że znacznie poprawia zdolność odzyskiwania.

Podsumowując, cs jest dużym krokiem w teorii próbkowania, zapewniając skuteczny sposób próbkowania sygnałów, pod warunkiem, że sygnały te są wystarczająco rzadkie . Tak więc cs jest teorią próbkowania , każdy, kto zamierza ją wykorzystać jako jakąś technikę klasyfikacji lub rozpoznawania, wprowadza w błąd zasadę. I czasami znajduję trochę papieru zatytułowanego „oparte na wyczuciu ściskającym .....” i myślę, że zasadą takiego papieru jest wykorzystanie minimalizacji L1 zamiast cs i lepiej jest używać „opartej na minimalizacji L1 ... „.

Jeśli się mylę, popraw mnie, proszę.

Pierre
źródło
Witamy w DSP.SE To świetny wkład.
Phonon
6

Przejrzałem gazetę i myślę, że mam ogólne pojęcie o metodzie. „Sekretny szum” tej metody polega na tym, jak uzyskać rzadką reprezentację sygnału wejściowego w dziedzinie częstotliwości. Poprzednie algorytmy wykorzystywały rodzaj brutalnej siły do ​​lokalizacji dominującego współczynnika rzadkości. W tej metodzie zastosowano technikę, która nazywa się „odzyskiwaniem przestrzeni” lub „skompresowanym wykrywaniem”. Artykuł wiki zastosowany tutaj Dokładna metoda odzyskiwania rzadkiego wygląda podobnie do „twardego progowania” - jednej z dominujących metod odzyskiwania rzadkiego.

Technika PS rzadkiego odzyskiwania / skompresowanego wykrywania i związana z nim minimalizacja L1 znalazły wiele zastosowania w nowoczesnym przetwarzaniu sygnału, a zwłaszcza w związku z transformacją Fouriera. W rzeczywistości jest to konieczność wiedzieć o nowoczesnym przetwarzaniu sygnału. Ale zanim transformacja Fouriera została wykorzystana jako jedna z metod rozwiązania problemu rzadkiego odzyskiwania. Tutaj widzimy naprzeciwko - rzadki odzyskiwania dla transformaty Fouriera.

Dobra strona do przeglądu skompresowanego wykrywania: nuit-blanche.blogspot.com/

Odpowiedź PPS na poprzedni komentarz - jeśli sygnał wejściowy nie jest bardzo rzadki, jest stratny.

Nie krępuj się mnie poprawić, jeśli popełniłem błąd.

mirror2image
źródło
Papier FFT nie wykrywa kompresji. Idea skompresowanego wykrywania polega na tym, że możesz odzyskać rzadkie dane z rzadkich losowych próbek pobranych z innej domeny (np. Odzyskać rzadkie obrazy z losowych rzadkich danych częstotliwości (tj. MRI)). Chociaż może to skrócić czas akwizycji, zwiększa koszty obliczeniowe. Dokument FFT różni się tym, że masz wszystkie dane w obu domenach, a celem jest szybkie obliczenie.
dranxo
Mylisz się co do skompresowanego wykrywania.
mirror2image
1
Czy możesz rozwinąć?
dranxo
Skompresowane wykrywanie jest ogromnym obszarem z rozmytymi krawędziami, które obejmują / są połączone nie tylko z odzyskiem per se, ale z podobnymi obszarami regularyzacją , minimalnymi złożonościami itp. Początkowo jest to problem ograniczony rzadkością , x in , R ^ n \ | x \ | _0 <k $, ale później stało się o wiele bardziej brad. Zacznij od przeczytania wiki x = y R m r I n , m > > n w ı t h k c ö a n s t r i n tLpAx=yRmyin,m>>nwithconstraint
mirror2image
Nie. Skompresowane wykrywanie oznacza, że ​​rozwiązujesz zastrzeżeniem . Istnieje wiele dalekosiężnych zastosowań, ale jeśli nie odwołujesz się do twierdzenia Candesa-Romberga-Tao, w pewnym momencie mylisz ludzi, jeśli nazywasz swoją pracę „kompresyjnym wyczuwaniem”. Oto odniesienie: www-stat.stanford.edu/~candes/papers/spm-robustcs-v05.pdfmin|x|1Ax=y
dranxo