Newton, Pascal i hermeneutyka - witajcie w świecie 4G

Mimo, że skończyłem szkołę w odległych i coraz szybciej, niestety, oddalających się czasach, pojęcie lektury obowiązkowej nie stało mi się obce. Tak więc, poza rzeczami które czytam z ciekawości, z chęci wzbogacenia poglądów, dla nauki, dla przyjemności, ze snobizmu etc. etc. zdarza mi się czytać rzeczy po prostu z obowiązku. Ostatnia lektura, która poczatkowo wydawała mi się koszmarnie nudna ale ciekawość moja rosła i wciąż rośnie oraz pojawiają się pewne oznaki satysfakcji z niej, to pewne fragmenty dokumentu o wiele mówiącym oznaczeniu 3GPP TS 36.213 V8.8.0 (2009-09) .

Tu dygresja: studiowanie dokumentów opisujących standardy telekomunikacyjne ma w sobie coś z sztuki walki, coś z rozwiązywania rebusa i coś ze studiowania świętej księgi. Zatem: Środki retoryczne jakimi posługują się autorzy owych dzieł ograniczają się zwykle do nadużywania trybu rozkazującego ("X shall Y..." - "Zaprawdę powiadam Ci, X będzie Y..." ). Powtarzalność schematów zdań ukrywa nagłe zwroty akcji. Jakakolwiek motywacja działań bohaterów jest szczelnie zakryta przed czytelnikiem. Zrozumienie wymaga długotrwałych medytacji i skomplikowanych egzegez. Wrogiem jest montonia, nuda, nieuwaga. Piszący owe standardy, w końcu, często nadzwyczaj jednostronnie biorą sobie do serca uwagę Gaussa o "zwiezłości, cesze którą należy brać pod rozwagę tak bardzo jak to możliwe".
Szczególnym gatunkiem owej literatury, do których przynależy i przywołany przeze mnie dokument, są opisy standardów komunikacji bezprzewodowej. Kapryśna i ograniczona natura medium i nieustający głód szybkości, pojemności i niezawodności prowadzi do tworzenia skomplikowanych piętrowych konstrukcji, nad którymi władzę absolutną sprawują Oszczędność, Zapobiegliwość i Kompromis.

Wracając do mojej lektury, okazuje się, że aby zadość uczynić surowym prawom owych trzech władców nadzwyczaj często należy uciec się do fortelu a pomocnikiem jest matematyka. O jednym fortelu , na który się natknąłem opowiem, bo to proste, ciekawe i - przynajmniej dla mnie - zaskakujące. Istotę tego fortelu należy jednak dopiero wyłuskać z opisu. Rzecz podana została bowiem do wierzenia.

Pomedytujmy, nad następującymi wersetami (przy okazji będącymi typową próbką stylu):




Co się za tym kryje. Otóż, chodzi o metodę pozwalającą w możliwie najzwięźlejszy sposób przekazać informację o wybranym M-elementowym podzbiorze w uporządkowanym zbiorze N - elementowym. Zakładamy przy tym, że obie strony znają N i M.

Uwaga - w dalszym ciągu na oznaczenie symbolu Newtona przyjmę (^N_M) - oznacza "N po M". Stosuję też konwencję jak w artykule (tj. dla N <>N_M) = 0).

Jak możnaby to zrobić? Pierwszy pomysł to wziąć N bitów i zapalić odpwiednie M z nich (stworzyć mapę bitową), następnie przesłać taką liczbę binarną. Ale, N może być duże i przesłać musielibyśmy wiele liczb. Ba, ten sposób pomija zupełnie informację, że M jest ustalone i potrzebuje więc zwykle [log₂N]+1 (czasem tylko log2N) bitów ale wykorzystuje tylko (^N_M)/2^N część owej przestrzeni możliwych map bitowych. Z punktu widzenia królowej Oszczędności sytuacja niedopuszczalna.

Możnaby z drugiej strony - korzystając z faktu, że jest (^N _M) kombinacji N elementów z M elementów - wymyślić jakąkolwiek funkcję przypisującą liczbom od 0 do (^N _M) -1 stosowny zbiór, umówić obie strony zeby ją znały i używały. Musielibyśmy wówczas jednak wymyślić bardzo wiele takich funkcji dla różnych par N i M - Zapobiegliwość nie byłaby z nas zadowolona.

Kompromisu w takich sytuacjach nakazuje s: znajdźmy uniwersalny sposób kodowania. Fortel - i mamy metodę opisaną w standardzie. Poniżej zajmę się jej objaśnieniem:

Po pierwsze, przypomnijmy sobie wzór dotyczący symbolu Newtona - nb. kluczowy dla konstrukcji trójkąta Pascala:

(ⁿ _k) + (ⁿ _k-1) = (ⁿ⁺¹ _k) (*)

Po drugie zauważmy, że jezeli n > m to
(ⁿ _k) >= (^m _k) (**)

To łatwo udowodnić indukcją (zadanie licealne) albo zobaczyć od razu (stosując indukcję niejako niejawnie) z (*). Po prostu

(ⁿ _k) = (^n-1 _k) + (^n-1_k-1) = (^n-2 _k) + (^n-2 _k-1) + (^n-1 _k-1) = [powtarzamy rozwinięcie pierwszego składnika] = (^m _k) + C

które to C jest >=0 (> 0 jeśli n > k).

Po trzecie zauważmy, że:

(^N-1 _M) + (^N-2 _M-1) +... + (^N-M ₁) = (^N _M) -1 (***)

Tym razem: szybka ale trochę fikuśna indukcja:

Oznaczmy F(n,m) = (^n-1 _m) + ... + (^n-m ₁)

Wtedy:
F(n,1) = (^n-1 ₁) = n = (ⁿ ₁) -1

Załóżmy, że dla ustalonego n i m F(n-1,m-1) = (^n-1 _m-1) -1

Wtedy F(n,m) = (^n-1 _m) + F(n-1, m-1) = (^n-1 _m) + (^n-1 _m-1) - 1 = (ⁿ _m) -1

(ponownie z (*) )

Teraz prosto do tajemnicy naszego indeksu.

Weżmy jakiekolwiek r ∈ {0,..., (^N _M)-1}.

Weźmy największe K = K(r, N, M) t. że (K(r,N,M) _M) <= r. Takie K(r, N, M) oczywiście istnieje i jest jedyne - z (**) Zauważmy, że r - (^{K(r, N, M)} _M) ≤ (^{K(r, N, M)} _M-1) - 1

to jasne bo w przeciwnym razie

r >= (^{K(r, N, M)} _M) + _{(^{K(r, N, M)} M-1}) = (^{K(r, N, M)+1} _M)

co jest sprzecznością bo K(r, N, M) było największe


Zatem, dla r' = (r - (^{K(r, N, M)} _M)) ∈ {0,...,(^K _M-1)-1} czynność możemy powtórzyć wyliczając K':

K > K' = K((r - (^K _M)), K, M-1)

itd. dla M-2, M-3 itd i kolejnych r otrzymując ciąg M różnych wartości.

W ten sposób podaliśmy, algorytm który danego r w jednoznaczny sposób przypisuje ciąg {K_i} spełniający warunek K_i > K_i+1

Proponuję - jako ćwiczenie, żeby nie było nudno - sprawdzić, że opisany algorytm wykonuje operację dokładnie odwrotną do tej opisanej w naszym cytacie. Dodam, że zdaje się, że by to stwierdzić nie trzeba już nic liczyć...

Jeśli chcesz w przyszłości zostać guru...

Co jakiś czas wertując różne nowości i ciekawostki ze świata nauki natrafia się na coś, co pachnie technologią przyszłości. Nie takiej za 50 czy sto lat. Takiej za 5 albo 10. Ostatnio mój kandydat numer jeden to technika tzw. compressed sensing rozwijana przez różne grupy zajmujace się przetwarzaniem sygnałów, głównie w USA, wsparte matematycznie przez taką sławę jak Terence Tao.

Zastosowania compressed sensing, które autorzy najczęściej podają, wiążą sie głównie z akwizycją i kompresowaniem obrazów, choć zastosowania potencjalne idą znacznie dalej. Postaram się w trzech słowach objaśnić co na razie z tego rozumiem.

Compreessed sensing jak wszystko co ma w nazwie "compressed" opiera sie na pewnej redundancji, czyli nadmiarowości w sygnale jakim w naszym przykładzie jest obraz. W klasycznym kodowaniu stratnym proces z grubsza wygląda tak:

(1) najpierw zbieramy dość dokładną informację o sygnale. Dokładność przekłada się zwykle na częstość próbkowania - na przykład w przypadku obrazu w aparacie cyfrowym na ilość elementów czułych w matrycy. Dostajemy pewien wektor w bazie, której każdy element przedstawia jeden piksel. Taka baza to zbiór wektorów postaci:

e_m,n(t,k) = 1 gdy t = m, k = n i 0 w innym wypadku.

W tej bazie obraz ma M na N pikseli ma przedstawienie:

OBRAZ = a_1,1 * e_1,1+...+a_M,N*e_M,N

gdzie a_m,n oznacza poziom jasności piksela. W tej bazie zwykle większość a_i,j jest sporych i nie możnaby łatwo ograniczyć się do części z nich by reprezentować obraz.

(2) Potem dokonujemy transformaty, czyli wyliczamy przedstawienie tego wektora w bazie transformaty.

W przypadku dyskretnej transformaty Fouriera będzie to baza postaci

F_m,n(t, k) = exp(2*pi*i*(t*m/M + n*k/N)).

W tej bazie, nasz wektor będzie miał przedstawienie:

OBRAZ = b_1,1 * F_1,1+...b_M,N*F_M,N.

Tu, zwykle okazuje się, że jest lepiej i pewna niewielka część współczynników dominuje ¹. Oczywiście możemy używać innych baz: np falek (wavelet) itp.

(3) Dokonujemy pewnych uproszczeń na sygnale korzystając z tej jego miłej cechy po przedstawieniu w bazie transformaty o której wspomniałem powyżej i dostajemy


OBRAZ' = b_1,1' * F_1,1+ ...b_M,N' *F_M,N



gdzie współczynniki primowane są bliskie nieprimowanych ale wiele z nich jest po prostu zerem. Wektor OBRAZ' jest bliski wektorowi OBRAZ.


(4) Na drugą stronę linii trzeba więc przekazać (względnie schować do pliku) indeksy i ich wartości tych niezerowych współczynników primowanych



(5) Odtwarzający (odpakowujący) odtwarza z tego co zapisane w punkcie (4) OBRAZ'.


Na ile dobrze to działa (modulo szczegóły techniczne, konkretne transformaty itp. bo zasada jest ta sama) możemy oglądać codziennie przeglądając obrazki na stronach WWW czy oglądając film na DVD.

A teraz wyobraźmy sobie, że nie musimy martwić się przekazywaniem informacji o tym podzbiorze ani o wartościach współczynników. Że zamiast mierzyć wszystkie piksele w kroku 1 mierzymy jedynie ich niewielką ale znaną część, że w ogóle pomijamy krok 2 i krok 3, i przesyłamy tylko wyniki tego pomiaru. Najpierw zalety: postępując w ten sposób mamy:

- mierzenie z kroku 1 staje się tańsze (bo mniej mamy punktów pomiarowych - np. w aparacie zamiast 5 mpx mamy tylko 1 mpx).

- pomijamy niezbyt może kosztowny w epoce FFT, ale mimo wszystko niedarmowy krok 2

- przesyłamy tylko wyniki pomiarów a nie dbmy o przesyłanie indeksów

- wciąż mamy sygnał skompresowany, bo choć przesyłamy wymniki pierwotnego pomiaru, to jest ich istotnie mniej niż w oryginalnym problemie

No dobrze: ale tym sposobem przesłaliśmy znacznie mniej informacji. Mniej jej wydobyliśmy z sygnału (mniej próbek) i nie dokonaliśmy żadnej analizy by wydobyć najcenniejszą jej część. Co zatem zyskaliśmy powyżej tracimy w postaci istotnego zaniku informacji. Nie ma darmowych obiadów... A jednak...

Przy pewnych założeniach, które wkrótce ostrożnie wypowiem (pamiętajcie, piszę co na razie sam z tego rozumiem) taka magia może mieć miejsce. Otóż:

Pomysł compressed sensing polega na tym, że jeżeli wiemy coś o sygnale ponad to co przesyła nam nadawca to coś może nam dać ową brakującą informację, której nikt nam nie przesłał i pozwolić na lepszą rekonstrukcję sygnału² Co to za magiczna wiedza ? Pisałem trochę wyżej, że kompresja się uda jeżeli sygnał będzie kombinacją liniową niewielu wektorów bazy transformaty. Zatem, jeżeli mamy dobrze dobraną do klasy sygnałów bazę i wiemy że sygnały z klasy którą rozważamy mają w niej przedstawienia rzadkie, możemy po stronie odbiorcy zapytać: jaki sygnał będący kombinacją liniową niewielu wektorów bazy transformaty da nam w bazie pomiarowej nasz wynik?

Okazuje się, że odpowiadając na to pytanie w wielu przypadkach jesteśmy w stanie zrekonstruować rzeczywisty sygnał, który tak niechlujnie pomierzyliśmy. W jeszcze większej ilości przypadków jesteśmy w stanie odtworzyć sygnał bliski temu wyjściowemu. Problem: jak to zrobić?

Sposób jest taki: sprowadzić zagadnienie do problemu optymalizacji. Więzy, czyli ograniczenia na sygnał zadane są przez początkowy pomiar. Jeżeli wektory pomiarowe oznaczymy przez e₁,...,e_K a wyniki naszego pomiaru (a więc współczynniki w rozkładzie rzutu wektora OBRAZ na podprzestrzeń generowaną zbiór pomiarowy) przez a₁,...,a_K ograniczenia na poszukiwany sygnał X dają się zapisać jako:

<e₁|X>=a₁, <e₂|X>=a₂,...<e_K|X>=a_K.

Teraz drugi warunek na X, który pozwoli nam wybrać jeden wektor z tej podprzestrzeni. Złym, choć naturalnie narzucającym się sposobem jest poszukiwać wprost wektora którego przedstawienie będzie najrzadsze w bazie transformaty. Złym bo prowadzącym do olbrzymiej, niewykonalnej w praktyce - ilości obliczeń. Pomysł wieć jest taki, żeby zminimalizować pewną normę na przstrzeni sygnału. Okazuje się jednak, że minimalizując (znowu narzucającą się) normę euklidesową | |₂ na ogół dochodzimy do wektora, który nie ma przedstawienia rzadkiego w bazie transformaty. Rozsądnym kompromisem pomiędzy obydwoma podejściami jest minimalizacja normy | |₁ powiązanej z bazą tranformaty

F_1,1, ..., F_M,N

tzn normy takiej, że:


|b_1,1 * F_1,1+ ...b_M,N *F_M,N|₁ = |b_1,1|+...+|b_M,N|


Taki problem jest zagadnieniem klasycznej optymalizacji wypukłej i sposoby jego rozwiązywania są dobrze znane.

Są dwa wybory, których trzeba tu dokonać. Pierwszy to - i jak mawiają Niemcy: hier liegt der hund begraben - wybór bazy transformaty. To ona musi być dobrana do klasy sygnału.
Drugi to wybór zbioru pomiarowego. Okazuje się, że rozmieszczenie wektorów którymi mierzymy sygnał "większość" jest dobra, tzn. można owe wektory wybrać praktycznie losowo. Natomiast ich ilość - aby dostać dobrą rekonstrukcję sygnału musi być rzędu A*log(B) gdzie A to rzadkość sygnału (a więć ilość elementów o niezerowych współczynnikach w przedstawieniu sygnału w bazie) a B to rozmiar tej bazy.

Podobno przykłady pokazują, że teoretyczne ograniczenia w poprzednim paragrafie w praktyce można jeszcze proprawić. Czyli jeśli empiria pokazuje, że jeśli mamy dobrą bazę, to sygnały spotykane w codziennym życiu nawet przy mniejszej ilości pomiarów dają się nieźle zrekonstruować.

Wydaje się, że wielki jest potencjał tych metod. Zarówno do przesyłania i transmisji sygnałów, jak i do rekonstrukcji - np. w obrazowaniu medycznym (choćby tomografia), itd. Zasosowanie do innych sygnałów niż obrazy - np mowy też może być ciekawe. Znowu przesyłanie jest ok, ale jeszcze ciekawsza może być rekonstrukcja z bardzo słabego albo silnie zniekształconego sygnału. Wydaje się, że od specyficznych zastosowań, np. obrazy twarzy itd. itd. można dobrać doskonale pasujące bazy i ich zastosowanie może dać ogromne, nieosiągalne dziś poziomy kompresji. Wydaje się też, że metoda może dać niezwykle tanie i energooszczędne a dokładnie obrazujące czujniki, kamery itp.

Słowem - matematyka w służbie ludzkości. Tak, stanowczo - jeśli chcecie zostać guru telekomunikacji, przetwarzania sygnałów itd. za lat 5-10 uczcie się o compressed sensing już dziś.




¹OK. W rzeczywistości wystarczy nam że sprowadzimy do takiego przedstawienia w bazie, które dobrze się pakuje kompresją bezstratną. "Rzadkość" przedstawienia (a więc duża ilość współczynników zerowych w przedstawieniu w bazie) daje możliwość dobrego upakowania. Dla dyskusji compressed sensing pozostanę przy tej cesze.



²Zupełnie jak paleontolog który z fragmentów kości dinozaura jest w
stanie zrekonstruować zwierzę, ponieważ wie, że rekonstruuje dinozaura.