Compressed sensing per applicazioni sismiche

(1)

Scuola di Ingegneria Industriale e dell’Informazione

Corso di Laurea Specialistica in Ingegneria Matematica

COMPRESSED SENSING

PER APPLICAZIONI SISMICHE

Relatore: Prof. Luca Formaggia Correlatore: Dott. Paolo Ferrandi

Candidato:

Pietro Andrea Mariani Matricola 739267

(2)

Il modello attualmente di maggiore interesse nella teoria dei segnali `e costi-tuito dalla rappresentazione sparsa e ridondante del segnale. In particolare, questo modello ha un grande impatto nel campo dell’acquisizione del segna-le, fornendo le basi per il paradigma del compressed sensing.

L’applicazione del modello di segnale sparso si estende alla quasi totalità delle operazioni di trattamento dei segnali, tuttavia conduce a numerose problematiche teoriche e numeriche legate alla ricerca della rappresentazio-ne sparsa e ridondante di un segnale, in quanto è richiesta la soluziorappresentazio-ne di un sistema di equazioni lineari sottodeterminato che, grazie all’ipotesi di spar-sità, può essere affrontato come un problema di ottimizzazione non lineare e NP-hard, la cui risoluzione attraverso una ricerca esaustiva è impraticabile in problemi di interesse ingegneristico.

Dai recenti sviluppi della teoria sono emersi risultati che garantiscono la possibilità di calcolare la soluzione per mezzo di un problema rilassato più semplice da trattare, ad esempio un problema di minimizzazione vincolato in norma ℓ1, per il quale la ricerca della soluzione è affrontabile nella pratica.

Scopo della tesi `e l’implementazione di una libreria di solutori per la ricerca della rappresentazione sparsa e ridondante di un segnale e il suo utilizzo per affrontare il problema della ricostruzione di tracce mancanti nell’ambito dell’acquisizione di dati per l’esplorazione sismica.

(3)

1 Introduzione 6

2 Basi teoriche e propriet`a degli algoritmi 9

2.1 Sparsit`a e comprimibilit`a . . . 9

2.2 Soluzioni sparse di sistemi di equazioni lineari . . . 11

2.2.1 Unicit`a . . . 12

2.2.2 Unicit`a dal principio di indeterminazione . . . 14

2.2.3 Soluzioni approssimate . . . 15

2.2.4 Propriet`a di isometria ristretta . . . 16

2.3 Algoritmi . . . 17

2.3.1 Algoritmi greedy . . . 17

2.3.2 Tecniche di rilassamento convesso . . . 19

2.3.3 Metodi iterative shrinkage . . . 22

2.3.4 L’algoritmo spectral projected gradient . . . 24

2.3.5 Metodo di proiezione . . . 26

2.3.6 Propriet`a del problema duale . . . 26

2.3.7 Metodo di Newton inesatto . . . 28

3 La libreria SparseModeling 31 3.1 Implementazione della libreria . . . 31

3.1.1 Design basato sulle policies . . . 32

3.1.2 Traits . . . 33 3.2 Solutori iterativi . . . 34 3.3 Metodi implementati . . . 35 3.3.1 Operatori . . . 36 4 Validazione 39 4.1 La suite Sparco . . . 39

4.2 Risultati dei test . . . 41

5 Applicazione all’esplorazione sismica 57 5.1 Ricostruzione di dati sismici . . . 58

6 Conclusioni 64

(4)

4.1 Segnali trattati nel problema 2. . . 43

5.1 Common shot gather da un rilievo in acque profonde. . . 60

5.2 Andamento dei 100000 coefficienti pi`u significativi della tra-sformata curvelet del common shot gather. . . 60

5.3 Ricostruzione delle tracce mancanti di uno shot gather. . . . 62

(5)

4.1 Tipi di operatore utilizzati nei test. . . 40

4.2 Caratteristiche dei problemi. . . 40

4.3 Caratteristiche della soluzione nel caso σ = σ1 . . . 41

4.4 Caratteristiche della soluzione nel caso σ = σ2 . . . 42

4.5 Tempi di esecuzione in secondi per la soluzione dei problemi. 43 5.1 Caratteristiche delle soluzioni. . . 61

(6)

Introduzione

L’uso della modellistica matematica per la descrizione dei dati è fondamen-tale nella teoria dei segnali, in quanto i modelli di segnale sono utilizzati nella quasi totalità delle operazioni di elaborazione. Ad esempio, il cam-pionamento di un segnale si basa su assunzioni riguardo al suo contenuto per garantire una limitata perdita di informazione, la compressione di un segnale è possibile solo grazie alla capacità di un modello di descriverlo con pochi parametri, la separazione di segnali sovrapposti si effettua grazie a modelli delle diverse componenti, infine la risoluzione di problemi inversi, quali la ricostruzione tomografica da sezioni, la tecnica di super risoluzio-ne, l’inpainting, l’estrapolazione di un segnale e il deblurring, si basa su un modello di segnale per regolarizzare un processo di inversione generalmente mal posto.

Il modello attualmente di maggior interesse `e costituito dalla rappresenta-zione sparsa e ridondante del segnale o modello sparseland. Tale modello si basa sulla ricerca di una rappresentazione x ∈ Rn_{di un segnale y ∈ R}m_tale

che y = Dx, con x sparso, cioè con pochi elementi non nulli, e ridondante, cioè tale che n > m, e con D ∈ Rm×nmatrice di rango pieno, detta diziona-rio. Il concetto di sparsità del segnale sarà trattato in dettaglio nel Capitolo 2.

Il modello sparseland, oltre ad introdurre idee innovative ed applicazioni in-gegneristiche, conduce ad una serie di problematiche teoriche e numeriche, in quanto il calcolo della rappresentazione sparsa x richiede la risoluzione di un problema di minimizzazione rispetto al numero di elementi non nulli di x, che è di natura non lineare e NP-hard. La garanzia sull’unicità della solu-zione e sulla possibilità di ricavarla è fornita da alcuni risultati che saranno riportati, accompagnati da una serie di algoritmi per calcolarla; tuttavia, sono ancora numerose le questioni aperte, riassunte in [20], in quanto la ri-cerca nel campo della rapparesentazione sparsa e ridondante del segnale è ancora ai suoi albori: l’ampio lavoro di ricerca negli anni dal 1980 al 2000 sulle trasformate e sulla teoria dei frames [13] ha contribuito a prepararne

(7)

le basi, mentre dopo il 1990 i lavori [12], [32] e [34] hanno dato inizio alla ricerca sui modelli sparsi e ridondanti di segnale. A partire dall’articolo del 2001 di Donoho e Huo [18] si `e sviluppata la parte pi`u consistente di ricerca nel campo.

L’applicazione del modello sparso e ridondante del segnale nel contesto del campionamento `e detto compressed sensing o, in alternativa, compressive sensing, compressive sampling o sparse recovery. Si tratta dell’ambito ap-plicativo attualmente di maggior impatto per tale modello, al punto tale che spesso si identifica con il termine compressed sensing l’intero campo della rappresentazione sparsa e ridondante del segnale.

La teoria del compressed sensing differisce dalla teoria classica del campiona-mento in tre aspetti: il campionacampiona-mento classico tratta segnali di lunghezza infinita a tempo continuo, mentre il compressed sensing considera segnali di dimensione finita; il secondo aspetto è il passaggio da un campionamento in istanti specifici del tempo o dello spazio ad una più generale acquisizione sotto forma di prodotti interni con funzioni test, nella definizione delle qua-li la teoria delle probabiqua-lità svolge un ruolo fondamentale. Infine, l’aspetto della ricostruzione, che nella teoria classica è costituito da un processo linea-re, l’interpolazione seno cardinale, nel compressed sensing è costituito dalla ricerca della soluzione sparsa di un sistema sottodeterminato, problema non lineare e NP-hard.

Il vantaggio del nuovo approccio è la possibilità di ridurre le misure neces-sarie per la corretta ricostruzione del segnale rispetto a quelle effettuate nei campionamenti basati sulla teoria classica, da cui il nome compressed sen-sing. Nella teoria classica, il numero di campionamenti è determinato dal teorema di Shannon-Nyquist, che garantisce una ricostruzione esatta se il segnale è campionato in punti equispaziati ad una frequenza maggiore del doppio della frequenza massima del segnale.

Nonostante il compressed sensing sia una teoria recente, sviluppatasi a par-tire dal 2006 dai lavori [8], [10], [16] di Candès, Romberg, Tao e Donoho, le prime intuizioni sulla possibilità di ricostruire il segnale da pochi campioni e sugli algoritmi per la ricostruzione di segnali sparsi sono antecedenti al teorema di Nyquist-Shannon. Nel 1795 Prony ha proposto un metodo per ricavare i parametri di una somma di esponenziali a partire da campioni equispaziati. Successivamente Carathéodory, all’inizio dell XX secolo, ha dimostrato che una combinazione lineare positiva di k sinusoidi è univoca-mente determinata dal suo valore per t = 0 e da 2k altri punti qualsiasi, cioè un numero di campioni che non rispetta il criterio di Nyquist se l’intervallo di frequenze delle sinusoidi è ampio. A partire dal 1990, questa teoria è stata generalizzata nel campo dell’imaging biomagnetico e in altri contesti ed è stato proposto uno schema di acquisizione per alcune classi di segnali, ma senza garanzie sulla possibilità di ricostruzione nel caso generale. All’ini-zio del decennio successivo, Blu, Marziliano e Vetterli hanno sviluppato dei metodi di acquisizione per alcune classi di segnali parametrici, governati da

(8)

k parametri, mostrando che possono essere ricostruiti a partire da 2k cam-pioni. Infine, l’approccio proposto da Beurling nel 1938 alla ricostruzione di un segnale a partire da un’osservazione parziale della sua trasformata di Fourier, basato sulla minimizzazione in norma ℓ1, `e molto simile ad alcuni

algoritmi utilizzati per la ricostruzione del segnale nel compressed sensing. Un campo che può trarre grandi benefici dall’utilizzo del modello sparseland è quello dell’esplorazione sismica. Essa si occupa dell’indagine del sottosuo-lo mediante sottosuo-lo studio della propagazione di onde meccaniche al suo interno e richiede numerose procedure di elaborazione del segnale. La riduzione di dimensionalità dei dati per mezzo del compressed sensing potrebbe essere lo strumento adatto per superare il principale ostacolo alla costruzione di immagini del sottosuolo ad una risoluzione più alta, costituito dall’enorme mole di dati che il rispetto del criterio di Nyquist richiede di acquisire ed elaborare [31].

Questo lavoro di tesi ha come obiettivo la realizzazione di una libreria C++ che implementi gli algoritmi per la risoluzione del problema della ricerca della rappresentazione sparsa di un segnale, alla base di qualunque appli-cazione che sfrutti il modello sparseland e, in particolare, del compressed sensing. Il secondo obiettivo è la risoluzione di un problema di ricostruzione di dati mancanti nel campo dell’esplorazione sismica, utilizzando il modello sparso e ridondante di segnale e la libreria implementata. I contenuti della tesi sono organizzati in cinque capitoli, successivi a questa introduzione. Il Capitolo 2 introduce i concetti di vettore sparso e comprimibile ed espone i risultati fondamentali che garantiscono la possibilità di risolvere il proble-ma della ricerca della rappresentazione sparsa di un segnale. La seconda parte del capitolo descrive alcuni algoritmi che permettono di calcolare la soluzione del problema e le loro proprietà.

Il Capitolo 3 descrive la libreria SparseModeling, implementata in questo lavoro di tesi, le esigenze a cui vuole rispondere e le tecniche di programma-zione utilizzate.

Il Capitolo 4 espone i risultati dei test eseguiti per la validazione della libre-ria ed un confronto con il software Matlab SPGL1.

Il Capitolo 5 descrive brevemente il metodo dell’esplorazione sismica ed i benefici che esso pu`o trarre dall’utilizzo del modello sparso e ridondante del segnale. Sono, poi, riportati i risultati ottenuti utilizzando il modello e la libreria per risolvere il problema della ricostruzione di tracce mancanti nel processo di acquisizione di dati sismici.

Infine, il Capitolo 6 riporta le conclusioni sul lavoro svolto e le ipotesi su possibili sviluppi futuri.

(9)

Basi teoriche e propriet`

a

degli algoritmi

In questo capitolo saranno introdotte le nozioni e i teoremi fondamentali nel campo della rappresentazione sparsa e ridondante dei segnali, per segnali discreti finiti, trattabili come vettori di Rn. Saranno date le definizioni di sparsità e di comprimibilità per un vettore, saranno poi formulati i proble-mi della risoluzione di un sistema sottodeterproble-minato e di ottiproble-mizzazione che è necessario affrontare in questo ambito ed illustrati i principali risultati che garantiscono la possibilità di risolverli. Infine, saranno descritti alcuni algoritmi per la risoluzione dei problemi introdotti.

2.1 Sparsit`

a e comprimibilit`

a

Una semplice ed intuitiva misura della sparsit`a di un vettore x consiste nel conteggio degli elementi non nulli di x mediante la funzione

kxk0= # {i : xi 6= 0} , (2.1)

detta “norma” ℓ0, sebbene non soddisfi la condizione di omogeneit`a. Il

vettore è sparso se gli elementi non nulli sono pochi rispetto al totale: un vettore x ∈ Rn si definisce s-sparso, se ha al massimo s elementi non nulli, cioè se kxk0≤ s. La definizione di sparsità basata sulla “norma” ℓ0 appena

introdotta è difficilmente applicabile nella pratica, in quanto raramente un vettore di dati reali può essere rappresentato da un vettore di coefficienti contenenti molti valori esattamente nulli, ad esempio per la presenza di ru-more, quindi è utile costruire nozioni di sparsità più deboli, come il concetto di comprimibilità.

Si definiscano, anzitutto, le norme ℓp per p ∈ [1, ∞) e le quasi-norme ℓp per

p ∈ (0, 1) come kxkp = X i |xi|p !1/p (2.2)

(10)

e, a partire da esse, l’errore ℓp di migliore approssimazione a s termini:

σs(x)p= inf kzk0≤s

kx − zkp. (2.3)

Un vettore `e detto comprimibile, se il suo errore ℓp di migliore

approssima-zione a s termini decresce rapidamente all’aumentare di s, cio`e se

σs(x)p ≪ 1 per s ≪ n. (2.4)

In particolare, ci`o avviene per i vettori appartenenti ad una palla ℓp, con

p ∈ (0, 1), di raggio r adeguatamente piccolo, definita come

B_pn_{(r) = {x ∈ R}n_{, kxk}p ≤ r}, (2.5)

infatti in [24] si dimostra che per ogni q > p > 0 ed ogni x ∈ Rn vale la disuguaglianza σs(x)q≤ cp,q s1/p−1/qkxkp, con cp,q= " p q p/q 1 −p_q 1−p/q# ≤ 1 (2.6) Un modo alternativo per definire la comprimibilità è legato alla rapidità di decrescita degli elementi del vettore. Siano xi gli elementi del vettore x

ordinati in modo tale che |x1| ≥ |x2| ≥ · · · ≥ |xn|: se esistono due costanti

K, α > 0 tali che

|xi| ≤ Ki−α per i = 1, . . . , n, (2.7)

gli elementi decrescono con legge di potenza. In [15] si mostra che, essendo C1, C2, r > 0, σs(x)2 ≤ C1s−r (2.8) se e solo se |xs| ≤ C2s−r− 1 2, (2.9)

quindi maggiore è il valore di r, più rapidamente decresce la successione {σs(x)2}s=1,...,n, cioè più il vettore è comprimibile.

Indicando con

N (ǫ, x) = # {i : |xi| > ǫ} (2.10)

il numero di elementi di x il cui valore assoluto eccede un ǫ fissato, è possibile dare un’altra definizione di comprimibilit`_{a: il vettore x ∈ R}n comprimibile se il numero dei suoi elementi significativamente diversi da 0 è piccolo, cioè se

N (ǫ, x) ≪ n, (2.11)

per un ǫ adeguato. Questa definizione porta all’introduzione delle quasi-norme ℓp-deboli, per p > 0:

kxkwℓp= sup

ǫ>0 ǫ · N (ǫ, x)

1

(11)

da cui si ricava facilmente la disuguaglianza N (t, x) ≤ kxkpwℓpt

−p _{per t > 0,} _(2.13)

che permette di affermare che un vettore con norma ℓp-debole piccola avr`a

pochi elementi significativi e di conseguenza sar`a sparso secondo la definizio-ne (2.11). Inoltre, per le quasi-norme ℓp-deboli vale la seguente

disuguaglian-za, dimostrata in [24], che le lega alle corrispondenti norme o quasi-norme ℓp:

kxkwℓp≤ kxkp, (2.14)

dove l’uguaglianza vale per i vettori in cui il modulo degli elementi non nulli ha per tutti lo stesso valore assoluto. Vale, infine, un risultato analogo al (2.6): per ogni q > p > 0 ed ogni x ∈ Rn vale la disuguaglianza

σs(x)q ≤ dp,q s1/p−1/qkxkwℓp, con dp,q= p q − p 1/q (2.15) per cui se un vettore `e considerato comprimibile secondo la definizione (2.11), lo sar`a anche secondo la definizione (2.4).

2.2 Soluzioni sparse di sistemi di equazioni lineari

Il problema della ricerca della rappresentazione sparsa e ridondante di un segnale richiede la risoluzione di un sistema di equazioni lineari sottodeter-minato. Si consideri una matrice di rango pieno A ∈ Rm×n con m < n e si definisca il sistema sottodeterminato di equazioni lineari Ax = b. Questo sistema ha infinite soluzioni, quindi se si desidera individuare una particolare soluzione sono necessari criteri addizionali. Un metodo usuale è introdurre una funzione J (x) per valutare la desiderabilità della candidata soluzio-ne x, dove i valori più piccoli sono preferiti. Si definisca il problema di ottimizzazione:

min

x J (x) subject to b = Ax. (2.16)

La scelta di una funzione J (·) strettamente convessa garantisce l’unicit`a della soluzione, ad esempio come nel noto caso

min

x kxk 2

2 subject to b = Ax, (2.17)

in cui la funzione obiettivo da minimizzare `e il quadrato della norma eucli-dea J(x) = kxk22.

Sfruttando, invece, l’ipotesi di segnale sparso, si pu`o porre come funzio-ne obiettivo del problema (2.16) una delle funzioni introdotte funzio-nella seziofunzio-ne precedente, ad esempio la “norma” ℓ0definita in (2.1), ottenendo il problema

min

(12)

simile nella notazione al problema della minimizzazione della norma ℓ2. In

realt`a i due problemi differiscono in modo significativo: grazie all’analisi convessa, si mostra che la soluzione ˆxdi (2.17) `e sempre unica e agevolmente calcolabile in modo esplicito:

ˆ

x= AT AAT−1

b, (2.19)

mentre l’analisi del problema (2.18) non pu`o contare su tali strumenti, data la natura discreta e discontinua della “norma” ℓ0. Nel caso generale, (2.18)

è un problema di ricerca combinatoria, inoltre in [24] si dimostra che è NP-hard. Se si tenta di risolvere il problema con una ricerca esaustiva su tutti i sottoinsiemi di colonne di A, si ottiene un metodo di complessità esponenziale in n.

Nelle prossime sezioni saranno presentati alcuni risultati di unicit`a per la soluzione del problema e alcuni metodi per calcolarla, di complessit`a inferiore rispetto alla ricerca esaustiva.

In alternativa, si pu`o utilizzare come funzione obiettivo J(x) una delle norme ℓp descritte precedentemente, con p ∈ (0, 1]: anche questa scelta favorisce la

sparsit`a della soluzione del problema (2.16). Questa tendenza si pu`o spiegare considerando il problema

min

x kxk p

p subject to b= Ax, (2.20)

i cui vincoli definiscono un insieme di soluzioni ammissibili in un sottospazio affine. Se si considera la pi`u piccola sfera ℓp che intersechi il sottospazio, il

punto di intersezione tende ad essere in corrispondenza degli assi del sistema di riferimento, cio`e la soluzione del problema (2.20) tende ad essere sparsa. Si osservi che la scelta di p ∈ (0, 1) porta ad un problema di ottimizzazione non convessa, difficile da risolvere nel caso generale. Per p = 1 si ha, inve-ce, un problema di ottimizzazione convessa, che verr`a trattato nelle sezioni successive.

Infine, vi sono altre funzioni che promuovono la sparsit`a altrettanto be-ne, come le quasi-norme ℓp-deboli, per p ∈ (0, 1], e quelle della forma

J(x) =P

iρ(xi), con ρ(x) simmetrica, monotona non decrescente e con

de-rivata monotona non crescente per x ≥ 0. Appartengono a questa famiglia, ad esempio, ρ(x) = 1 − exp(|x|), ρ(x) = log(1 + |x|) e ρ(x) = |x|/(1 + |x|). 2.2.1 Unicit`a

Una proprietà fondamentale per lo studio dell’unicità della soluzione del problema (2.18) è lo spark. Lo spark di una matrice A è il più piccolo numero positivo di colonne di A che sono linearmente dipendenti:

spark (A) = min

(13)

Si tratta di un concetto simile al rango, ma è più difficile da calcolare, poiché richiede una ricerca combinatoria su tutti i possibili sosttoinsiemi di colonne di A. Grazie allo spark si ottiene un semplice criterio per l’unicità di soluzioni sparse:

Teorema 1.

Se un sistema di equazioni lineari Ax = b ha una soluzione x tale che kxk0 < spark(A)/2, allora questa soluzione `e la pi`u sparsa possibile.

Questo risultato, dimostrato nel capitolo 2 di [19], è molto interessante, in quanto permette di verificare l’ottimalità globale, mentre solitamente nei problemi di ottimizzazione combinatoria ci si accontenta di verificare l’otti-malità locale. Lo spark di una matrice è incluso nell’intervallo [1, m + 1] e assume valore 1 solo se è presente una colonna nulla. Un valore elevato dello spark molto utile: ad esempio per una matrice A con elementi casuali, indi-penti e identicamente distribuiti, si ha con probabilità 1 spark(A) = m + 1, cioè nessun insieme di al più m colonne è linearmente dipendente, mentre esiste almeno un insieme di m + 1 colonne linearmente dipendenti. In questo caso, grazie al teorema 1 per una soluzione con al più m/2 elementi non nulli è garantita l’unicità.

Dato che la difficoltà nel calcolare lo spark è paragonabile a quella del pro-blema (2.18), è interessante cercare altri criteri più semplici per garantire l’unicità, ad esempio sfruttando la mutua coerenza della matrice A.

Sia ak la k-esima colonna della matrice A, che assumiamo essere priva di

colonne nulle, la mutua coerenza `e data da:

µ (A) = max 1≤k, j≤n, k6=j aT_kaj kakk2· kajk₂ (2.22) La mutua coerenza è un modo per caratterizare la dipendenza tra le co-lonne della matrice A e assume valori in [0, 1]. In generale, per matrici con più colonne che righe (n > m), µ è strettamente positiva ed è limitata inferiormente da

µ ≥ r

n − m

m(n − 1). (2.23)

I valori più desiderabili per la mutua coerenza sono i più piccoli, in modo che la matrice abbia caratteristiche simili ad una matrice unitaria, in cui la mutua coerenza è nulla grazie all’ortogonalità tra le colonne. Si può mostrare che per ogni matrice A ∈ Rm×n, vale la relazione

spark (A) ≥ 1 + 1

µ (A), (2.24)

grazie alla quale si ottiene un teorema analogo al teorema 1, dimostrato nel capitolo 2 di [19]:

(14)

Teorema 2.

Se un sistema di equazioni lineari Ax = b ha una soluzione x tale che kxk0 < 12(1 + 1/µ(A)), allora questa soluzione `e la pi`u sparsa possibile.

Confrontando i teoremi 1 e 2 si osserva che il primo è molto più potente del secondo, poichè la mutua coerenza è un minorante dello spark : la mutua coerenza non è mai minore di 1/√m (questo valore è assunto per matrici particolari, ad esempio da quella formata dalla matrice identità e dalla ma-trice di Fourier affiancate orizzontalmente), quindi nel secondo teorema non si avrà mai un’ipotesi meno restrittiva di kxk0 < √m/2, mentre lo spark

potrebbe essere facilmente circa m e, conseguentemente, l’ipotesi del primo teorema kxk0< m/2.

2.2.2 Unicit`a dal principio di indeterminazione

Si consideri una matrice A ∈ Rm×2m formata da due blocchi A1, A2 ∈

Rm×m affiancati orizzontalmente:

A= [A1A2]. (2.25)

Nel caso particolare in cui A1 e A2 sono due matrici ortogonali, vale un

risultato di unicità più forte rispetto al caso generale e lo stesso avviene per i risultati di equivalenza che verranno mostrati in seguito, inoltre, il caso in cui A1 e A2 sono rispettivamente la matrice identità e la matrice di

Fou-rier fu il primo ad essere studiato. In questo contesto, l’indeterminatezza del sistema Ax = b può essere interpretata come la possibilità di rappre-sentare in diversi modi il segnale dato b come sovrapposizione di alcune sinusoidi (colonne dalla matrice di Fourier) e alcuni picchi (colonne dalla matrice identità). L’unicità della soluzione del sistema con A = [I F], dove I è la matrice identità e F la matrice di Fourier, può essere interpretata come l’impossibilità di rappresentare un segnale in modo sparso sia in tem-po che in frequenza, infatti il risultato di unicità discende da un principio di indeterminazione. Si consideri un vettore non nullo y ∈ Rn_{: esso può}

essere rappresentato come combinazione lineare delle colonne di una base ortonormale Ψ o di un’altra base ortonormale Φ

y= Ψα = Φβ, (2.26)

dove i vettori α e β sono determinati in modo univoco. Definita A = [Ψ Φ], come dimostrato nel capitolo 2 di [19], vale la disuguaglianza

kαk0+ kβk0≥

2

µ(A), (2.27)

detta principio di indeterminazione, che permette di affermare che se la mutua coerenza di A `e piccola, allora α e β non possono essere entrambi

(15)

sparsi. In particolare, nel caso con Ψ = I e Φ = F la mutua coerenza vale 1/√m e, quindi, la rappresentazione in tempo e in frequenza non potranno essere entrambe sparse.

Sempre nel capitolo 2 di [19], a partire dalla disuguaglianza (2.27) si ottiene il teorema di unicit`a

Teorema 3.

Se un sistema di equazioni lineari Ax = b, in cui A = [A1A2], con

A1, A2 ∈ Rm×m matrici ortogonali, ha una soluzione x tale che kxk₀ <

1/µ(A), allora questa soluzione `e la pi`u sparsa possibile.

Grazie alla particolare struttura di A, il teorema 3 ha una condizione meno restrittiva rispetto a quella del teorema 2.

2.2.3 Soluzioni approssimate

Il problema (2.18) può essere rilassato sostituendo il vincolo esatto Ax = b con un’approssimazione in cui l’errore è misurato dalla funzione di pena-lità quadratica Q(x) = kAx − bk22. Si definisce il problema rilassato con

tolleranza δ > 0: min

x kxk0 subject to kb − Axk2≤ δ. (2.28)

Il rilassamento del problema permette di definire una quasi-soluzione nei casi in cui non esistono soluzioni del problema esatto, di sfruttare gli strumenti della programmazione matematica e di misurare la qualit`a di una candidata soluzione. La norma ℓ2, usata per misurare l’errore b − Ax, pu`o essere

so-stituita da altre funzioni, ad esempio le norme ℓ1, ℓ∞o la norma ℓ2 pesata.

Un’interpretazione naturale del problema (2.28) `e quello dell’eliminazione del rumore. Si consideri un vettore sparso x0 e sia b = Ax0 + z, dove il

vettore del rumore z ha energia finita kzk22 = δ2: l’obiettivo del problema

(2.28) `e trovare x0, come farebbe il problema (2.18) nel caso senza

rumo-re b = Ax0. Nell’analisi del problema rilassato, invece dell’unicit`a della

soluzione, se ne richiede la stabilità, cioè la garanzia che se si trova una soluzione sufficientemente sparsa, allora le soluzioni alternative saranno in un suo intorno. La stabilità è garantita dal seguente teorema dimostrato in [17]:

Teorema 4.

Si consideri un’istanza del problema (2.28), definita dalla terna (A, b, δ). Sia x0 ∈ Rn un vettore che soddisfa il vincolo di sparsit`a kx0k0 < 12(1 +

1/µ(A)) e fornisce una rappresentazione di b con una tolleranza dell’errore kb − Ax0k2≤ δ, allora ogni soluzione xδ0 di (2.28) soddisfa

kxδ0− x0k22 ≤

4δ2

1 − µ (A) (2kx0k0− 1)

. (2.29)

(16)

2.2.4 Propriet`a di isometria ristretta

I teoremi che garantiscono l’unicità o la stabilità della soluzione enunciati nelle sezioni precedenti si possono ricavare anche a partire da una diffe-rente proprietà della matrice A del problema, detta proprietà di isometria ristretta. La proprietà di isometria ristretta è simile alla mutua coerenza, ma considera gruppi di colonne della matrice, anzichè solamente coppie: per una matrice A ∈ Rm×n, con colonne di norma ℓ2 unitaria, si definisce la

s-esima costante di isometria ristretta δs(A) come il pi`u piccolo δ ≥ 0 tale

che

∀v ∈ Rn, kvk0≤ s (1 − δs)kvk22 ≤ kAvk22 ≤ (1 + δs)kvk22 (2.30)

Se la s-esima costante di isometria ristretta δs `e piccola per s

ragionevol-mente grande, allora informalragionevol-mente si dice che A soddisfa la propriet`a di isometria ristretta. Grazie alla propriet`a di isometria ristretta, nel capitolo 5 di [19], si ricava un risultato analogo al teorema 4

Teorema 5.

Si consideri un’istanza del problema (2.28), definita dalla terna (A, b, δ). Sia x0 ∈ Rn un vettore tale che kx0k0 < s e fornisce una rappresentazione

di b con una tolleranza dell’errore kb − Ax0k2 ≤ δ. Se δ2s(A) < 1 allora

ogni soluzione xδ₀ di (2.28) soddisfa kxδ0− x0k22 ≤

4δ2 1 − δ2s

. (2.31)

La stima fornita dal teorema 5 `e migliore di quella del teorema 4, in quanto nel capitolo 6 di [24] si mostra che

δs(A) ≤ (s − 1)µ(A) per s ≥ 2. (2.32)

Applicando il teorema 5 al caso con δ = 0, cio`e al problema (2.18), si ricava l’unicit`a di una soluzione x0 tale che kx0k0≤ s.

La propriet`a di isometria ristretta e la mutua coerenza saranno utilizzate nelle sezioni successive per ottenere delle garanzie sulla possibilit`a di cal-colare la soluzione dei problemi (2.18) e (2.28) applicando gli algoritmi che saranno introdotti.

(17)

2.3 Algoritmi

Il calcolo della soluzione del problema (2.18) richiede l’utilizzo di metodi specifici, che saranno presentati in questa sezione. Si consideri un problema di tipo (2.18), tale che spark(A) > 2, con soluzione x0 tale che kx0k0 = 1:

in questo caso b `e un multiplo scalare di una colonna di A. Tale colonna pu`o essere individuata eseguendo un test per ogni colonna della matrice A, si ha quindi un metodo dell’ordine di O(mn) operazioni. Si consideri ora una matrice A tale che spark(A) > 2k0 e un problema con soluzione tale che

kx0k0 = k0: b `e una combinazione lineare di k0 colonne di A. Replicando il

metodo precedente, si potrebbe tentare di enumerare tutti i _kn

0 = O(n

k0₎

sottoinsiemi di k0 colonne di A e testarli. L’enumerazione dei sottoinsiemi

`e dell’ordine di O(nk0_mk2

0) operazioni, nella maggior parte dei casi troppo

elevato per essere applicabile. La strategia della ricerca esaustiva va quindi scartata.

2.3.1 Algoritmi greedy

Una possibile strategia alternativa `e quella degli algoritmi greedy, in cui si cerca la soluzione ottima globale scegliendo la soluzione ottima locale ad ogni passo dell’algoritmo. Un esempio di algoritmo di questo tipo `e l’orthogonal matching pursuit (OMP): partendo dal vettore nullo e da un insieme vuo-to di colonne attive, ad ogni iterazione si aggiunge la colonna che riduce maggiormente l’errore ℓ2 nell’approssimazione di b con le colonne attive.

L’algoritmo termina quando il residuo in norma ℓ2 scende al di sotto di una

tolleranza stabilita ǫ. Il costo del calcolo di una soluzione con k0 elementi

non nulli `e dell’ordine di O(k0mn) operazioni, notevolmente minore rispetto

alla ricerca esaustiva, tuttavia questo approccio non garantisce che la so-luzione pi`u sparsa sia effettivamente trovata. Esistono numerose varianti dell’orthogonal matching pursuit, che ne migliorano l’accuratezza o ne di-minuiscono la complessit`a, ad esempio il least squares orthogonal matching pursuit, il matching pursuit o il weak matching pursuit, descritti nel capitolo 3 di [19].

Data la NP-hardness del caso generale del problema, non si può garantire che gli algoritmi greedy trovino la soluzione in tutti i casi, tuttavia si dimo-stra che nei casi in cui esiste una soluzione ”sufficientemente” sparsa, essa può essere trovata: ad esempio, per l’algoritmo orthogonal matching pursuit vale il seguente teorema, la cui dimostrazione è riportata nel capitolo 4 di [19]

Teorema 6.

(18)

e m < n, se esiste una soluzione x tale che kxk0< 1 2 1 + 1 µ (A) , (2.33)

allora l’algoritmo orthogonal matching pursuit con parametro ǫ = 0 la trova esattamente.

Nel caso in cui la matrice A `e composta da due matrici ortogonali affiancate orizzontalmente vale il teorema:

Teorema 7.

Per un sistema di equazioni lineari Ax = b, in cui A = [Ψ Φ], con Ψ, Φ ∈ Rm×m matrici ortogonali, se esiste una soluzione x0 con kΨ elementi non

nulli nella prima met`a e kΦ nella seconda e vale

max{kΨ, kΦ} <

1

2µ(A), (2.34)

allora l’algoritmo orthogonal matching pursuit con parametro ǫ = 0 la trova esattamente in kΨ+ kΦ iterazioni.

Gli algoritmi greedy possono essere utilizzati anche per risolvere il proble-ma rilassato (2.28), scegliendo come parametro del criterio di arresto la tolleranza: ǫ = δ. Per l’algoritmo orthogonal matching pursuit, in [17] sono dimostrate la stabilit`a e la corretta ricostruzione del supporto della soluzione:

Teorema 8.

Si consideri un’istanza del problema (2.28), definita dalla terna (A, b, δ). Sia x0 ∈ Rn un vettore che soddisfa il vincolo di sparsit`a

kx0k0 < 1 2 1 + 1 µ(A) −_µ(A)xδ min , (2.35)

dove xmin `e l’elemento non nullo di x0 pi`u piccolo in valore assoluto, e

forni-sce una rappresentazione di b con una tolleranza dell’errore kb−Ax0k2 ≤ δ,

allora il vettore xOM P risultante dall’applicazione dell’algoritmo orthogonal

matching pursuit soddisfa

kxOM P − x0k22≤

δ2

1 − µ(A)(kx0k0− 1)

. (2.36)

Inoltre, l’algoritmo orthogonal matching pursuit ricostruisce correttamente il supporto della soluzione.

(19)

2.3.2 Tecniche di rilassamento convesso

Una seconda possibilit`a per trattare il problema (2.18) `e la regolarizza-zione della norma ℓ0. Essa viene sostituita da una funzione continua, ad

esempio una “norma” ℓp con p ∈ (0, 1], o ancora pi`u regolare, ad esempio

P

jlog(1 + αx2j),

P

jx2j/(α + x2j) o

P

j(1 − exp(−αx2j)). Una volta

rego-larizzata la funzione obiettivo, si procede risolvendo il nuovo problema, ad esempio per le “norme” ℓp si pu`o sfruttare l’algoritmo focal underdetermined

system solver (FOCUSS), descritto nel capitolo 3 di [19]. Esso `e un algorit-mo semplice, tuttavia al algorit-momento non si conosce sotto quali ipotesi riesca a risolvere i problemi, nemmeno nel caso convesso con norma ℓ1.

Rilassando il problema (2.18) bisogna prestare attenzione al fatto che la “norma” ℓ0 non `e sensibile alla grandezza degli elementi non nulli, mentre

le “norme” ℓp, p ∈ (0, 1], tendono a penalizzare i valori elevati e quindi

distorcono la soluzione, portando ad essere non nulli gli elementi che mol-tiplicano le colonne di A con norma elevata. Per evitare la distorsione si introduce una matrice di pesi W ∈ Rn×n e si ottiene, nel caso con norma ℓ1, il problema

min

x kWxk1 subject to b= Ax. (2.37)

La matrice W `e diagonale e definita positiva ed una scelta abituale per i suoi elementi `e Wjj = kajk2, dove aj sono le colonne di A. Il cambio di

variabile ˜x= Wx permette di riscrivere il problema (2.37) nella forma: min

˜

x k˜xk1 subject to b = ˜A˜x, (2.38)

dove Ã = W−1A è composta da colonne di norma unitaria. Poichè ogni problema in cui A non ha colonne nulle può essere riscritto nella forma (2.38), nel seguito saranno considerati problemi in cui le colonne di A hanno norma unitaria.

Il problema (2.38) `e conosciuto come basis pursuit (BP) e, come mostrato nel capitolo 1 di [19], pu`o essere agevolmente riscritto come un problema di programmazione lineare, per il quale si hanno a disposizione numerosi metodi, ad esempio di punto interno, del simplesso o di omotopia.

Il problema (2.38), oltre ad algoritmi adatti per la sua risoluzione, ha a disposizione numerosi risultati di equivalenza con il problema (2.18) sotto opportune ipotesi, ad esempio in nel capitolo 4 di [19] sono dimostrati i teoremi 9 e 10:

Teorema 9.

Per un sistema di equazioni lineari Ax = b, con A ∈ Rm×n di rango pieno e m < n, se esiste una soluzione x tale che

kxk0< 1 2 1 + 1 µ (A) , (2.39)

(20)

allora `e l’unica soluzione sia del problema (2.18) che del problema (2.38). Nel caso particolare in cui si hanno due matrici ortogonali affiancate oriz-zontalmente, vale il teorema pi`u potente:

Teorema 10.

Per un sistema di equazioni lineari Ax = b, in cui A = [Ψ Φ], con Ψ, Φ ∈ Rm×m matrici ortogonali, se esiste una soluzione x0 con kΨ elementi non

nulli nella prima met`a e kΦ ≥ kΨ nella seconda e vale

2µ(A)2kΨkΦ+ µ(A)kΨ− 1 < 0, (2.40)

allora x0`e l’unica soluzione sia del problema (2.38) che del problema (2.18).

La condizione (2.40) può essere sostituita dalla seguente condizione più semplice ma più restrittiva:

kxk0 <

√ 2 − 0.5

µ(A) (2.41)

Le tecniche di rilassamento convesso possono essere applicate anche al pro-blema rilassato (2.28): sostituendo la “norma” ℓ0 con la norma ℓ1 si ha il

problema

min

x kxk1 subject to kb − Axk2≤ δ. (2.42)

Il problema (2.42) `e conosciuto come basis pursuit denoising (BPDN) e pu`o essere riscritto come un problema di ottimizzazione lineare e risolto, come in precedenza, con i metodi sviluppati in questo campo.

La stabilit`a del problema `e garantita dal seguente teorema dimostrato in [17]:

Teorema 11.

Si consideri un’istanza del problema (2.42), definita dalla terna (A, b, δ). Sia x0 ∈ Rn un vettore che soddisfa il vincolo di sparsit`a kxk0 < 14(1 +

1/µ(A)) e fornisce una rappresentazione di b con una tolleranza dell’errore kb − Ax0k2≤ δ, allora la soluzione xδ1 di (2.42) soddisfa

kxδ1− x0k22 ≤

4δ2

1 − µ(A)(4kx0k0− 1)

. (2.43)

In [17], inoltre, sono riportati alcuni risultati che garantiscono la corretta ricostruzione del supporto della soluzione, ma richiedono ipotesi pi`u restrit-tive, quindi meno realistiche.

Utilizzando la propriet`a di isometria ristretta, si ottengono altri due risultati per i problemi (2.38) e (2.42). Sia ˆx_{∈ R}n un vettore tale che Aˆx= b, in [5] si dimostrano i seguenti teoremi:

(21)

Teorema 12.

Sia δ2s <√2 − 1. Allora la soluzione x1 del problema (2.38) `e tale che

kx1− ˆxk1 ≤ C0σs(ˆx)1 (2.44)

kx1− ˆxk2 ≤ C0σs√(ˆx)1

s (2.45)

per una costante C0 > 0.

Teorema 13.

Siano δ2s <√2 − 1 e kzk2 ≤ ǫ. Allora la soluzione x1 del problema (2.42)

`e tale che

kx1− ˆxk2 ≤ C0σs√(ˆx)1

s + C1ǫ (2.46)

per due costanti C0, C1 > 0.

Dal teorema 2.45 si pu`o dedurre l’equivalenza tra i problemi (2.18) e (2.38), infatti se il vettore ˆx `e s-sparso e valgono le ipotesi del teorema 12, allora ˆ

x= x0, grazie al teorema 5, e x1 = ˆx, poich`e l’errore di migliore

approssima-zione a s-terimini σs(ˆx)1nella disuguaglianza (2.44) `e nullo. Analogamente,

se ˆxè sparso, dal teorema 13 si deduce la stabilità del problema (2.42). Questi risultati sono più generali dei precedenti, in quanto forniscono delle stime anche per il problema della ricostruzione di un vettore ˆxgenerico. Tali stime indicano che si ottiene una ricostruzione buona quanto quella che si otterrebbe dalla conoscenza degli s coefficienti più significativi di ˆx.

Alcuni tipi di matrice con elementi casuali soddisfano le ipotesi del teorema 13, infatti, in [11] `e enunciato il teorema

Teorema 14.

Sia A una matrice tale che

i. le sue colonne sono ottenute campionando n vettori come variabili indi-pendenti e identicamente distribuite dalla distribuzione uniforme sulla sfera unitaria in Rm;

ii. oppure, i suoi elementi sono ottenuti come variabili indipendenti e iden-ticamente distribuite dalla distribuzione normale di media 0 e varianza

1 m;

iii. oppure, i suoi elementi sono ottenuti come variabili indipendenti e iden-ticamente distribuite dalla distribuzione di Bernoulli simmetrica con P Aij = ±√1_m = 1₂. Se vale la relazione m ≥ Cs logn_s, (2.47)

dove C `e una costante,allora la matrice A soddisfa le ipotesi del teorema 13 con grande probabilit`a.

(22)

Nel caso in cui A `e il prodotto di due matrici A = MB, tali che B ∈ Rm×n

è una base ortonormale e M ∈ Rn×n è una matrice dei tipi elencati nel teo-rema 14 e vale (2.47) con C costante opportuna, allora A soddisfa le ipotesi del teorema 11 con grande probabilità. Questo tipo di matrice è utilizzato nella pratica per le applicazioni del campo del compressed sensing.

Un altro possibile approccio per risolvere il problema (2.42), utile per i pro-blemi di grandi dimensioni, consiste nell’osservare che ha la stessa soluzione del problema di ottimizzazione non vincolata

min x λ kxk1+ 1 2kb − Axk 2 2, (2.48)

per un opportuno moltiplicatore di Lagrange λ funzione di A, b e δ. Un sem-plice metodo per la risoluzione di (2.48) `e l’algoritmo iteratively reweighted least squares (IRLS), un metodo iterativo che sfrutta la posssibilit`a di riscri-vere la norma ℓ1 come il quadrato di una norma ℓ2 adattivamente pesata:

ponenedo X = diag(|x|), si ha kxk1 = xTX−1x. Data una soluzione

ap-prossimata x_k−1 e posto X_k−1 _{= diag(|x}_k−1_{|), si cerca la soluzione x}k del

problema di ottimizzazione quadratica xk = arg min x λxTX−1_k−1x+1 2kb − Axk 2 2. (2.49)

Una volta trovato xk si costruisce la nuova matrice diagonale Xk e si itera

fino a convergenza.

Infine, il metodo least angle regression (LARS), sviluppato nel campo del-l’apprendimento automatico, è interessante per il problema (2.42), poichè permette di trovare la soluzione al variare di λ con lo stesso sforzo compu-tazionale della ricerca della soluzione per un λ fissato. Inoltre, esso è simile all’OMP, ma commette un errore maggiore nella ricostruzione del suppor-to della soluzione. Per una descrizione dettagliata, è possibile consultare il capitolo 5 di [19].

2.3.3 Metodi iterative shrinkage

Il problema (2.48) rientra nel caso pi`u generale della minimizzazione di una funzione della forma

f (x) = λ1Tρ(x) +1

2kb − Axk

2

2, (2.50)

dove ρ(x) `e una funzione che opera sui singoli elementi di x e promuove la sparsit`a. Si osservi che scegliendo ρ(x) = |x|p si ottiene 1T_{ρ(x) = kxk}pp. Per

i problemi di questo tipo, in particolare per quelli di grandi dimensioni, i metodi generali, come il gradiente coniugato o i metodi di punto interno, e i metodi trattati precedentemente, come l’OMP, l’IRLS o il LARS, risulta-no spesso inefficienti, mentre la famiglia di algoritmi iterative shrinkage `e

(23)

pi`u efficace. Questi algoritmi hanno una struttura molto semplice: ad ogni iterazione sfruttano operazioni di moltiplicazione per A e per il suo aggiun-to e uno shrinkage scalare del risultaaggiun-to ottenuaggiun-to. L’utilizzo di operazioni di moltiplicazione per A rappresenta un vantaggio nei problemi di grandi dimensioni, in quanto solitamente la matrice non `e definita esplicitando i suoi elementi, ma da un operatore applicabile in modo efficiente, invece la manipolazione diretta delle colonne della matrice, come avviene ad esempio nell’OMP, richiede di costruire esplicitamente A e di memorizzarla.

Un esempio di algoritmo iterative shrinkage `e il metodo separable surrogate functionals (SSF). Esso si ricava aggiungendo alla funzione (2.50) il termine

d(x, x0) = c 2kx − x0k 2 2− 1 2kAx − Ax0k 2 2, (2.51)

dove il parametro c `e scelto in modo tale che la funzione d(·) sia strettamente convessa, che equivale ad imporre che la matrice Hessiana cI − ATA sia definita positiva, condizione soddisfatta prendendo c > kATA_k2. Si ottiene

cos`ı la funzione surrogata ˜ f (x) = 1 2kb − Axk 2 2+ λ1Tρ(x) + c 2kx − x0k 2 2− 1 2kAx − Ax0k 2 2. (2.52)

Riorganizzando i termini di (2.52), dividendoli per c e sfruttando la defini-zione v0 = 1 cA T_{(b − Ax} 0) + x0, (2.53) si ottiene l’espressione ˜ f (x) = C + λ c1 T_{ρ(x) +}1 2kx − v0k 2 2, (2.54)

dove la costante C include tutti i termini che dipendono solo da b e x0. Tale

espressione pu`o essere separata nella somma di funzioni scalari: ˜ f (x) = C + n X k=1 1 2(v0[k] − x[k]) 2₊λ cρ (x[k]) = n X k=1 g (x[k], v0[k]) . (2.55)

La minimizzazione della funzione surrogata si riduce alla minimizzazione di funzioni scalari g(x; a) = 0.5(x − a)2+ λ_cρ(x), con soluzione ˆ_{x = S}_ρ,λ/c(a). La soluzione ˆx _{si ottiene applicando l’operatore S ad ogni elemento di x}0.

Nel caso ρi(x) = |x|p

ˆ

x = sign(x) · (|x| − λ)+ (2.56)

Nell’algoritmo separable surrogate functionals, quindi, ad ogni iterazione k + 1 si assegna x0= xknella funzione surrogata ˜f e la si minimizza. L’algoritmo

ottenuto consiste, quindi, nell’applicazione successiva di xk+1 = Sρ,λ/c 1 cA T (b − Axk) + xk (2.57)

(24)

che genera la successione di soluzioni {xk}k convergente al punto di minimo

locale della funzione iniziale f . Se la funzione ρ `e convessa, la successione converge ad un minimo globale.

Altri algoritmi di questa famiglia, trattati nel capitolo 6 di [19], sono l’IRLS based shrinkage algorithm, che sfrutta la trasformazione di 1Tρ(x) in una norma ℓ2 pesata e l’applicazione di un metodo di punto fisso, il parallel

coordinate descent iterative shrinkage, che si ispira ai metodi di discesa, e lo stagewise orthogonal matching pursuit, pi`u complesso dei precedenti e ispirato agli algoritmi OMP e LARS.

Infine, i metodi iterative shrinkage possono essere accelerati introducendo una ricerca lineare ad ogni iterazione o grazie al metodo sequential subspace optimization (SESOP).

2.3.4 L’algoritmo spectral projected gradient

Nella sezione precedente si è osservata l’equivalenza tra i problemi (2.42) e (2.48) per opportuni valori dei parametri τ e λ, tuttavia il valore di tali parametri non è noto a priori. Dato che la formulazione (2.42) ha il vantag-gio di imporre un vincolo sul residuo b − Ax, utile per includere una stima a priori del rumore, mentre per la formulazione (2.48) si hanno a disposi-zione dei metodi efficienti per il calcolo della soludisposi-zione, è utile sviluppare un’opportuna strategia per ottenere la soluzione del primo a partire da una successione di problemi di tipo (2.48). In alternativa, si può notare che anche il problema

min

x kb − Axk2 subject to kxk1 ≤ τ (2.58)

ha la stessa soluzione di (2.42) e (2.48) per una scelta appropriata del para-metro τ .

In [37] `e proposto un approccio al problema che prevede la risoluzione di una successione di problemi di tipo (2.58):

min

x kb − Axk2 subject to kxk1≤ τk, (2.59)

costruita utilizzando un metodo di Newton inesatto per determinare i para-metri di regolarizzazione τk. Prima di motivare questa scelta, verr`a illustrato

il metodo proposto per la risoluzione di problemi di tipo (2.58): l’algoritmo spectral projected gradient (SPG). Esso permette di risolvere un’istanza del problema (2.58) in campo reale o complesso e, come nei metodi iterative shrinkage, non vi `e la necessit`a di esplicitare gli elementi della matrice del problema. Il metodo spectral projected gradient sfrutta la proiezione ortogo-nale sull’insieme convesso delle soluzioni ammissibili {x | kxk1≤ τ}, grazie

all’operatore Pτ(c) = arg min x kc − xk2 subject to kxk1 ≤ τ , (2.60)

(25)

che fornisce la proiezione di un vettore c sulla palla di raggio τ in norma ℓ1.

Ad ogni iterazione, l’algoritmo applica un metodo di ricerca unidimensionale non monotona alla funzione f (α) = k¯rk22= kb−A¯xk22, con ¯x= Pτ(xℓ−αgℓ),

dove gℓ`e il gradiente di kAxℓ−bk22 all’iterazione ℓ, utilizzando come criterio

di arresto la condizione di Armijo non monotona k¯rk22 ≤ max

j∈[0,min{ℓ,M−1}]krℓ−jk 2

2+ γ(¯x− xℓ)Tgℓ, (2.61)

dove γ ∈ (0, 1) `e un parametro di discesa sufficiente, ℓ l’iterazione corrente dell’algoritmo e ri = b − Axi il residuo all’i-esima iterazione. Tale

con-dizione garantisce che almeno ogni M iterazioni avvenga una diminuzione adeguata della funzione obiettivo.

La ricerca unidimensionale considera punti della forma Pτ(xℓ− αgℓ), con

α ∈ (0, αℓ], che formano una traiettoria curvilinea, quindi per ogni

candi-data soluzione ˆx `e necessario effettuare la proiezione e calcolare il prodot-to scalare nella condizione (2.61). Inoltre, la distanza tra due candidate soluzioni successive pu`o essere molto piccola, in quanto proiezioni di pun-ti distanpun-ti possono risultare vicine. In questo modo la funzione obietpun-tivo viene valutata in punti vicini, con conseguente cattivo utilizzo dell’infor-mazione a disposizione. Una variante dell’algoritmo prevede l’applicazione della ricerca unidimensionale alla funzione h(λ) = k˜rk22 = kb − A˜xk22, con

˜

x= λPτ(xℓ− αℓgℓ) + (1 − λ)xℓ, con condizione di arresto

k˜rk22 ≤ max

j∈[0,min{ℓ,M−1}]krℓ−jk 2

2+ γλ(Pτ(xℓ− αℓgℓ) − xℓ)Tgℓ, (2.62)

in questo modo i punti sono disposti lungo la stessa direzione e, quindi, richiedono una sola proiezione e il prodotto scalare in (2.62) `e calcolato una sola volta.

Una volta ottenuto la soluzione del problema di ricerca unidimensionale, si pone xℓ+1 = ¯x (o xℓ+1= ˜x) e si aggiornano le variabili al passo ℓ + 1.

g_ℓ+1 _{= −A}Tr_ℓ+1, (2.63)

∆xℓ+1 = xℓ+1− xℓ, (2.64)

∆gℓ+1 = gℓ+1− gℓ. (2.65)

A questo punto `e possibile fissare il valore di α per la ricerca unidimensionale del passo successivo, ponendolo pari alla lunghezza spettrale introdotta da Barzilai e Borwein [2], che si ottiene da

αℓ+1 =          αmax se ∆xTℓ+1∆gℓ+1≤ 0 min ( αmax, max ( αmin, ∆xT_ℓ+1∆xℓ+1 ∆xT ℓ+1∆gℓ+1 )) se ∆xT ℓ+1∆gℓ+1> 0. (2.66) In [4] si prova che entrambe le varianti dell’algoritmo sono globalmente convergenti.

(26)

2.3.5 Metodo di proiezione

Per effettuare la proiezione definita dall’operatore (2.60) si utilizza un al-goritmo di complessità O(n log n) nel caso peggiore. Nella pratica il costo della proiezione si rivela solitamente molto minore del caso peggiore. Per semplicità, si consideri un vettore c con elementi non-negativi, in quanto per un vettore generico è possibile sostituire la funzione obiettivo in (2.60) con la funzione equivalente kDc − Dxk2, dove D è la matrice diagonale

con elementi Dii = sgn(ci), e ottenere la soluzione applicando D−1 = D

alla proiezione ottenuta. Il primo passo del metodo considera la soluzione ipotetica x = c: se `e ammissibile allora si avr`a Pτ(c) = c, altrimenti si

cercherà di diminuire la norma della soluzione ipotetica x della quantità di inammissibilità

ν = kxk1− τ. (2.67)

Si cercher`_{a, quindi, un vettore d tale che kx − dk}1 = τ di norma euclidea

minima, in modo tale da minimizzare il possibile incremento nella funzione obiettivo. Si cerca, cio`e,

d∗ = arg min

d kdk2

subject to d_{≥ 0, kdk}1 = ν. (2.68)

Si verifica facilmente che la soluzione del problema `e

d∗ = γe, (2.69)

con γ = ν/n. Tuttavia, `e necessario verificare che la proiezione preservi il segno degli elementi di c per evitare che il valore di kxk1 aumenti, si

veri-fica, cio`e, che valga d∗

i < cmin = min

i ci ∀i, altrimenti si definisce l’insieme

I = {i | d∗

i ≥ cmin} e si pone xi = 0 ∀i∈ I e si applica ricorsivamente il

processo per le variabili rimanenti {1, . . . , n} \ I.

L’algoritmo di proiezione pu`o essere adattato al caso complesso, come mo-strato in [37].

2.3.6 Propriet`a del problema duale

Grazie agli strumenti introdotti nelle sezioni precedenti, `e ora possibile de-scrivere un algoritmo per la ricerca della soluzione del problema (2.42). Si consideri la funzione

φ(τ ) = krτk2, (2.70)

con

rτ = b − Axτ, (2.71)

che restituisce il valore ottimo del problema (2.58) per ogni scelta del para-metro τ ≥ 0. A partire dalla funzione (2.70) `e possibile definire l’equazione non lineare

(27)

la cui soluzione τσ `e il valore del parametro τ per cui i problemi (2.42)

e (2.58) condividono la stessa soluzione xτσ. Per ottenere la soluzione di

(2.42), quindi, si risolve l’equazione non lineare (2.72), per la quale `e pos-sibile sfruttare l’algoritmo proposto in [37], basato sul metodo di Newton e sulle propriet`a della funzione φ.

Si pu`o mostrare che φ `e una funzione convessa e differenziabile di τ , uti-lizzando le informazioni fornite dal duale del problema (2.58). Per ricavare tale duale, si riscriva il problema (2.58) nella forma equivalente

min

r,x krk2 subject to Ax+ r = b, kxk1 ≤ τ. (2.73)

il cui duale `e dato da max

y,λ L(y, λ) subject to λ ≥ 0, (2.74)

dove

L(y, λ) = inf_x,rkrk2− yT(Ax + r − b) + λ(kxk1− τ)

(2.75) `e la funzione Lagrangiana duale, y e λ sono i moltiplicatori di Lagrange corrispondenti ai vincoli di (2.73). Separando l’estremo inferiore rispetto a re rispetto a x e riordinando i termini, si ottiene:

L(y, λ) = bTy_{− τλ − sup} r yT_r − krk2 − sup x yT_Ax − λkxk1 . (2.76)

Nell’espressione (2.76) `e possibile osservare che gli estremi superiori corri-spondono alle funzioni coniugate rispettivamente di krk2 e di λkxk1. Per

una norma arbitraria k · k con norma duale k · k∗, la funzione coniugata di

f (x) = αkxk per ogni α ≥ 0 `e data da f_∗(y) = sup x yT_x − αkxk = 0 _{se kyk}_∗ _{≤ α,} ∞ altrimenti. (2.77)

Grazie all’espressione (2.77) segue che il problema (2.74) rimane limitato se e solo se le variabili duali y e λ soddisfano i vincoli kyk2≤ 1 e kATyk∞≤ λ.

Il duale di (2.73) e di (2.58) sar`a quindi max

y,λ b T_y

− τλ subject to kyk2 ≤ 1, kATyk∞≤ λ, (2.78)

dove la non negativit`a di λ `e garantita dal secondo vincolo.

Le variabili duali possono essere facilmente calcolate dalla soluzione primale ottima. Per derivare y si sfrutta da (2.77) il fatto che

sup

x

yT_x_{− krk}

(28)

da cui y = r/krk2. Senza perdita di generalit`a si pu`o quindi prendere

kyk2 = 1 in (2.78).

Per derivare λ si osservi che se τ > 0, λ deve essere al suo estremo inferiore, come implica il vincolo kAT_y_k

∞ ≤ λ. Si prende quindi λ = kATyk∞

(se r = 0 o τ = 0 la scelta, rispettivamente, di y o di λ è arbitraria). La variabile duale y può essere eliminata e si possono scrivere le seguenti condizioni necessarie e sufficienti di ottimalità per la soluzione primale-duale (rτ, xτ, λτ)

Axτ + rτ = b, kxτk1≤ τ (2.80a)

kATrτk∞≤ λτkrτk2 (2.80b)

λτ(kxτk1− τ) = 0 (2.80c)

Le propriet`a del duale sono utilizzate in [37] per dimostrare il seguente teorema:

Teorema 15.

La funzione φ `e convessa e non crescente.

Per ogni τ ∈ (0, τBP), φ `e differenziabile con continuit`a, φ′(τ ) = −λτ e la

variabile duale ottima λτ = kATyτk∞, dove yτ = _krr_ττ_k2.

Per ogni τ ∈ [0, τBP], kxτk1= τ e φ `e strettamente descrescente.

Infine, il teorema pu`o essere esteso al caso generico in cui Φ(τ ) `e il valore del problema

min

x kb − Axks subject to kxkp ≤ τ, (2.81)

dove 1 ≤ (p, s) ≤ ∞ definiscono le norme di interesse, come mostrato in [37].

2.3.7 Metodo di Newton inesatto

Per la ricerca della soluzione dell’equazione non lineare (2.72) `e possibile sfruttare l’algoritmo proposto in [37], che genera una successione di para-metri τk→ τσ basata sull’iterazione di Newton

τk+1= τk+ ∆τk, con ∆τk= σ − φ(τk

)

φ′_(τ_k₎ , (2.82)

tale che le corrispondenti soluzioni xτk del problema (2.58) convergono a

xτσ. Grazie al Teorema 15 `e noto che φ `e convessa, strettamente

decrescen-te e differenziabile con continuit`_{a per ogni σ ∈ (0, kbk}2), quindi τk → τσ

superlinearmente per ogni valore iniziale τ0∈ (0, τBP) (si veda, ad esempio,

il capitolo 1 di [3]).

Per rendere efficiente il metodo, si utilizzano approssimazioni di φ(τk) e di

(29)

richiede la soluzione del problema di ottimizzazione (2.58), computazional-mente onerosa da ottenere in modo esatto. Con queste approssimazioni, si ha una rapidità di convergenza sublineare e, come si vedrà in seguito, ci si può avvicinare arbitrariamente alla convergenza superlineare.

Grazie alla soluzione del problema primale-duale è possibile ricavare delle espressioni che stimano l’accuratezza dei valori approssimati di Φ e Φ′. L’algoritmo spectral projected gradient per la risoluzione di (2.58) mantie-ne l’ammissibilità della soluzione ad ogni iterazione, perciò una soluzione approssimata ¯xτ e il corrispondente residuo ¯rτ = b − A¯xτ soddisfano

k¯xτk1 ≤ τ e k¯rτk2≥ kr2k2 > 0, (2.83)

dove la seconda disuguaglianza vale perch`e ¯xτ `e subottimale e τ < τBP. Si

possono costruire le approssimazioni ¯

yτ =

¯rτ

k¯rτk2

e λ¯τ = kATy¯τk∞ (2.84)

delle variabili duali, che sono ammissibili per il duale, cio`e soddisfano la con-dizione (2.80b). Il valore del problema duale (2.78) in un punto ammissibile d`a un limite inferiore al valore ottimo krτk2 e il valore del problema primale

(2.58) in un punto ammissibile d`a un limite superiore, perci`o

bTy¯τ− τ ¯λτ ≤ krτk2 ≤ k¯rk2. (2.85)

Si pu`o quindi usare il salto di dualit`a

δτ = k¯rτk2− (bTy¯τ− τ ¯λτ) (2.86)

per misurare la qualit`a di una soluzione approssimata ¯xτ. Da (2.85) si ha

che δτ `e necessariamente non negativo.

Sia ¯_{Φ(τ ) = k¯r}τk2 il valore della funzione obiettivo del problema (2.58)

cor-rispondente alla soluzione approssimata ¯xτ. Il salto di dualit`a in ¯xτ fornisce

un limite alla differenza tra Φ(τ ) e ¯Φ(τ ). Se, inoltre, A ha rango pieno e, quindi, numero di condizionamento limitato, δτ fornisce un limite anche per

la differenza tra le derivate Φ′_{(τ ) e ¯}_Φ′_{(τ ). Da (2.85), (2.86) e dal Teorema}

15 si ottiene che ¯

Φ(τ ) − Φ(τ) < δτ ∀τ ∈ (0, τBP), (2.87a)

|¯Φ′_{(τ ) − Φ}′_{(τ )| <γδ}τ ∀τ ∈ (0, τBP) (2.87b)

per una costante positiva γ indipendente da τ . Dalla definizione di Φ′ e dalle propriet`a delle norme matriciali si ha che γ `e proporzionale al numero di condizionamento di A.

La versione inesatta del metodo di Newton converge sublinearmente, ma ci si pu`o avvicinare arbitrariamente alla convergenza superlineare incremen-tando l’accuratezza nel calcolo di φ, come mostrato dal seguente teorema dimostrato in [37], che permette di stimare la rapidit`a di convergenza del metodo:

(30)

Teorema 16.

Si consideri una matrice A di rango pieno, σ ∈ (0, kbk2) e la successione

δk = δτk → 0. Allora, se τ0 `e sufficientemente vicino a τσ, l’iterazione del

metodo di Newton (2.82) con φ e φ′ _{sostituiti dalle loro approssimazioni ¯}_φ

e ¯φ′ _{genera una successione τ}_k_{→ τ}_σ _{che soddisfa}

|τk+1− τσ| = γδk+ ηk|τk− τσ|, (2.88)

dove ηk→ 0 e γ `e una costante positiva.

Si osservi che la rapidit`a di convergenza dell’algoritmo dipende dalla rapidit`a con cui δk → 0 e dal valore di γ, legato al numero di condizionamento di

A. Infine, se si risolve il problema (2.58) in modo esatto ad ogni iterazione (δk = 0), cio`e con il metodo di Newton standard, allora il Teorema 16 mostra

che la rapidità di convergenza è superlineare, in accordo con le proprietà di tale metodo.

(31)

La libreria SparseModeling

Alcuni degli algoritmi e delle strategie per la ricerca della soluzione pi`u spar-sa di un sistema sottodeterminato presentati nel capitolo precedente sono stati implementati nella libreria di classi SparseModeling.

La libreria vuole soddisfare alcune esigenze legate alle numerose applicazioni dei modelli sparsi e ridondanti e ai differenti algoritmi risolutivi: considerata la molteplicità degli ambiti in cui la ricerca della soluzione più sparsa di un sistema sottodeterminato può essere applicata, è auspicabile poter utilizzare la libreria per differenti tipi di applicazione, sia di uso comune, ad esempio la compressione audio-video, sia di calcolo intensivo. Vi è quindi l’esigenza che la libreria SparseModeling si adatti a varie piattaforme e possa inter-facciarsi con librerie adatte all’ambito del problema. La seconda esigenza è legata allo sviluppo del codice: gli algoritmi risolutivi sono numerosi e in evoluzione, il lavoro di ricerca nel campo dei modelli sparsi e ridondanti è in rapido sviluppo e, probabilmente, porterà continui miglioramenti dei me-todi esistenti e ne introdurrà di nuovi. La libreria dovrà quindi permettere l’implementazione e lo sviluppo dei nuovi algoritmi, limitando la riscrittura di codice e la possibilità di errori di programmazione. Infine, è necessario un codice efficiente e parallelizzabile, in particolar modo per problemi di grandi dimensioni, ad esempio nel trattamentdo di dati sismici.

3.1 Implementazione della libreria

Per rispondere a queste esigenze è stato scelto di implementare la libreria nel linguaggio C++11, utilizzando la programmazione generica ed un design basato sulle policies, che garantisce flessibilità e riusabilità del codice. Tra le estensioni introdotte dal C++11, la libreria sfrutta gli alias template e le keywords auto e decltype.

L’uso della programmazione generica si riflette nell’implementazione della maggior parte delle classi della libreria come class templates che presentano

(32)

il parametro linear algebra implementation, con lo scopo di definire la scelta dei tipi base e di quelli per vettori e matrici. Tale parametro, infatti, prende come argomento una struct contenente le informazioni sui tipi utilizzati in una particolare implementazione, in modo tale da poter gestire un tipo in tutta la libreria con una sola modifica al codice, inoltre, lo stesso parame-tro permette di implementare specializzazioni dei class templates specifiche per ogni implementazione dell’algebra, per ottenere efficienza e gestire la differenza di nomi delle operazioni algebriche nelle librerie per l’algebra sup-portate. Al momento sono presenti le struct UBLASLinearAlgebraImple-mentation, TpetraLinearAlgebraImplementation e PETScLinearAlgebraIm-plementation, che sfruttano rispettivamente le librerie per l’algebra lineare uBLAS, Tpetra e PETSc. La prima appartiene alla collezione di librerie C++ Boost, disponibile per varie piattaforme, diffusa e spesso presa in con-siderazione per aggiunte alla libreria standard. uBlas permette di utilizzare vettori e matrici in cui è possibile definire il tipo contenuto tramite un para-metro template, ma non è tra le più veloci librerie di algebra nè implementa la costruzione di strutture dati distribuite, quindi il suo utilizzo in Spar-seModeling è finalizzato allo studio dei metodi risolutivi senza necessità di installare librerie aggiuntive più complesse nell’utilizzo.

La libreria Tpetra, anch’essa scritta in C++, appartiene alla collezione Tri-linos ed è pensata per l’utilizzo in applicazioni scientifiche e per il calcolo parallelo. Come uBlas, permette di utilizzare matrici e vettori pieni o sparsi, parametrizzati rispetto al dato contenuto, inoltre permette la costruzione di strutture dati distribuite. Infine, la libreria PETSc, scritta principalmente in C, è una libreria per il calcolo scientifico, in particolare per le equazioni differenziali alle derivate parziali. Il suo utilizzo in SparseModeling è limi-tato ai vettori distribuiti e alle operazioni su di essi. L’utilizzo di Tpetra e PETSc è indicato il trattamento di problemi di grandi dimensioni con la libreria SparseModeling.

3.1.1 Design basato sulle policies

Il design basato sulle policies è una tecnica che permette di assemblare una classe dal comportamento complesso utilizzando classi più piccole, dette po-licies, ognuna delle quali si occupa di un solo aspetto comportamentale o strutturale. Una policy stabilisce un’interfaccia che riguarda un aspetto specifico, quindi è possibile implementare la policy in vari modi, purchè ri-spettino tale interfaccia. Le implementazioni di una policy sono dette policy classes, mentre una classe che usa una o più policies è detta classe host. Il paradigma delle policies può essere implementato utilizzando l’ereditarietà pubblica, che in questo caso non rappresenterà la relazione is-a, facendo in modo che la classe host erediti dalla policy class passata come argomento. Una classe host con più policies sfrutterà l’ereditarietà multipla. Grazie

(33)

all’ereditarietà pubblica, è possibile definire l’interfaccia della classe host ar-ricchendola delle funzionalità implementate nella policy class.

Il vantaggio di questo design è la possibilità di ottenere un codice flessibile a partire da un numero ridotto di comportamenti, tuttavia la sua creazione richiede attenzione nella decomposizione delle funzionalità di una classe in policies: in questa fase è importante realizzare una decomposizione ortogo-nale, cioè in cui le policies sono completamente indipendenti l’una dall’altra. La dipendenza tra policies non ortogonali riduce la sicurezza rispetto ai tipi e complica il design.

Il design basato sulle policies `e trattato in dettaglio nel capitolo 1 di [1]. 3.1.2 Traits

I traits sono una tecnica di programmazione generica che permette di ri-durre il numero di parametri di un class template, facendo dipendere da un parametro principale alcuni parametri secondari. Ci`o avviene definendo i parametri dipendenti in una template class che abbia come argomento il parametro principale.

A titolo di esempio, si consideri un semplice function template, in cui il tipo dell’argomento e di ritorno siano definiti dal parametro T:

template<typename T>

T myFunction( T myArgument ) {

// ... }

Per ottenere la possibilit`a di avere un tipo di ritorno diverso da quello del-l’argomento, `e possibile aggiungere un secondo parametro template, oppure sfruttare la tecnica dei traits:

template<typename T> struct ReturnTraits { typedef T type; }; template<> struct ReturnTraits<int> {

typedef float type; };

template<typename T>

typename ReturnTraits<T>::type myFunction( T myArgument ) {

// ... }

(34)

In questo modo, si mantiene il tipo di ritorno uguale a quello dell’argomento per tutti i tipi tranne che per int, per il quale si ha tipo di ritorno float. Per una trattazione approfondita `e possibile consultare, ad esempio, il capitolo 15 di [39].

3.2 Solutori iterativi

I metodi per risolvere i problemi di ottimizzazione presentati precedente-mente sono numerosi e tutti iterativi, quindi si è deciso di utilizzare come fulcro della libreria il class template IterativeMethod. Esso è una classe host che astrae il concetto di metodo iterativo e permette la definizione dei suoi aspetti particolari, ad esempio le operazioni effettuate ad ogni iterazione o il criterio di arresto, attraverso policy classes. Grazie alla scelta di un design basato sulle policies, è possibile riutilizzare parte del codice che gli algorit-mi hanno in comune e, allo stesso tempo, specializzare l’idea di algoritmo iterativo negli aspetti specifici del particolare algoritmo e nella scelta del-le strutture dati per l’algebra lineare. Il class template IterativeMethod ha sette parametri:

• linear algebra implementation: questo parametro, come detto in pre-cedenza, permette di definire i tipi utilizzati per matrici, vettori, nu-meri reali e interi.

• iteration policy: questo parametro definisce le operazioni effettuate ad ogni iterazione dell’algoritmo.

• stopping rule policy: questo parametro permette di definire il criterio di arresto dell’algoritmo.

• pre loop policy: questo parametro definisce le operazioni da effettuare prima di iniziare le iterazioni dell’algoritmo.

• post loop policy: questo parametro definisce le operazioni da effettuare al termine dell’algoritmo, una volta che il criterio d’arresto `e stato soddisfatto.

• solver status policy: questo parametro definisce la struttura dati che memorizza lo stato dell’algoritmo e l’interfaccia che permette di otte-nere informazioni sulla sua esecuzione, al termine della stessa.

• ensure first iteration: questo parametro booleano permette di sceglie-re se il ciclo del solutosceglie-re avr`a una struttura di tipo while o do-while. La struttura viene definita durante la compilazione, grazie alla meta-funzione della standard library enable if, che sfrutta il concetto di sub-stitution failure is not an error (SFINAE) per inserire selettivamente un metodo nell’overload resolution set.

(35)

Entrando nel dettaglio si osserva che la policy iteration policy è specifica per ogni metodo per la risoluzione di sistemi sottodeterminati e determina, attraverso la tecnica dei traits, la struttura che riceve i dati del problema e quella che memorizza le variabili interne all’algoritmo; al contrario, le po-licies solver status policy e stopping rule policy permettono scelte differenti per uno stesso algoritmo (ad esempio si può scegliere un criterio d’arresto basato sulla norma della variazione della soluzione o sulla norma relativa del residuo) ed una stessa policy class può essere adatta a più algoritmi (ad esempio uno stato dell’algoritmo che memorizza il suo successo e il numero di iterazioni effettuate).

L’interfaccia di IterativeMethod non è definita in modo rigido, ma è eredi-tata dalle policy classes attraverso il meccanismo dell’ereditarietà multipla, quindi dipende dalla scelta delle stesse e si adatta al particolare algoritmo iterativo.

Le policy classes non sono implementate come classi, ma come class templa-tes, poichè sono parametrizzate rispetto a linear algebra implementation ed altri parametri, quindi il class template IterativeMethod sfrutta la tecnica dei template template parameters. Inoltre, il design di alcune policy classes è a sua volta basato sulle policies, ad esempio il class template OrthogonalMat-chingPursuitIteration presenta un parametro per la selezione del solutore del problema provvisorio da utilizzare ad ogni iterazione del metodo OMP. La presenza di un parametro aggiuntivo, però, rende il class template inadat-to come argomeninadat-to del parametro iteration policy di IterativeMethod. Per semplificare la gestione di questa policy class, è fornita la template struct set omp iteration provisional problem solver, parametrizzata rispetto al ti-po del solutore del problema provvisorio, che definisce al suo interno un alias template adatto come argomento di iteration policy.

3.3 Metodi implementati

La libreria contiene le implementazioni di alcuni dei metodi presentati nel capitolo 2 per la risoluzione di sistemi sottodeterminati. Tali implementazio-ni sfruttano la classe host IterativeMethod : per ogimplementazio-ni metodo è presente una policy class per la policy iteration policy, oltre alle classi ad essa collegate, come quelle per i dati in ingresso, per le variabili interne e per il valore dei parametri. Oltre a queste classi specifiche, ogni metodo richiede la scelta o la possibilità di scelta di altre policies, ad esempio quella per il criterio d’ar-resto, quindi, per una gestione più semplice, si sfruttano degli alias template che riducono il numero di parametri rispetto ai sette di IterativeMethod. Gli alias template attualmente presenti sono:

• LinearConjugateGradient: implementa il metodo del gradiente coniu-gato lineare, adatto a risolvere sistemi di equazioni lineari determina-ti, con matrice dei coefficienti simmetrica e definita positiva. Questo