l0-Normi, l1-Normi, l2-Normi, ... , l-infinity Normi - Rorasan blogi

Käsittelen normiin liittyviä asioita paljon viime aikoina ja on aika puhua siitä. Tässä postauksessa keskustelemme koko normiperheestä.

Mikä on normi?

Matemaattisesti normi on vektoriavaruuden tai matriisien kaikkien vektoreiden yhteenlaskettu koko tai pituus. Yksinkertaisuuden vuoksi voidaan sanoa, että mitä suurempi normi on, sitä suurempi (arvo) matriisi tai vektori on. Normi voi esiintyä monessa muodossa ja monella nimellä, kuten näillä suosituilla nimillä: Euklidinen etäisyys, keskineliövirhe jne.

Viimeisimmin normi esiintyy tällaisessa yhtälössä:

$\left \| x \right \|$ missä $x$ voi olla vektori tai matriisi.

Etuklidinen normi esimerkiksi vektorille $a = \begin{bmatrix} 3 \\ -2 \\ 1 \end{bmatrix}$ on $\left \| a \right \|_2=\sqrt{3^2+(-2)^2+1^2}=3.742$ , joka on vektorin

Yllä oleva esimerkki osoittaa, miten lasketaan euklidinen normi eli muodollisesti $l_2$ -normi. On olemassa monia muita normityyppejä, joita emme voi selittää tässä, itse asiassa jokaiselle reaaliluvulle on olemassa sitä vastaava normi (Huomaa korostettu sana reaaliluku, joka tarkoittaa, että se ei rajoitu vain kokonaislukuihin.)

Formallisesti $l_p$ -normi $x$ :lle $x$ määritellään seuraavasti:

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

Siinä se! Kaikkien alkioiden yhteenlaskun p:nnen potenssin p:nnen potenssiin on se, mitä kutsumme normiksi.

Erityisen mielenkiintoista on se, että vaikka kaikki $l_p$ -normit näyttävät hyvin samankaltaisilta, niiden matemaattiset ominaisuudet ovat hyvin erilaiset ja näin ollen myös niiden sovellukset ovat dramaattisesti erilaisia. Seuraavassa tarkastelemme joitakin näistä normeista yksityiskohtaisesti.

l0-normi

Ensimmäinen normi, jota käsittelemme, on $l_0$ -normi. Määritelmän mukaan $x$ :n $l_0$ -normi on

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

Suoraan ottaen $l_0$ -normi ei varsinaisesti ole normi. Se on kardinaalisuusfunktio, jonka määritelmä on muodossa $l_p$ -normi, vaikka monet kutsuvatkin sitä normiksi. Sen kanssa on hieman hankala työskennellä, koska siinä esiintyy nollapotentiaalia ja nollajuurta. Ilmeisesti mistä tahansa $x>0$ :stä tulee sellainen, mutta nollavoiman ja erityisesti nollan juuren määritelmään liittyvät ongelmat sotkevat asioita tässä. Niinpä todellisuudessa useimmat matemaatikot ja insinöörit käyttävät sen sijaan tätä $l_0$ -normin määritelmää:

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

Se on nollasta poikkeavien elementtien kokonaislukumäärä vektorissa.

Koska se on nollasta poikkeavien elementtien lukumäärä, on niin monia sovelluksia, jotka käyttävät $l_0$ -normia. Viime aikoina se on vieläkin enemmän esillä, koska nousu Compressive Sensing järjestelmä, joka on yrittää löytää harvinaisin ratkaisu alideterminoituun lineaariseen järjestelmään. Harvinaisin ratkaisu tarkoittaa ratkaisua, jossa on vähiten nollasta poikkeavia merkintöjä eli pienin $l_0$ -normi. Tätä ongelmaa pidetään yleensä $l_0$ -normin optimointiongelmana tai $l_0$ -optimointiongelmana.

l0-optimointi

Monissa sovelluksissa, kuten kompressiivisessa sensoinnissa, yritetään minimoida joidenkin rajoitusten mukaisen vektorin $l_0$ -normia, mistä käytetään nimitystä ” $l_0$ -minimointi”. Tavallinen minimointiongelma muotoillaan seuraavasti:

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

Mutta sen tekeminen ei ole helppo tehtävä. Koska $l_0$ -normin matemaattisen esityksen puuttuessa $l_0$ -minimointia pidetään tietojenkäsittelytieteilijöiden keskuudessa NP-vaikeana ongelmana, mikä kertoo yksinkertaisesti siitä, että se on liian monimutkainen ja lähes mahdoton ratkaista.

Monissa tapauksissa $l_0$ -minimointiongelma relaksoidaan korkeamman asteen normiongelmaksi, kuten $l_1$ -minimointi ja $l_2$ -minimointi.

l1-normi

Normin määritelmää noudattaen $l_1$ -normi $x$ määritellään seuraavasti:

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

Tämä normi on varsin yleinen normiperheen keskuudessa. Sillä on monta nimeä ja monta muotoa eri alojen keskuudessa, nimittäin Manhattan-normi on sen lempinimi. Jos $l_1$ -normi lasketaan kahden vektorin tai matriisin erotukselle, eli

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

sitä kutsutaan tietokonenäön tutkijoiden keskuudessa Sum of Absolute Difference (SAD).

Yleisemmässä tapauksessa signaalien eron mittauksessa se voidaan skaalata yksikkövektoriin seuraavasti:

$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 |$ missä $n$ on koko $x$ .

jota kutsutaan nimellä Mean-Absolute Error (MAE).

l2-normi

Normista suosituin on $l_2$ -normi. Sitä käytetään lähes kaikilla tekniikan ja koko tieteen aloilla. Perusmääritelmän mukaisesti $l_2$ -normi määritellään seuraavasti:

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

$l_2$ -normi tunnetaan hyvin euklidisena normina, jota käytetään vakiosuureena vektorieron mittaamisessa. Kuten $l_1$ -normi, jos Euklidinen normi lasketaan vektorierolle, se tunnetaan Euklidisena etäisyytenä:

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

tai neliömuodossaan, joka tunnetaan tietokonenäön tutkijoiden keskuudessa nimellä Sum of Squared Difference (SSD):

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

Sen tunnetuin sovellus signaalinkäsittelyn alalla on keskineliövirheen (Mean-Squared Error, MSE) mittaus, jota käytetään kahden signaalin välisen samankaltaisuuden, laadun tai korrelaation laskemiseen. MSE on

$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$

Kuten aiemmin $l_0$ -optimointi-osiossa käsiteltiin, monien sekä laskennallisesta että matemaattisesta näkökulmasta ilmenevien ongelmien vuoksi monet $l_0$ -optimointiongelmat rentoutuvat sen sijaan $l_1$ – ja $l_2$ -optimointiin. Tämän vuoksi keskustelemme nyt $l_2$ -optimoinnista.

l2-optimointi

Kuten $l_0$ -optimointitapauksessa $l_2$ -normin minimointiongelma muotoillaan

$min \left \| x \right \|_2$ , jolle pätee $Ax = b$

Asetetaan, että rajoitusmatriisilla $A$ on täysi arvojärjestys (full rank), niin tämä ongelma on nyt aliterminoidun systeemin alainen systeemi, jolla on ääretön määrä ratkaisuja. Tavoitteena on tässä tapauksessa poimia näistä äärettömän monista ratkaisuista paras ratkaisu, eli jolla on pienin $l_2$ -normi. Tämä voisi olla hyvin työlästä, jos se laskettaisiin suoraan. Onneksi on olemassa matemaattinen kikka, joka voi auttaa meitä paljon tässä työssä.

Käyttämällä Lagrangen kertoimien temppua voimme sitten määritellä Lagrangen

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

jossa $\lambda$ on esitelty Lagrangen kertoimet. Otetaan tämän yhtälön derivaatta nollaksi optimaalisen ratkaisun löytämiseksi ja saadaan

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

sovitetaan tämä ratkaisu rajoitukseen, jolloin saadaan

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

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

ja lopuksi

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

Käyttämällä tätä yhtälöä pystymme nyt välittömästi laskemaan optimaalisen ratkaisun $l_2$ -optimointiongelmaan. Tämä yhtälö tunnetaan hyvin nimellä Moore-Penrosen pseudoinversio ja itse ongelma tunnetaan yleensä nimellä pienimmän neliösumman ongelma, pienimmän neliösumman regressio tai pienimmän neliösumman optimointi.

Mutta vaikka pienimmän neliösumman menetelmän ratkaisu on helppo laskea, se ei välttämättä ole paras ratkaisu. Koska $l_2$ -normi itsessään on tasainen, on vaikea löytää yhtä ainoaa, parasta ratkaisua ongelmaan.

Vaikka päinvastoin, $l_1$ -optimointi voi antaa paljon paremman tuloksen kuin tämä ratkaisu.

l1-optimointi

Tavanomaiseen tapaan $l_1$ -minimointiongelma muotoillaan seuraavasti:

$min \left \| x \right \|_1$ jolle pätee $Ax = b$

Koska $l_1$ -normin luonne ei ole tasainen kuten $l_2$ -normin tapauksessa, tämän ongelman ratkaisu on paljon parempi ja yksikäsitteisempi kuin $l_2$ -optimoinnin.

Vaikka $l_1$ -minimoinnin ongelma on lähes samanmuotoinen kuin $l_2$ -minimoinnin ongelma, se on kuitenkin paljon vaikeampi ratkaista. Koska tässä ongelmassa ei ole sileää funktiota, temppu, jota käytimme $l_2$ -ongelman ratkaisemiseen, ei enää päde. Ainoa jäljellä oleva tapa löytää sen ratkaisu on etsiä sitä suoraan. Ratkaisun etsiminen tarkoittaa sitä, että meidän on laskettava jokainen yksittäinen mahdollinen ratkaisu löytääksemme parhaan ”äärettömän monen” mahdollisen ratkaisun joukosta.

Koska ei ole helppoa tapaa löytää ratkaisua tälle ongelmalle matemaattisesti, $l_1$ -optimoinnin käyttökelpoisuus on hyvin rajallinen vuosikymmeniä. Viime aikoihin asti suuren laskentatehon omaavien tietokoneiden kehittyminen on mahdollistanut sen, että voimme ”pyyhkäistä” läpi kaikki ratkaisut. Käyttämällä monia hyödyllisiä algoritmeja, nimittäin Convex Optimisation -algoritmia, kuten lineaarista ohjelmointia tai epälineaarista ohjelmointia jne. on nyt mahdollista löytää paras ratkaisu tähän kysymykseen. Monet $l_1$ -optimointiin perustuvat sovellukset, kuten kompressiivinen anturointi, ovat nyt mahdollisia.

Nykyään on saatavilla monia $l_1$ -optimointiin tarkoitettuja työkalupakkeja. Nämä työkalupakit käyttävät yleensä erilaisia lähestymistapoja ja/tai algoritmeja saman kysymyksen ratkaisemiseen. Esimerkkinä näistä työkalupaketeista ovat l1-magic, SparseLab, ISAL1,

Nyt olemme käsitelleet monia normiperheen jäseniä alkaen $l_0$ -normista, $l_1$ -normista ja $l_2$ -normista. On aika siirtyä seuraavaan. Koska keskustelimme heti alussa siitä, että voi olla mitä tahansa l-minkä tahansa normia, joka noudattaa samaa normin perusmääritelmää, vie paljon aikaa puhua kaikista niistä. Onneksi $l_0$ -, $l_1$ – ja $l_2$ -normia lukuun ottamatta loput niistä ovat yleensä harvinaisia, joten niissä ei ole niin paljon mielenkiintoista tarkasteltavaa. Tarkastelemme siis normin ääritapausta, joka on $l_{\infty}$ -normi (l-infiniteettinormi).

l-infiniteettinormi

Kuten aina, $l_{\infty}$ -normin määritelmä on

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

Nyt tämä määritelmä näyttää taas hankalalta, mutta itse asiassa se on aika suoraviivainen. Tarkastellaan vektoria $\boldsymbol{x}$ , sanotaan jos $x_j$ on vektorin $\boldsymbol{x}$ korkein merkintä, itse äärettömyyden ominaisuuden mukaan, voimme sanoa, että

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

silloin

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

ton

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

Nyt voimme yksinkertaisesti sanoa, että $l_{\infty}$ -normi on

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

eli tuon vektorin maksimimerkintöjen suuruus. Tämä varmasti demystifioi $l_{\infty}$ -normin

merkityksen Nyt olemme keskustelleet koko normiperheestä $l_0$ :sta $l_{\infty}$ :een, toivon, että tämä keskustelu auttaisi ymmärtämään normin merkityksen, sen matemaattiset ominaisuudet ja sen reaalimaailman seuraukset.

Viitteet ja jatkolukemista:

Matemaattinen normi – wikipedia

Matemaattinen normi – 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

Muokattu (15/02/15) : Korjattu sisällön epätarkkuuksia.

Arquidia Mantina

Arquidia Mantina

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

Vastaa Peruuta vastaus