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

În ultima vreme lucrez mult la lucruri legate de normă și a venit timpul să vorbesc despre asta. În această postare vom discuta despre o întreagă familie de norme.

Ce este o normă?

Matematic, o normă este dimensiunea sau lungimea totală a tuturor vectorilor dintr-un spațiu vectorial sau matrici. Pentru simplificare, putem spune că, cu cât norma este mai mare, cu atât matricea sau vectorul (valoarea din) este mai mare. Norma poate avea multe forme și multe denumiri, inclusiv aceste denumiri populare: Distanța euclidiană, Eroare medie pătrată, etc.

De cele mai multe ori veți vedea că norma apare într-o ecuație de genul:

$\left \| x \right \|$ unde $x$ poate fi un vector sau o matrice.

De exemplu, norma euclidiană a unui vector $a = \begin{bmatrix} 3 \\ -2 \\ 1 \end{bmatrix}$ este $\left \| a \right \|_2=\sqrt{3^2+(-2)^2+1^2}=3.742$ care este dimensiunea vectorului $a$

Exemplul de mai sus arată cum se calculează o normă euclidiană, sau formal numită $l_2$ -normă. Există multe alte tipuri de norme care depășesc explicațiile noastre, de fapt, pentru fiecare număr real există o normă care îi corespunde (observați cuvântul „număr real” subliniat, ceea ce înseamnă că nu se limitează doar la numere întregi.)

În mod formal, norma $l_p$ a lui $x$ se definește astfel:

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

Asta este! Rădăcina a p-a a unei adunări a tuturor elementelor la puterea a p-a este ceea ce numim normă.

Este interesant faptul că, chiar dacă toate $l_p$ -normele sunt foarte asemănătoare între ele, proprietățile lor matematice sunt foarte diferite și, prin urmare, și aplicațiile lor sunt dramatic de diferite. În cele ce urmează vom analiza în detaliu unele dintre aceste norme.

Norma L0

Prima normă pe care o vom discuta este o normă $l_0$ . Prin definiție, $l_0$ -norma lui $x$ este

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

Strict vorbind, $l_0$ -norma nu este de fapt o normă. Este o funcție de cardinalitate care își are definiția sub forma $l_p$ -normă, deși multă lume o numește normă. Este un pic mai complicat să lucrezi cu ea deoarece în ea este prezentă puterea zeroth și rădăcina zeroth. Evident, orice $x>0$ va deveni o $x>0$ , dar problemele legate de definiția puterii zero și mai ales a rădăcinii zero încurcă lucrurile aici. Așa că, în realitate, majoritatea matematicienilor și inginerilor folosesc în schimb această definiție a $l_0$ -normă:

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

care este un număr total de elemente non-zero într-un vector.

Pentru că este un număr de elemente non-zero, există atât de multe aplicații care folosesc $l_0$ -normă. În ultima vreme este și mai mult în centrul atenției din cauza apariției schemei Compressive Sensing, care încearcă să găsească cea mai rară soluție a sistemului liniar subdeterminat. Soluția cea mai săracă înseamnă soluția care are cele mai puține intrări non-zero, adică cea mai mică $l_0$ -normă. Această problemă este, de obicei, considerată o problemă de optimizare a $l_0$ -normă sau de optimizare $l_0$ .

l0-optimizare

Multe aplicații, inclusiv detecția compresivă, încearcă să minimizeze $l_0$ -norma $l_0$ a unui vector care corespunde unor constrângeri, de aceea se numește „ $l_0$ -minimizare”. O problemă standard de minimizare este formulată ca:

$min \left \| x \right \|_0$ sub rezerva $Ax = b$

Cu toate acestea, a face acest lucru nu este o sarcină ușoară. Din cauza lipsei de reprezentare matematică a normei $l_0$ , $l_0$ -minimizarea este considerată de către informaticieni ca fiind o problemă NP-hard, ceea ce spune pur și simplu că este prea complexă și aproape imposibil de rezolvat.

În multe cazuri, problema de $l_0$ -minimizare este relaxată pentru a fi o problemă de normă de ordin superior, cum ar fi $l_1$ -minimizare și $l_2$ -minimizare.

l1-normă

În urma definiției normei, $l_1$ -norma lui $x$ se definește ca

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

Această normă este destul de comună în familia de norme. Ea are mai multe nume și mai multe forme în diverse domenii, și anume norma Manhattan este porecla sa. Dacă norma $l_1$ este calculată pentru o diferență între doi vectori sau matrici, adică

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

se numește Sum of Absolute Difference (SAD) printre cercetătorii în domeniul vederii computerizate.

În cazul mai general al măsurării diferenței de semnal, aceasta poate fi scalată la un vector unitar prin:

$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 |$ unde $n$ este o mărime de $x$ .

care este cunoscută sub numele de Eroare medie absolută (MAE).

l2-normă

Cea mai populară dintre toate normele este $l_2$ norma. Ea este utilizată în aproape toate domeniile ingineriei și ale științei în ansamblu. Urmărind definiția de bază, $l_2$ -norma se definește ca

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

$l_2$ -norma este bine cunoscută ca normă euclidiană, care este utilizată ca mărime standard pentru măsurarea unei diferențe vectoriale. Ca și în cazul $l_1$ -norma, dacă norma euclidiană este calculată pentru o diferență vectorială, aceasta este cunoscută sub numele de distanță euclidiană:

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

sau în forma sa pătratică, cunoscută sub numele de Sum of Squared Difference (SSD) printre cercetătorii din domeniul viziunii computerizate:

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

Cea mai cunoscută aplicație în domeniul prelucrării semnalelor este măsurarea erorii pătratice medii (Mean-Squared Error – MSE), care este utilizată pentru a calcula o similaritate, o calitate sau o corelație între două semnale. MSE este

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

După cum s-a discutat anterior în secțiunea $l_0$ -optimizare, din cauza multor probleme atât din punct de vedere computațional, cât și matematic, multe probleme de $l_0$ -optimizare se relaxează pentru a deveni în schimb $l_1$ – și $l_2$ -optimizare. Din această cauză, vom discuta acum despre optimizarea $l_2$ .

optimizare

Ca și în cazul optimizării $l_0$ , problema minimizării normei $l_2$ se formulează prin

$min \left \| x \right \|_2$ sub rezerva $Ax = b$

Să presupunem că matricea de constrângeri $A$ are rang complet, această problemă este acum un sistem subdeterminat care are soluții infinite. Scopul în acest caz este de a extrage cea mai bună soluție, adică are cea mai mică $l_2$ -normă, din aceste soluții infinit de numeroase. Aceasta ar putea fi o muncă foarte anevoioasă dacă ar fi calculată direct. Din fericire, există un truc matematic care ne poate ajuta foarte mult în această lucrare.

Cu ajutorul unui truc al multiplicatorilor Lagrange, putem defini apoi un Lagrangian

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

unde $\lambda$ este multiplicatorul Lagrange introdus. Luați derivata acestei ecuații egală cu zero pentru a găsi o soluție optimă și obțineți

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

Conectați această soluție în constrângere pentru a obține

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

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

și în final

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

Cu ajutorul acestei ecuații, putem acum calcula instantaneu o soluție optimă a problemei de optimizare $l_2$ . Această ecuație este binecunoscută sub numele de Pseudoinversul Moore-Penrose, iar problema în sine este de obicei cunoscută sub numele de problemă Least Square, regresie Least Square sau optimizare Least Square.

Cu toate acestea, chiar dacă soluția metodei Least Square este ușor de calculat, nu este necesar să fie cea mai bună soluție. Din cauza naturii netede a normei $l_2$ în sine, este greu de găsit o singură soluție, cea mai bună soluție pentru problemă.

În schimb, optimizarea $l_1$ poate oferi un rezultat mult mai bun decât această soluție.

l1-optimizare

Ca de obicei, problema de $l_1$ -minimizare se formulează ca

$min \left \| x \right \|_1$ sub rezerva $Ax = b$

Pentru că natura normei $l_1$ nu este netedă ca în cazul normei $l_2$ , soluția acestei probleme este mult mai bună și mai unică decât cea a $l_2$ -optimizării.

Cu toate acestea, chiar dacă problema de $l_1$ -minimizare are aproape aceeași formă ca și cea de $l_2$ -minimizare, ea este mult mai greu de rezolvat. Deoarece această problemă nu are o funcție netedă, trucul pe care l-am folosit pentru a rezolva problema $l_2$ nu mai este valabil. Singura modalitate rămasă pentru a-i găsi soluția este să o căutăm direct. Căutarea soluției înseamnă că trebuie să calculăm fiecare soluție posibilă pentru a o găsi pe cea mai bună din fondul de „infinit de multe” soluții posibile.

Din moment ce nu există o modalitate ușoară de a găsi matematic soluția pentru această problemă, utilitatea $l_1$ -optimizării este foarte limitată de zeci de ani. Până de curând, progresul calculatoarelor cu putere mare de calcul ne permite să „măturam” toate soluțiile. Prin utilizarea multor algoritmi utili, și anume algoritmul de optimizare convexă, cum ar fi programarea liniară sau programarea neliniară etc., este acum posibil să se găsească cea mai bună soluție la această întrebare. Multe aplicații care se bazează pe optimizarea $l_1$ , inclusiv detecția compresivă, sunt acum posibile.

Există multe cutii de instrumente pentru optimizarea $l_1$ disponibile în zilele noastre. Aceste seturi de instrumente utilizează de obicei abordări și/sau algoritmi diferiți pentru a rezolva aceeași problemă. Exemplele acestor cutii de instrumente sunt l1-magic, SparseLab, ISAL1,

Acum am discutat mai mulți membri ai familiei de norme, începând cu $l_0$ -normă, $l_1$ -normă și $l_2$ -normă. Este timpul să trecem la următorul. Având în vedere că am discutat încă de la început despre faptul că poate exista orice normă l-ceva care urmează aceeași definiție de bază a normei, va fi nevoie de mult timp pentru a vorbi despre toate acestea. Din fericire, în afară de $l_0$ -, $l_1$ – , și $l_2$ -normă, restul sunt de obicei neobișnuite și, prin urmare, nu au atât de multe lucruri interesante de analizat. Așa că ne vom uita la cazul extrem al normei, care este o $l_{\infty}$ -normă (normă l-infinită).

normă l-infinită

Ca întotdeauna, definiția pentru $l_{\infty}$ -normă este

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

Acum această definiție pare din nou complicată, dar de fapt este destul de directă. Să considerăm vectorul $\boldsymbol{x}$ , să spunem dacă $x_j$ este cea mai mare intrare în vectorul $\boldsymbol{x}$ , prin însăși proprietatea infinitului, putem spune că

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

atunci

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

atunci

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

Acum putem spune pur și simplu că norma $l_{\infty}$ este

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

care este mărimea maximă a intrărilor din acel vector. Acest lucru a demistificat cu siguranță semnificația lui $l_{\infty}$ -norma

Acum am discutat întreaga familie de norme de la $l_0$ la $l_{\infty}$ , sper că această discuție va ajuta la înțelegerea semnificației normei, a proprietăților sale matematice și a implicațiilor sale în lumea reală.

Referințe și lecturi suplimentare:

Norma matematică – wikipedia

Norma matematică – 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) : A corectat inexactități de conținut.

Arquidia Mantina

Arquidia Mantina

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

Lasă un răspuns Anulează răspunsul