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

Jeg har arbejdet meget med ting relateret til norm på det seneste, og det er på tide at tale om det. I dette indlæg skal vi diskutere en hel familie af norm.

Hvad er en norm?

Matematisk set er en norm en samlet størrelse eller længde af alle vektorer i et vektorrum eller matricer. For enkelhedens skyld kan vi sige, at jo højere normen er, jo større er (værdien i) matrixen eller vektoren. Norm kan komme i mange former og mange navne, herunder disse populære navn: Euklidisk afstand, Mean-squared Error osv.

De fleste gange vil du se, at normen optræder i en ligning som denne:

$\left \| x \right \|$ hvor $x$ kan være en vektor eller en matrix.

For eksempel er en euklidisk norm for en vektor $a = \begin{bmatrix} 3 \\ -2 \\ 1 \end{bmatrix}$ $\left \| a \right \|_2=\sqrt{3^2+(-2)^2+1^2}=3.742$ , som er størrelsen af vektor $a$

Overstående eksempel viser, hvordan man beregner en euklidisk norm, eller formelt kaldet en $l_2$ -norm. Der findes mange andre typer normer, som ligger uden for vores forklaring her, faktisk er der for hvert enkelt reelt tal en norm, der svarer til det (bemærk det fremhævede ord reelt tal, det betyder, at det ikke kun er begrænset til hele tal).

Formelt set er $l_p$ -normen for $x$ defineret som:

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

Det er det hele! En p-te rod af en summering af alle elementer til p-te potens er det, vi kalder en norm.

Det interessante er, at selv om alle $l_p$ -normer alle ligner hinanden meget, er deres matematiske egenskaber meget forskellige, og dermed er deres anvendelse også dramatisk forskellig. Hermed vil vi se nærmere på nogle af disse normer i detaljer.

l0-norm

Den første norm, vi vil diskutere, er en $l_0$ -norm. Per definition er $l_0$ -norm af $x$

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

Strengt taget er $l_0$ -norm faktisk ikke en norm. Det er en kardinalitetsfunktion, som har sin definition i form af $l_p$ -norm, selv om mange kalder det en norm. Den er lidt vanskelig at arbejde med, fordi der er en tilstedeværelse af nul-power og nul-root i den. Naturligvis vil enhver $x>0$ blive en sådan, men problemerne med definitionen af zeroth-power og især zeroth-root roder tingene rundt her. Så i virkeligheden bruger de fleste matematikere og ingeniører i stedet denne definition af $l_0$ -norm:

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

det er et samlet antal ikke-nul-elementer i en vektor.

Da det er et antal ikke-nul-elementer, er der så mange anvendelser, der bruger $l_0$ -norm. På det seneste er det endnu mere i fokus på grund af fremkomsten af Compressive Sensing-ordningen, som forsøger at finde den sparsomste løsning af det underbestemte lineære system. Ved den sparsomste løsning forstås den løsning, der har færrest ikke-nulposter, dvs. den laveste $l_0$ -norm. Dette problem betragtes normalt som et optimeringsproblem med $l_0$ -norm eller $l_0$ -optimering.

l0-optimering

Mange applikationer, herunder Compressive Sensing, forsøger at minimere $l_0$ -normen af en vektor, der svarer til nogle begrænsninger, og kaldes derfor “ $l_0$ -minimisering”. Et standardminimeringsproblem er formuleret som:

$min \left \| x \right \|_0$ med forbehold af $Ax = b$

Det er imidlertid ikke nogen nem opgave at gøre dette. På grund af manglen på $l_0$ -normens matematiske repræsentation betragtes $l_0$ -minimisering af dataloger som et NP-hårdt problem, hvilket ganske enkelt betyder, at det er for komplekst og næsten umuligt at løse.

I mange tilfælde er $l_0$ -minimiseringsproblemet afslappet til at være et normproblem af højere orden, såsom $l_1$ -minimisering og $l_2$ -minimisering.

l1-norm

Ifølge definitionen af norm er $l_1$ -norm af $x$ defineret som

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

Denne norm er ganske almindelig blandt normfamilien. Den har mange navne og mange former blandt forskellige områder, nemlig Manhattan-norm er dens kælenavn. Hvis $l_1$ -normen beregnes for en forskel mellem to vektorer eller matricer, dvs.

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

, kaldes den for Sum of Absolute Difference (SAD) blandt forskere inden for computervision.

I det mere generelle tilfælde af måling af signalforskelle kan den skaleres til en enhedsvektor ved:

$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 |$ hvor $n$ er en størrelse på $x$ .

som er kendt som Mean-Absolute Error (MAE).

l2-norm

Den mest populære af alle normer er $l_2$ -normen. Den anvendes inden for næsten alle områder inden for teknik og videnskab som helhed. Efter den grundlæggende definition er $l_2$ -norm defineret som

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

$l_2$ -norm er velkendt som en euklidisk norm, der bruges som en standardmængde til måling af en vektordifference. Som i $l_1$ -norm, hvis den euklidiske norm beregnes for en vektordifference, er den kendt som en euklidisk afstand:

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

eller i sin kvadrerede form, kendt som en sum af kvadreret forskel (Sum of Squared Difference (SSD) blandt Computer Vision-forskere:

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

Dets mest kendte anvendelse inden for signalbehandlingsområdet er MSE-målingen (Mean-Squared Error), som bruges til at beregne en lighed, en kvalitet eller en korrelation mellem to signaler. MSE er

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

Som tidligere omtalt i afsnittet om $l_0$ -optimering slapper mange $l_0$ -optimeringsproblemer på grund af mange problemer fra både et beregningsteknisk synspunkt og et matematisk synspunkt af sig selv for i stedet at blive $l_1$ – og $l_2$ -optimering. På grund af dette vil vi nu diskutere om optimering af $l_2$ .

l2-optimering

Som i $l_0$ -optimeringstilfælde formuleres problemet med minimering af $l_2$ -norm ved

$min \left \| x \right \|_2$ med forbehold af $Ax = b$

Hvis man antager, at begrænsningsmatrixen $A$ har fuld rang, er dette problem nu et underdertermineret system, som har uendelige løsninger. Målet i dette tilfælde er at udtrække den bedste løsning, dvs. har laveste $l_2$ -norm, blandt disse uendeligt mange løsninger. Dette kunne være et meget besværligt arbejde, hvis det skulle beregnes direkte. Heldigvis er der et matematisk trick, som kan hjælpe os meget i dette arbejde.

Ved hjælp af et trick med Lagrange-multiplikatorer kan vi så definere en lagrangian

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

hvor $\lambda$ er de indførte Lagrange-multiplikatorer. Tag afledning af denne ligning lig med nul for at finde en optimal løsning og få

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

indsæt denne løsning i begrænsningen for at få

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

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

og endelig

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

Ved hjælp af denne ligning kan vi nu straks beregne en optimal løsning af $l_2$ -optimeringsproblemet. Denne ligning er velkendt som Moore-Penrose Pseudoinverse, og selve problemet er normalt kendt som Least Square-problem, Least Square-regression eller Least Square-optimering.

Men selv om løsningen af Least Square-metoden er let at beregne, er det ikke nødvendigt, at det er den bedste løsning. På grund af $l_2$ -normens glatte natur i sig selv er det svært at finde en enkelt, bedste løsning til problemet.

Tværtimod kan $l_1$ -optimering give et langt bedre resultat end denne løsning.

l1-optimering

Som sædvanlig formuleres $l_1$ -minimeringsproblemet som

$min \left \| x \right \|_1$ med forbehold af $Ax = b$

Da $l_1$ -normens karakter ikke er glat som i $l_2$ -normens tilfælde, er løsningen af dette problem meget bedre og mere entydig end $l_2$ -optimeringen.

Men selv om problemet med $l_1$ -minimisering har næsten samme form som $l_2$ -minimiseringen, er det meget sværere at løse. Fordi dette problem ikke har en glat funktion, er det trick, vi brugte til at løse $l_2$ -problemet, ikke længere gyldigt. Den eneste måde, der er tilbage for at finde dets løsning, er at søge direkte efter det. At søge efter løsningen betyder, at vi skal beregne hver enkelt mulig løsning for at finde den bedste løsning fra puljen af “uendeligt mange” mulige løsninger.

Da der ikke er nogen nem måde at finde løsningen på dette problem matematisk, er $l_1$ -optimeringens nytteværdi meget begrænset i årtier. Indtil for nylig har udviklingen af computere med stor regnekraft gjort det muligt at “feje” gennem alle løsningerne. Ved at bruge mange nyttige algoritmer, nemlig den konvekse optimeringsalgoritme såsom lineær programmering eller ikke-lineær programmering osv. er det nu muligt at finde den bedste løsning på dette spørgsmål. Mange applikationer, der er afhængige af $l_1$ -optimering, herunder Compressive Sensing, er nu mulige.

Der findes i dag mange værktøjskasser til $l_1$ -optimering. Disse værktøjskasser anvender normalt forskellige tilgange og/eller algoritmer til at løse det samme spørgsmål. Eksemplet på disse værktøjskasser er l1-magic, SparseLab, ISAL1,

Nu har vi diskuteret mange medlemmer af normfamilien, begyndende med $l_0$ -norm, $l_1$ -norm og $l_2$ -norm. Det er tid til at gå videre til den næste. Da vi diskuterede helt fra starten, at der kan være enhver l-hvad-norm, der følger den samme grundlæggende definition af norm, vil det tage meget tid at tale om dem alle sammen. Heldigvis er det sådan, at bortset fra $l_0$ -, $l_1$ – , og $l_2$ -norm, er resten af dem normalt ualmindelige og har derfor ikke så mange interessante ting at se på. Så vi skal se på det ekstreme tilfælde af norm, som er en $l_{\infty}$ -norm (l-infinity norm).

l-infinity norm

Som altid er definitionen for $l_{\infty}$ -norm

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

Nu ser denne definition igen vanskelig ud, men faktisk er den ret ligetil. Betragt vektoren $\boldsymbol{x}$ , lad os sige, om $x_j$ er den højeste post i vektoren $\boldsymbol{x}$ , ved selve uendelighedens egenskab, kan vi sige, at

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

så

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

så

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

Nu kan vi simpelthen sige, at $l_{\infty}$ -normen er

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

det er den maksimale posters størrelse i denne vektor. Det afmystificerede sikkert betydningen af $l_{\infty}$ -norm

Nu har vi diskuteret hele familien af norm fra $l_0$ til $l_{\infty}$ , og jeg håber, at denne diskussion vil hjælpe med at forstå betydningen af norm, dens matematiske egenskaber og dens implikationer i den virkelige verden.

Reference og yderligere læsning:

Matematisk norm – wikipedia

Matematisk 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

Edit (15/02/15) : Rettet unøjagtigheder i indholdet.

Arquidia Mantina

Arquidia Mantina

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

Skriv et svar Annuller svar