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

Sto lavorando molto sulle cose relative alla norma ultimamente ed è ora di parlarne. In questo post parleremo di un’intera famiglia di norme.

Che cos’è una norma?

Matematicamente una norma è una dimensione o lunghezza totale di tutti i vettori in uno spazio vettoriale o matrici. Per semplicità, possiamo dire che più alta è la norma, più grande è il (valore in) matrice o vettore. La norma può avere molte forme e molti nomi, compresi questi nomi popolari: distanza euclidea, errore quadratico medio, ecc.

Il più delle volte vedrete la norma apparire in un’equazione come questa:

dove può essere un vettore o una matrice.

Per esempio, una norma euclidea di un vettore è che è la dimensione del vettore

L’esempio precedente mostra come calcolare una norma euclidea, o formalmente chiamata norma . Ci sono molti altri tipi di norma che vanno oltre la nostra spiegazione qui, in realtà per ogni singolo numero reale, c’è una norma che gli corrisponde (notare la parola enfatizzata numero reale, che significa che non è limitata solo ai numeri interi.)

Formalmente la -norma di è definita come:

dove

Ecco! Una radice p-esima di una sommatoria di tutti gli elementi alla potenza p-esima è ciò che chiamiamo una norma.

Il punto interessante è che anche se ogni -norma è molto simile all’altra, le loro proprietà matematiche sono molto diverse e quindi anche la loro applicazione è drammaticamente diversa. Qui esamineremo alcune di queste norme in dettaglio.

l0-norm

La prima norma che discuteremo è una -norm. Per definizione, la -norma di è

In senso stretto, la -norma non è effettivamente una norma. È una funzione di cardinalità che ha la sua definizione nella forma di -norm, anche se molte persone la chiamano norma. È un po’ complicato lavorarci perché c’è una presenza di zeroth-power e zeroth-root in essa. Ovviamente qualsiasi lo diventerà, ma i problemi della definizione di zeroth-power e soprattutto di zeroth-root stanno incasinando le cose qui. Così, in realtà, la maggior parte dei matematici e degli ingegneri usano invece questa definizione di -norma:

che è un numero totale di elementi non nulli in un vettore.

Perché è un numero di elementi non nulli, ci sono così tante applicazioni che usano -norma. Ultimamente è ancora più a fuoco a causa dell’aumento dello schema Compressive Sensing, che cerca di trovare la soluzione più sparsa del sistema lineare sottodeterminato. La soluzione più spartana significa la soluzione che ha meno voci non nulle, cioè il più basso -norm. Questo problema è di solito considerato come un problema di ottimizzazione della -norma o -ottimizzazione.

l0-ottimizzazione

Molte applicazioni, incluso il Compressive Sensing, cercano di minimizzare la -norma di un vettore corrispondente ad alcuni vincoli, quindi chiamato “-minimizzazione”. Un problema di minimizzazione standard è formulato come:

soggetto a

Tuttavia, farlo non è un compito facile. A causa della mancanza della rappresentazione matematica di -norm, la -minimizzazione è considerata dagli scienziati informatici come un problema NP-hard, semplicemente dice che è troppo complesso e quasi impossibile da risolvere.

In molti casi, il problema di -minimizzazione è rilassato per essere un problema di norma di ordine superiore come -minimizzazione e -minimizzazione.

l1-norm

Seguendo la definizione di norma, -norm di è definito come

Questa norma è abbastanza comune nella famiglia delle norme. Ha molti nomi e molte forme in vari campi, cioè la norma Manhattan è il suo soprannome. Se la norma è calcolata per una differenza tra due vettori o matrici, cioè

viene chiamata Somma delle differenze assolute (SAD) tra gli scienziati di computer vision.

Nel caso più generale della misurazione della differenza del segnale, può essere scalata ad un vettore unitario da:

dove è una dimensione di .

che è conosciuta come Mean-Absolute Error (MAE).

l2-norm

La più popolare di tutte le norme è la -norm. È usata in quasi tutti i campi dell’ingegneria e della scienza in generale. Seguendo la definizione di base, la -norma è definita come

-norma è ben nota come una norma euclidea, che è usata come una quantità standard per misurare una differenza vettoriale. Come nella norma , se la norma euclidea è calcolata per una differenza vettoriale, è nota come distanza euclidea:

o nella sua forma quadrata, nota come Somma delle differenze quadrate (SSD) tra gli scienziati di Computer Vision:

La sua applicazione più nota nel campo dell’elaborazione dei segnali è la misura dell’errore quadratico medio (MSE), che è usata per calcolare una somiglianza, una qualità o una correlazione tra due segnali. MSE è

Come precedentemente discusso nella sezione -ottimizzazione, a causa di molti problemi sia da un punto di vista computazionale che matematico, molti problemi di -ottimizzazione si rilassano per diventare invece – e -ottimizzazione. A causa di questo, discuteremo ora dell’ottimizzazione di .

l2-ottimizzazione

Come nel caso di -ottimizzazione, il problema di minimizzare -norm è formulato da

soggetto a

Assumiamo che la matrice di vincolo abbia pieno rango, questo problema è ora un sistema sottosoglia che ha infinite soluzioni. L’obiettivo in questo caso è quello di estrarre la soluzione migliore, cioè quella con la norma più bassa, da queste infinite soluzioni. Questo potrebbe essere un lavoro molto noioso se dovesse essere calcolato direttamente. Per fortuna c’è un trucco matematico che può aiutarci molto in questo lavoro.

Utilizzando un trucco dei moltiplicatori di Lagrange, possiamo quindi definire una lagrangiana

dove è il moltiplicatore di Lagrange introdotto. Prendiamo la derivata di questa equazione uguale a zero per trovare una soluzione ottimale e otteniamo

Inseriamo questa soluzione nel vincolo per ottenere

e infine

Con questa equazione, possiamo ora calcolare istantaneamente una soluzione ottimale del problema di ottimizzazione . Questa equazione è ben nota come la pseudoinversa di Moore-Penrose e il problema stesso è solitamente noto come problema del Least Square, regressione Least Square o ottimizzazione Least Square.

Tuttavia, anche se la soluzione del metodo Least Square è facile da calcolare, non è necessariamente la soluzione migliore. A causa della natura liscia della -norm stessa, è difficile trovare un’unica, migliore soluzione per il problema.

Al contrario, l’ottimizzazione può fornire un risultato molto migliore di questa soluzione.

l1-ottimizzazione

Come al solito, il problema di -minimizzazione è formulato come

soggetto a

Perché la natura della -norm non è liscia come nel caso della -norm, la soluzione di questo problema è molto migliore e più unica della -ottimizzazione.

Tuttavia, anche se il problema della -minimizzazione ha quasi la stessa forma della -ottimizzazione, è molto più difficile da risolvere. Poiché questo problema non ha una funzione liscia, il trucco che abbiamo usato per risolvere il problema non è più valido. L’unico modo rimasto per trovare la sua soluzione è di cercarla direttamente. Cercare la soluzione significa che dobbiamo calcolare ogni singola soluzione possibile per trovare la migliore dal pool di “infinitamente molte” soluzioni possibili.

Non essendoci un modo facile per trovare matematicamente la soluzione di questo problema, l’utilità dell’ottimizzazione è stata molto limitata per decenni. Fino a poco tempo fa, l’avanzamento dei computer ad alta potenza di calcolo ci permette di “spazzare” tutte le soluzioni. Utilizzando molti algoritmi utili, in particolare l’algoritmo di ottimizzazione convessa come la programmazione lineare, o la programmazione non lineare, ecc. Molte applicazioni che si basano sull’ottimizzazione , incluso il Compressive Sensing, sono ora possibili.

Ci sono molti toolbox per l’ottimizzazione oggi disponibili. Questi toolbox di solito usano diversi approcci e/o algoritmi per risolvere la stessa questione. Gli esempi di questi toolbox sono l1-magic, SparseLab, ISAL1,

Ora che abbiamo discusso molti membri della famiglia delle norme, a partire da -norm, -norm, e -norm. È ora di passare al prossimo. Dato che abbiamo discusso all’inizio che ci può essere qualsiasi norma l-qualunque cosa che segua la stessa definizione di base di norma, ci vorrà molto tempo per parlare di tutte. Fortunatamente, a parte -, – , e -norm, le altre di solito non sono comuni e quindi non hanno così tante cose interessanti da vedere. Quindi guarderemo il caso estremo di norma che è una -norma (norma di l-infinito).

norma di l-infinito

Come sempre, la definizione di -norma è

Ora questa definizione sembra di nuovo complicata, ma in realtà è abbastanza semplice. Consideriamo il vettore , diciamo che se è la voce più alta nel vettore , per la proprietà dell’infinito stesso, possiamo dire che

allora

allora

Ora possiamo semplicemente dire che la -norma è

che è la grandezza massima delle voci di quel vettore. Questo ha sicuramente demistificato il significato di -norm

Ora abbiamo discusso l’intera famiglia della norma da a , spero che questa discussione possa aiutare a capire il significato della norma, le sue proprietà matematiche e le sue implicazioni nel mondo reale.

Riferimenti e ulteriori letture:

Norma matematica – wikipedia

Norma matematica – MathWorld

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

Programmazione lineare – MathWorld

Rilevamento compressivo – Rice University

Edit (15/02/15) : Corrette imprecisioni del contenuto.