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ę.
źródło
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ę.
źródło
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.
źródło