l0-Norm, l1-Norm, l2-Norm, ... , l-infinity Norm - blog Rorasa

Ostatnio dużo pracuję nad rzeczami związanymi z normą i nadszedł czas, aby o tym porozmawiać. W tym poście zamierzamy omówić całą rodzinę norm.

Co to jest norma?

Matematycznie norma to całkowity rozmiar lub długość wszystkich wektorów w przestrzeni wektorowej lub macierzy. Dla uproszczenia możemy powiedzieć, że im wyższa jest norma, tym większa jest (wartość w) macierzy lub wektorze. Norma może występować w wielu formach i wielu nazwach, w tym te popularne nazwy: odległość euklidesowa, średni błąd kwadratowy, itp.

Większość czasu zobaczysz norma pojawia się w równaniu, jak to:

$\left \| x \right \|$ gdzie $x$ może być wektorem lub macierzą.

Na przykład norma euklidesowa wektora $a = \begin{bmatrix} 3 \\ -2 \\ 1 \end{bmatrix}$ wynosi $\left \| a \right \|_2=\sqrt{3^2+(-2)^2+1^2}=3.742$ , co jest rozmiarem wektora $a$

Powyższy przykład pokazuje, jak obliczyć normę euklidesową, lub formalnie nazywaną normą $l_2$ . Istnieje wiele innych typów norm, które wykraczają poza nasze wyjaśnienia tutaj, faktycznie dla każdej liczby rzeczywistej, istnieje norma jej odpowiadająca (Zauważ, że podkreślone słowo liczba rzeczywista, oznacza to, że nie ogranicza się tylko do liczb całkowitych.)

Formalnie norma $l_p$ dla $x$ jest zdefiniowana jako:

$\left \| x \right \|_p = \sqrt[p]{\sum_{i}\left | x_i \right |^p}$ gdzie $p \epsilon \mathbb{R}$

To wszystko! P-root sumy wszystkich elementów do p-tej potęgi jest tym, co nazywamy normą.

Ciekawy punkt jest taki, że nawet jeśli każda $l_p$ -norma jest bardzo podobna do siebie, ich właściwości matematyczne są bardzo różne, a zatem ich zastosowanie jest również dramatycznie różne. Poniżej zamierzamy przyjrzeć się niektórym z tych norm w szczegółach.

l0-norma

Pierwszą normą, którą zamierzamy omówić jest $l_0$ -norma. Z definicji, $l_0$ -norma z $x$ jest

$\left \| x \right \|_0 = \sqrt[0]{\sum_{i}x_i^0}$

Ściśle mówiąc, $l_0$ -norma nie jest w rzeczywistości normą. Jest to funkcja kardynalności, która ma swoją definicję w postaci $l_p$ -normy, choć wiele osób nazywa ją normą. Jest to trochę trudne do pracy, ponieważ występuje w nim obecność zerowej mocy i zerowej korzeni. Oczywiście każdy $x>0$ stanie się jednym z nich, ale problemy z definicją zerowej mocy, a zwłaszcza zerowej podstawy, powodują bałagan tutaj. Więc w rzeczywistości większość matematyków i inżynierów używa tej definicji $l_0$ -normy zamiast:

$\left \| x \right \|_0 = \#(i | x_i \neq 0)$

to całkowita liczba niezerowych elementów w wektorze.

Ponieważ jest to liczba niezerowego elementu, jest tak wiele aplikacji, które używają $l_0$ -normy. Ostatnio jest to jeszcze bardziej w centrum uwagi ze względu na wzrost Compressive Sensing schematu, który jest spróbować znaleźć najsłabsze rozwiązanie under-determined układu liniowego. Najskromniejsze rozwiązanie oznacza rozwiązanie, które ma najmniejszą liczbę niezerowych pozycji, czyli najmniejszą $l_0$ normę. Problem ten jest zwykle traktowany jako problem optymalizacji $l_0$ normy lub $l_0$ -optymalizacji.

l0-optymalizacja

W wielu aplikacjach, w tym Compressive Sensing, próbuje się zminimalizować $l_0$ normę wektora odpowiadającego pewnym ograniczeniom, stąd nazywa się to „ $l_0$ -minimalizacją”. Standardowy problem minimalizacji jest sformułowany jako:

$min \left \| x \right \|_0$ subject to $Ax = b$

Jednak wykonanie takiego zadania nie jest łatwe. Ze względu na brak matematycznej reprezentacji $l_0$ -normy, $l_0$ -minimalizacja jest uważana przez informatyków za problem NP-hard, co po prostu mówi, że jest to problem zbyt złożony i prawie niemożliwy do rozwiązania.

W wielu przypadkach problem $l_0$ -minimalizacji jest zrelaksowany do bycia problemem norm wyższego rzędu, takim jak $l_1$ -minimalizacja i $l_2$ -minimalizacja.

l1-norma

Podążając za definicją normy, $l_1$ -norma z $x$ jest zdefiniowana jako

$\left \| x \right \|_1 = \sum_{i} \left | x_i \right |$

Ta norma jest dość powszechna wśród rodziny norm. Ma wiele nazw i wiele form wśród różnych dziedzin, a mianowicie Manhattan norm jest jej pseudonimem. Jeśli $l_1$ norma jest obliczana dla różnicy między dwoma wektorami lub macierzami, to jest

$SAD(x_1,x_2) = \left \| x_1-x_2 \right \|_1 = \sum \left | x_{1_i}-x_{2_i} \right |$

nazywana jest Sumą Różnicy Absolutnej (SAD) wśród naukowców zajmujących się widzeniem komputerowym.

W bardziej ogólnym przypadku pomiaru różnicy sygnałów, może być ona przeskalowana do wektora jednostkowego przez:

$MAE(x_1,x_2) = \frac{1}{n} \left \| x_1-x_2 \right \|_1 = \frac {1} {n} \sum \left | x_{1_i} - x_{2_i} \right |$ gdzie $n$ jest wielkością $x$ .

która jest znana jako Mean-Absolute Error (MAE).

l2-norma

Najpopularniejszą ze wszystkich norm jest $l_2$ -norma. Jest ona stosowana w prawie każdej dziedzinie inżynierii i nauki jako całości. Po podstawowej definicji, $l_2$ -norma jest zdefiniowana jako

$\left \| x \right \|_2 = \sqrt{\sum_{i}x_i^2}$

$l_2$ -norma jest dobrze znana jako norma euklidesowa, która jest używana jako standardowa wielkość do pomiaru różnicy wektorów. Podobnie jak w $l_1$ -normie, jeśli norma euklidesowa jest obliczana dla różnicy wektorów, jest ona znana jako odległość euklidesowa:

$\left \| x_1-x_2 \right \|_2 = \sqrt{\sum_i (x_{1_i}-x_{2_i})^2}$

lub w postaci podniesionej do kwadratu, znanej jako suma różnicy kwadratowej (SSD) wśród naukowców zajmujących się widzeniem komputerowym:

$SSD(x_1,x_2) = \left \| x_1-x_2 \right \|_2^2 = \sum_i (x_{1_i}-x_{2_i})^2$

Najbardziej znanym jego zastosowaniem w dziedzinie przetwarzania sygnałów jest pomiar błędu średniokwadratowego (MSE), który jest używany do obliczania podobieństwa, jakości lub korelacji między dwoma sygnałami. MSE jest

$MSE(x_1,x_2) = \frac{1}{n} \left \| x_1-x_2 \right \|_2^2 = \frac{1}{n} \sum_i (x_{1_i}-x_{2_i})^2$

Jak wcześniej omówiono w sekcji $l_0$ -optymalizacja, z powodu wielu problemów zarówno z punktu widzenia obliczeniowego, jak i matematycznego, wiele problemów $l_0$ -optymalizacji rozluźnia się, aby zamiast tego stać się $l_1$ – i $l_2$ -optymalizacją. Z tego powodu omówimy teraz optymalizację $l_2$ .

l2-optymalizacja

Tak jak w przypadku $l_0$ -optymalizacji, problem minimalizacji $l_2$ -normy jest sformułowany przez

$min \left \| x \right \|_2$ subject to $Ax = b$

Zakładając, że macierz ograniczeń $A$ ma pełną rangę, problem ten jest teraz systemem underdertermined, który ma nieskończone rozwiązania. Celem w tym przypadku jest wyciągnięcie najlepszego rozwiązania, tj. mającego najniższą $l_2$ -normę, z tych nieskończenie wielu rozwiązań. Mogłoby to być bardzo żmudną pracą, gdyby miało być obliczane bezpośrednio. Na szczęście jest pewien matematyczny trik, który może nam bardzo pomóc w tej pracy.

Używając triku z mnożnikami Lagrange’a, możemy wtedy zdefiniować Lagrangian

$\mathfrak{L}(\boldsymbol{x}) = \left \| \boldsymbol{x} \right \|_2^2+\lambda^{T}(\boldsymbol{Ax}-\boldsymbol{b})$

gdzie $\lambda$ jest wprowadzonym mnożnikiem Lagrange’a. Weźmy pochodną tego równania równą zero, aby znaleźć optymalne rozwiązanie i otrzymać

$\hat{\boldsymbol{x}}_{opt} = -\frac{1}{2} \boldsymbol{A}^{T} \lambda$

włączmy to rozwiązanie do ograniczenia, aby otrzymać

$\boldsymbol{A}\hat{\boldsymbol{x}}_{opt} = -\frac{1}{2}\boldsymbol{AA}^{T}\lambda=\boldsymbol{b}$

$\lambda=-2(\boldsymbol{AA}^{T})^{-1}\boldsymbol{b}$

i w końcu

$\hat{\boldsymbol{x}}_{opt}=\boldsymbol{A}^{T} (\boldsymbol{AA}^{T})^{-1} \boldsymbol{b}=\boldsymbol{A}^{+} \boldsymbol{b}$

Korzystając z tego równania, możemy teraz natychmiast obliczyć optymalne rozwiązanie problemu optymalizacji $l_2$ . To równanie jest dobrze znane jako pseudoinwersja Moore’a-Penrose’a, a sam problem jest zwykle znany jako problem najmniejszej kwadratowości, regresja najmniejszej kwadratowości lub optymalizacja najmniejszej kwadratowości.

Jednakże, mimo że rozwiązanie metody najmniejszej kwadratowości jest łatwe do obliczenia, nie musi być najlepszym rozwiązaniem. Z powodu gładkiej natury $l_2$ -normy samej w sobie, trudno jest znaleźć jedno, najlepsze rozwiązanie dla problemu.

W przeciwieństwie do tego, $l_1$ -optymalizacja może zapewnić znacznie lepszy wynik niż to rozwiązanie.

l1-optymalizacja

Jak zwykle, problem $l_1$ -minimalizacji jest sformułowany jako

$min \left \| x \right \|_1$ subject to $Ax = b$

Ponieważ natura $l_1$ -normy nie jest gładka jak w przypadku $l_2$ -normy, rozwiązanie tego problemu jest znacznie lepsze i bardziej unikalne niż $l_2$ -optymalizacja.

Jednakże, mimo że problem $l_1$ -minimalizacji ma prawie taką samą postać jak $l_2$ -minimalizacji, jest on znacznie trudniejszy do rozwiązania. Ponieważ problem ten nie ma funkcji gładkiej, sztuczka, której użyliśmy do rozwiązania $l_2$ -problemu, nie ma już racji bytu. Jedynym sposobem na znalezienie jego rozwiązania jest bezpośrednie szukanie. Poszukiwanie rozwiązania oznacza, że musimy obliczyć każde możliwe rozwiązanie, aby znaleźć najlepsze z puli „nieskończenie wielu” możliwych rozwiązań.

Ponieważ nie ma łatwego sposobu na matematyczne znalezienie rozwiązania tego problemu, użyteczność $l_1$ -optymalizacji jest bardzo ograniczona przez dziesięciolecia. Do niedawna postęp w dziedzinie komputerów o dużej mocy obliczeniowej pozwala na „przeczesanie” wszystkich rozwiązań. Dzięki zastosowaniu wielu pomocnych algorytmów, a mianowicie algorytmu optymalizacji wypukłej, takich jak programowanie liniowe, lub programowanie nieliniowe, itp. możliwe jest obecnie znalezienie najlepszego rozwiązania tego pytania. Wiele aplikacji, które opierają się na $l_1$ -optymalizacji, w tym Compressive Sensing, jest teraz możliwe.

W dzisiejszych czasach dostępnych jest wiele zestawów narzędzi do $l_1$ -optymalizacji. Te skrzynki narzędziowe zazwyczaj używają różnych podejść i/lub algorytmów do rozwiązania tego samego problemu. Przykładem takich narzędzi są l1-magic, SparseLab, ISAL1,

Teraz omówiliśmy wielu członków rodziny norm, począwszy od $l_0$ -normy, $l_1$ -normy i $l_2$ -normy. Nadszedł czas, aby przejść do następnego. Ponieważ na samym początku rozmawialiśmy o tym, że może istnieć dowolna l-wszelka norma zgodna z tą samą podstawową definicją normy, omówienie ich wszystkich zajmie sporo czasu. Na szczęście, poza $l_0$ -, $l_1$ – , i $l_2$ -norma, pozostałe są zwykle rzadkie i dlatego nie ma tak wielu ciekawych rzeczy do oglądania. Przyjrzymy się więc skrajnemu przypadkowi normy, którym jest $l_{\infty}$ -norma (l-infinity norm).

l-infinity norm

Jak zawsze, definicja dla $l_{\infty}$ -normy jest

$\left \| x \right \|_{\infty} = \sqrt[\infty]{\sum_i x_i^{\infty}}$

Teraz ta definicja znowu wygląda na podchwytliwą, ale w rzeczywistości jest całkiem prosta. Rozważmy wektor $\boldsymbol{x}$ , powiedzmy, że jeśli $x_j$ jest najwyższym wpisem w wektorze $\boldsymbol{x}$ , przez własność samej nieskończoności, możemy powiedzieć, że

$x_j^{\infty}\gg x_i^{\infty}$ $\forall i \neq j$

$\sum_i x_i^{\infty} = x_j^{\infty}$

then

$\left \| x \right \|_{\infty} = \sqrt[\infty]{\sum_i x_i^{\infty}} = \sqrt[\infty]{x_j^{\infty}} = \left | x_j \right |$

Teraz możemy po prostu powiedzieć, że $l_{\infty}$ -norma jest

$\left \| x \right \|_{\infty} = max(\left | x_i \right |)$

czyli maksymalna wielkość wpisów tego wektora. To z pewnością zdemistyfikowało znaczenie $l_{\infty}$ -normy

Teraz omówiliśmy całą rodzinę norm od $l_0$ do $l_{\infty}$ , mam nadzieję, że ta dyskusja pomogłaby zrozumieć znaczenie normy, jej matematyczne właściwości i jej implikacje w świecie rzeczywistym.

Referencje i dalsza lektura:

Mathematical Norm – wikipedia

Mathematical Norm – MathWorld

Michael Elad – „Sparse and Redundant Representations : From Theory to Applications in Signal and Image Processing” , Springer, 2010.

Linear Programming – MathWorld

Compressive Sensing – Rice University

Edycja (15/02/15) : Poprawione nieścisłości w treści.

Arquidia Mantina

Arquidia Mantina

l0-Norm, l1-Norm, l2-Norm, … , l-infinity Norm

Dodaj komentarz Anuluj pisanie odpowiedzi