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

Jag har jobbat mycket med saker som har med norm att göra på sistone och det är dags att prata om det. I det här inlägget kommer vi att diskutera en hel familj av normer.

Vad är en norm?

Matematiskt sett är en norm den totala storleken eller längden på alla vektorer i ett vektorrum eller matriser. För enkelhetens skull kan vi säga att ju högre normen är, desto större är (värdet i) matrisen eller vektorn. Norm kan komma i många former och med många namn, inklusive dessa populära namn: Euklidiskt avstånd, medelkvadratiskt fel, etc.

För det mesta kommer du att se att normen förekommer i en ekvation som denna:

$\left \| x \right \|$ där $x$ kan vara en vektor eller en matris.

En euklidisk norm för en vektor $a = \begin{bmatrix} 3 \\ -2 \\ 1 \end{bmatrix}$ är till exempel $\left \| a \right \|_2=\sqrt{3^2+(-2)^2+1^2}=3.742$ vilket är storleken på vektor $a$

Ovanstående exempel visar hur man beräknar en euklidisk norm, eller formellt kallad $l_2$ -norm. Det finns många andra typer av normer som vi inte kan förklara här, faktiskt finns det en norm som motsvarar varje enskilt reellt tal (lägg märke till det betonade ordet reellt tal, det betyder att det inte är begränsat till bara heltal).

Formellt definieras $l_p$ -normen för $x$ som:

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

Det är allt! En p-te rot av en summering av alla element till p-te potensen är vad vi kallar en norm.

Den intressanta punkten är att även om alla $l_p$ -normer ser väldigt lika ut, så är deras matematiska egenskaper väldigt olika och därmed är deras tillämpning också dramatiskt annorlunda. Härmed ska vi titta närmare på några av dessa normer.

l0-norm

Den första normen vi ska diskutera är en $l_0$ -norm. Per definition är $l_0$ -normen för $x$

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

Strikt sett är $l_0$ -normen egentligen inte en norm. Det är en kardinalitetsfunktion som har sin definition i form av $l_p$ -norm, även om många kallar det för en norm. Den är lite knepig att arbeta med eftersom det finns en förekomst av zeroth-power och zeroth-root i den. Självklart kommer alla $x>0$ att bli en sådan, men problemen med definitionen av zeroth-power och särskilt zeroth-root ställer till det här. Så i verkligheten använder de flesta matematiker och ingenjörer denna definition av $l_0$ -norm i stället:

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

Det är ett totalt antal icke-noll-element i en vektor.

Då det är ett antal icke-noll-element, finns det så många tillämpningar som använder $l_0$ -norm. På senare tid har den hamnat ännu mer i fokus på grund av Compressive Sensing-principen, som går ut på att hitta den sparsammaste lösningen på det underbestämda linjära systemet. Med den sparsammaste lösningen menas den lösning som har minst antal icke-nollposter, dvs. den lägsta $l_0$ -normen. Detta problem betraktas vanligen som ett optimeringsproblem med $l_0$ -norm eller $l_0$ -optimering.

l0-optimering

Många tillämpningar, inklusive Compressive Sensing, försöker minimera $l_0$ -normen för en vektor som motsvarar vissa begränsningar, och kallas därför ” $l_0$ -minimering”. Ett standardminimeringsproblem formuleras som:

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

Det är dock ingen lätt uppgift att göra detta. På grund av bristen på $l_0$ -normens matematiska representation betraktas $l_0$ -minimering av datavetare som ett NP-hårt problem, vilket helt enkelt innebär att det är för komplext och nästan omöjligt att lösa.

I många fall är $l_0$ -minimeringsproblem avslappnat till högre ordningens normproblem som $l_1$ -minimering och $l_2$ -minimering.

l1-norm

Följande definitionen av norm definieras $l_1$ -norm för $x$ som

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

Denna norm är ganska vanlig bland normfamiljen. Den har många namn och många former bland olika områden, nämligen Manhattan norm är dess smeknamn. Om $l_1$ -normen beräknas för en skillnad mellan två vektorer eller matriser, det vill säga

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

, kallas den för Sum of Absolute Difference (SAD) bland forskare inom datorseende.

I ett mer allmänt fall av mätning av signaldifferens kan den skalas till en enhetsvektor genom:

$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 |$ där $n$ är en storlek på $x$ .

vilket är känt som Mean-Absolute Error (MAE).

l2-norm

Den mest populära av alla normer är $l_2$ -normen. Den används inom nästan alla områden inom teknik och vetenskap som helhet. Enligt den grundläggande definitionen definieras $l_2$ -normen som

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

$l_2$ -normen är välkänd som en euklidisk norm, som används som en standardmängd för att mäta en vektordifferens. Liksom i $l_1$ -norm, om den euklidiska normen beräknas för en vektordifferens, är den känd som ett euklidiskt avstånd:

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

eller i sin kvadratiska form, känd som en summa av kvadratisk skillnad (Sum of Squared Difference, SSD) bland forskare inom datorseende:

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

Den mest kända tillämpningen inom signalbehandlingsområdet är MSE-måttet (Mean-Squared Error), som används för att beräkna en likhet, en kvalitet eller en korrelation mellan två signaler. MSE är

$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 tidigare diskuterats i $l_0$ -optimeringsavsnittet, på grund av många problem från både en beräkningssynpunkt och en matematisk synpunkt, slappnar många $l_0$ -optimeringsproblem av för att istället bli $l_1$ – och $l_2$ -optimering. På grund av detta kommer vi nu att diskutera om optimering av $l_2$ .

l2-optimering

Som i $l_0$ -optimeringsfallet formuleras problemet med att minimera $l_2$ -normen genom

$min \left \| x \right \|_2$ med förbehåll för $Ax = b$

Antag att tvångsmatrisen $A$ har full rang, är detta problem nu ett underderminerat system som har oändliga lösningar. Målet i detta fall är att ur dessa oändligt många lösningar dra ut den bästa lösningen, dvs. som har lägst $l_2$ -norm, från dessa oändligt många lösningar. Detta skulle kunna bli ett mycket tråkigt arbete om det skulle beräknas direkt. Som tur är finns det ett matematiskt knep som kan hjälpa oss mycket i detta arbete.

Med hjälp av ett knep med Lagrange-multiplikatorer kan vi sedan definiera en lagrangian

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

där $\lambda$ är den införda Lagrange-multiplikatorn. Ta derivatan av denna ekvation lika med noll för att hitta en optimal lösning och få

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

plugga in denna lösning i begränsningen för att få

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

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

och slutligen

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

Med hjälp av denna ekvation kan vi nu omedelbart beräkna en optimal lösning av $l_2$ -optimeringsproblemet. Denna ekvation är välkänd som Moore-Penrose Pseudoinverse och själva problemet brukar kallas Least Square-problem, Least Square-regression eller Least Square-optimering.

Men även om lösningen med Least Square-metoden är lätt att beräkna är det inte nödvändigtvis den bästa lösningen. På grund av $l_2$ -normens jämna natur i sig är det svårt att hitta en enda, bästa lösning för problemet.

Tvärtom kan $l_1$ -optimering ge ett mycket bättre resultat än denna lösning.

l1-optimering

Som vanligt formuleras $l_1$ -minimeringsproblemet som

$min \left \| x \right \|_1$ med förbehåll för $Ax = b$

Om $l_1$ -normens karaktär inte är lika jämn som i $l_2$ -normfallet är lösningen på detta problem mycket bättre och mer unik än $l_2$ -optimeringen.

Men även om problemet med $l_1$ -minimering har nästan samma form som $l_2$ -minimering är det mycket svårare att lösa. Eftersom detta problem inte har en jämn funktion är det trick vi använde för att lösa $l_2$ -problemet inte längre giltigt. Det enda sättet som återstår för att hitta dess lösning är att söka efter den direkt. Att söka efter lösningen innebär att vi måste beräkna varje enskild möjlig lösning för att hitta den bästa från poolen av ”oändligt många” möjliga lösningar.

Då det inte finns något enkelt sätt att matematiskt hitta lösningen på detta problem, är användbarheten av $l_1$ -optimering mycket begränsad under årtionden. Fram till nyligen har utvecklingen av datorer med hög beräkningskraft gjort det möjligt för oss att ”svepa” igenom alla lösningar. Genom att använda många användbara algoritmer, nämligen den konvexa optimeringsalgoritmen såsom linjär programmering, eller icke-linjär programmering, etc. är det nu möjligt att hitta den bästa lösningen på denna fråga. Många tillämpningar som bygger på $l_1$ -optimering, bland annat Compressive Sensing, är nu möjliga.

Det finns många verktygslådor för $l_1$ -optimering tillgängliga nuförtiden. Dessa verktygslådor använder vanligtvis olika metoder och/eller algoritmer för att lösa samma fråga. Exempel på dessa verktygslådor är l1-magic, SparseLab, ISAL1,

Nu har vi diskuterat många medlemmar av normfamiljen, med utgångspunkt i $l_0$ -norm, $l_1$ -norm och $l_2$ -norm. Det är dags att gå vidare till nästa. Eftersom vi redan i början diskuterade att det kan finnas vilken l-vad-norm som helst som följer samma grundläggande definition av norm, kommer det att ta mycket tid att prata om dem alla. Lyckligtvis är det så att bortsett från $l_0$ -, $l_1$ – och $l_2$ -norm är resten av dem oftast ovanliga och har därför inte så många intressanta saker att titta på. Så vi ska titta på extremfallet av norm som är en $l_{\infty}$ -norm (l-infinity norm).

l-infinity norm

Som alltid är definitionen för $l_{\infty}$ -norm

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

Nu ser den här definitionen återigen knepig ut, men den är faktiskt ganska rak. Betrakta vektorn $\boldsymbol{x}$ , låt oss säga om $x_j$ är den högsta posten i vektorn $\boldsymbol{x}$ , genom egenskapen oändligheten själv, kan vi säga att

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

då

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

då

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

Nu kan vi helt enkelt säga att $l_{\infty}$ -normen är

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

därmed är den högsta postens storlek i denna vektor. Det avmystifierade säkert innebörden av $l_{\infty}$ -norm

Nu har vi diskuterat hela familjen av norm från $l_0$ till $l_{\infty}$ , jag hoppas att den här diskussionen hjälper till att förstå innebörden av norm, dess matematiska egenskaper och dess implikationer i den verkliga världen.

Referenser och vidare 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

Redigera (15/02/15) : Korrigerade felaktigheter i innehållet.

Arquidia Mantina

Arquidia Mantina

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

Lämna ett svar Avbryt svar