L’impianto teorico dell’algoritmo MP

Sia ℋ uno spazio di Hilbert. In ambito matematico, questa denominazione indica un insieme dotato di una struttura lineare, cioè uno spazio vettoriale, su cui sia definita l’operazione di prodotto scalare. Inoltre, in uno spazio di Hilbert è garantita la completezza. Questo significa che le operazioni di passaggio al limite sono sempre e comunque ben definite.

In siffatto contesto, il dizionario viene definito come una famiglia di vettori, appartenenti allo spazio ℋ e caratterizzati da una norma – 𝑙𝑙₂ unitaria. Si tratta di due condizioni vincolanti, cui devono sottostare tutti gli atomi. La definizione ha un’immediata trasposizione matematica nella formula:

𝒟𝒟 = �𝑎𝑎_𝛾𝛾�_{𝛾𝛾∈Γ} ∶ �_�𝑎𝑎^{𝑎𝑎𝛾𝛾 ∈ ℋ}

Parallelamente, anche il segnale in esame viene inserito nell’ambito dello spazio ℋ. Per la precisione, si parla di un vettore 𝑓𝑓 ∈ ℋ.

L’obbiettivo dichiarato dell’algoritmo MP è decomporre 𝑓𝑓 su un opportuno sottoinsieme di 𝒟𝒟. Il termine opportuno è piuttosto astratto e necessita di alcune precisazioni: nel processo di selezione, si cercano quei candidati che più si avvicinano agli elementi strutturali interni di 𝑓𝑓.

Il protocollo elaborato da Mallat e Zhang non perviene alla soluzione ottimale in un unico passaggio. Secondo una procedura tipicamente iterativa, i risultati vengono progressivamente affinati e approssimano sempre con maggiore fedeltà il segnale originario.

3.9.1 Proiezioni ortogonali

Il metodo seguito in ogni iterazione si rifà ai dettami della geometria proiettiva. Scendendo maggiormente nel dettaglio, ad ogni passaggio il vettore originario 𝑓𝑓 viene proiettato lungo la direzione dei vari atomi prescelti.

A titolo di esempio, si consideri un caso particolarmente semplice, ma ugualmente istruttivo. Si immagini di utilizzare un unico atomo, tale 𝑎𝑎_𝛾𝛾0 ∈ 𝒟𝒟. La formula di proiezione fornisce la seguente decomposizione:

𝑓𝑓 = 〈𝑓𝑓, 𝑎𝑎𝛾𝛾₀〉 𝑎𝑎𝛾𝛾₀ + 𝑅𝑅𝑓𝑓

Il vettore cosiddetto dei residui, 𝑅𝑅𝑓𝑓, colma le eventuali discrepanze tra l’andamento approssimato e quello originario. In tal senso, può essere considerato un indice dell’errore commesso in fase di decomposizione. Chiaramente, visto il procedimento adottato, il vettore dei residui è perfettamente ortogonale a 𝑎𝑎_𝛾𝛾0. Nell’ambito dell’acquisizione dei segnali, però, si è soliti valutare un diverso indice di affidabilità: l’errore normalizzato ed elevato al quadrato. In quest’ottica, si ricava la seguente uguaglianza:

‖𝑓𝑓‖₂2= �〈𝑓𝑓, 𝑎𝑎𝛾𝛾₀〉�²+ ‖𝑅𝑅𝑓𝑓‖₂2 (3.1) A questo punto, è facile valutare l’approssimazione restituita dall’algoritmo. La sua bontà è inversamente proporzionale alla misura quadratica dell’errore.

3.9.2 Selezione degli atomi

La (3.1) fornisce anche alcuni utili suggerimenti per la scelta ottimale dell’atomo 𝑎𝑎𝛾𝛾₀. Infatti, il primo membro non dipende in alcun modo dalla procedura di decomposizione. Dunque, è lecito considerarlo a tutti gli effetti una costante. Altrettanto si può dire per la somma al secondo membro. Ecco, allora, che il candidato ideale per l’atomo 𝑎𝑎_𝛾𝛾0 massimizza il termine �〈𝑓𝑓, 𝑎𝑎_𝛾𝛾0〉�², ossia minimizza il termine ‖𝑅𝑅𝑓𝑓‖₂2.

Sfortunatamente, all’atto pratico non sempre questa condizione è realizzabile e si riesce soltanto ad avvicinarsi alla soluzione ottimale. In particolare, la scelta ricade sul vettore 𝑎𝑎_𝛾𝛾0 che soddisfa la seguente disuguaglianza, che prevede un ulteriore grado di libertà, rappresentato dal fattore di ottimalità 𝛼𝛼, il cui intervallo di variazione spazia tra 0, nel caso peggiore, e 1, nel caso migliore:

In fin dei conti, la scelta del vettore 𝑎𝑎_𝛾𝛾0 è tutt’altro che casuale. Al contrario, si attiene ad un rigido criterio formale, esemplificato da questa disuguaglianza.

3.9.3 La funzione di scelta

Alla luce delle precedenti osservazioni, il processo di selezione può essere ridotto ad un’apposita funzione deterministica. Gli stessi autori Mallat e Zhang ne hanno approntato un prototipo, di facile realizzazione. Tipicamente, la cosiddetta funzione di scelta viene indicata con il simbolo 𝐶𝐶, che ricorda l’iniziale del termine inglese choice, che significa appunto scelta, selezione.

L’unico argomento in ingresso è rappresentato da un qualsiasi sottoinsieme Λ di Γ. In uscita, la funzione restituisce tra gli atomi con indice in Λ quello che meglio si presta ad approssimare il segnale originale. Il concetto, a parole complicato, si rivela semplice e immediato non appena si considera un esempio concreto. A tal proposito, il sottoinsieme Λ0 rispetti la seguente formulazione:

Λ₀= �𝛽𝛽 ∈ Γ ∶ �〈𝑓𝑓, 𝑎𝑎_𝛽𝛽〉� ≥ 𝛼𝛼 sup��〈𝑓𝑓, 𝑎𝑎_𝛾𝛾〉��_{𝛾𝛾∈Γ}�

Data una simile configurazione, la funzione di scelta porge come risultato precisamente 𝛾𝛾₀= 𝐶𝐶(Λ₀).

Allo stato attuale, non si conosce una definizione di 𝐶𝐶 valida universalmente. Al contrario, ne esistono diverse versioni, la cui opportunità dipende principalmente da questioni di complessità computazionale.

3.9.4 Progressiva decomposizione del residuo

L’algoritmo MP segue un procedimento di tipo iterativo: ad ogni passaggio, il residuo 𝑅𝑅𝑓𝑓 viene ulteriormente decomposto. In questa ottica, viene proiettato lungo la direzione dell’atomo che meglio lo approssima. A tal proposito, l’analogia con l’espansione lineare di 𝑓𝑓 è palese.

Idealmente, la procedura si sviluppa in modo semplice e lineare. Al passaggio iniziale, denotato dall’apice pari a 0, il residuo coincide esattamente con l’intero vettore 𝑓𝑓, ossia 𝑅𝑅0𝑓𝑓 = 𝑓𝑓. Mediante la funzione di scelta 𝐶𝐶, l’algoritmo elegge l’atomo 𝑎𝑎_{𝛾𝛾𝑠𝑠} che meglio approssima il residuo. Nello specifico, il candidato ottimale deve soddisfare la seguente disuguaglianza:

�〈𝑅𝑅𝑠𝑠𝑓𝑓, 𝑎𝑎_{𝛾𝛾𝑠𝑠}〉� ≥ 𝛼𝛼 sup��〈𝑅𝑅𝑠𝑠𝑓𝑓, 𝑎𝑎_𝛾𝛾〉��_{𝛾𝛾∈Γ}

Nota la direzione di proiezione, il residuo viene decomposto secondo la seguente espressione: 𝑅𝑅𝑠𝑠𝑓𝑓 = 〈𝑅𝑅𝑠𝑠𝑓𝑓, 𝑎𝑎𝛾𝛾_𝑠𝑠〉 𝑎𝑎𝛾𝛾_𝑠𝑠+ 𝑅𝑅𝑠𝑠+1𝑓𝑓

Vista la modalità con cui viene ricavato, il computo aggiornato del residuo, pari a 𝑅𝑅𝑠𝑠+1𝑓𝑓, è ortogonale all’atomo 𝑎𝑎_{𝛾𝛾𝑠𝑠}. Di conseguenza, è valida anche la seguente uguaglianza tra termini quadratici:

‖𝑅𝑅𝑠𝑠𝑓𝑓‖₂2= �〈𝑅𝑅𝑠𝑠𝑓𝑓, 𝑎𝑎_{𝛾𝛾𝑠𝑠}〉�²+ ‖𝑅𝑅𝑠𝑠+1𝑓𝑓‖₂2

Questo paradigma si ripete iterativamente, sempre uguale a se stesso. In linea di principio, gli autori non hanno formulato un vero e proprio criterio di arresto. Spetta all’utente decidere quando l’approssimazione fornita dall’algoritmo soddisfa le sue esigenze o i requisiti imposti.

La via più semplice da seguire prevede la definizione di un’apposita soglia: non appena il computo aggiornato del residuo si assesta al di sotto di questo valore limite, il procedimento iterativo si interrompe.

3.9.5 Approssimazioni intermedie

La proposta di Mallat e Zhang è molto affascinante, perché ad ogni passaggio riduce progressivamente il residuo, lo scarto rispetto al vettore originario. Tuttavia, l’algoritmo garantisce soltanto la convergenza asintotica. In altri termini, fissato un numero per quanto grande di iterazioni, rimane sempre e comunque una certa discrepanza.

A titolo di esempio, si considerino i risultati ottenuti al termine di 𝑚𝑚 iterazioni. L’algoritmo esprime 𝑓𝑓 con un’espressione che prevede una sommatoria di 𝑚𝑚 termini e il computo del residuo:

𝑓𝑓 = � (𝑅𝑅𝑠𝑠𝑓𝑓 − 𝑅𝑅𝑠𝑠+1𝑓𝑓) 𝑚𝑚−1 𝑠𝑠=0 + 𝑅𝑅𝑚𝑚𝑓𝑓 = � 〈𝑅𝑅𝑠𝑠𝑓𝑓, 𝑎𝑎𝛾𝛾_𝑠𝑠〉 𝑚𝑚−1 𝑠𝑠=0 𝑎𝑎𝛾𝛾_𝑠𝑠 + 𝑅𝑅𝑚𝑚𝑓𝑓

Con un procedimento del tutto analogo a quello seguito nella decomposizione del residuo, si normalizzano e si elevano al quadrato i vari addendi. La prima sommatoria porge la seguente espressione:

‖𝑓𝑓‖₂2 = � (‖𝑅𝑅𝑠𝑠𝑓𝑓‖₂2− ‖𝑅𝑅𝑠𝑠+1𝑓𝑓‖₂2) + ‖𝑅𝑅𝑚𝑚𝑓𝑓‖₂2 𝑚𝑚−1

𝑠𝑠=0

Parallelamente, dalla seconda sommatoria discende un’analoga equazione, facilmente interpretabile come una condizione di conservazione dell’energia:

‖𝑓𝑓‖₂2= ∑𝑚𝑚−1�〈𝑅𝑅𝑠𝑠𝑓𝑓, 𝑎𝑎_{𝛾𝛾𝑠𝑠}〉�²+ ‖𝑅𝑅𝑚𝑚𝑓𝑓‖₂2

𝑠𝑠=0 (3.2) Il significato della (3.2) è presto detto: nonostante l’operazione di proiezione sia palesemente non lineare, l’energia si conserva ugualmente.

Questo fenomeno ha due implicazioni di assoluta rilevanza. In primo luogo, garantisce in maniera incontrovertibile che il contenuto informativo non venga disperso nel corso dei passaggi. In secondo luogo, costituisce la base per le dimostrazioni formali della convergenza asintotica dell’algoritmo.