Czym jest rzadka transformata Fouriera?

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:

• Artykuł: „ Prawie optymalna rzadka transformata Fouriera ” (arXiv) autorstwa Haithama Hassanieha, Piotra Indyka, Diny Katabi, Erica Price'a.
• Strona projektu - zawiera przykładową implementację.

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.$N$$k \ll N$$N-k$$k$$k$

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.$k$$N-k$$O(n \log n)$$O(k \log n)$

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.$k$$k$$O(k \log n \log \frac{n}{k})$

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 .$\frac{1}{2^{11}}$$\frac{1}{2^{10}}$$\frac{N}{k} \in [2000, 10^6]$

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.

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ę.

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.