Premessa

Per la stesura di questo articolo mi sono servito come altre volte di un video pubblico della 3Blue1Brown dal titolo “But what is a convolution?” fermandomi solo alla parte iniziale, dato che il mio intento è di introdurre l’argomento nel modo più semplice possibile.

Liste di numeri e operazioni

In quanti modi si può ottenere una terza lista date due liste di numeri? Certamente moltissimi, o infiniti, direte voi. Se disponiamo le due liste, chiamiamole "a" e "b", in due colonne affiancate, otteniamo una tabella con tante righe quanti sono i numeri di ciascuna lista (ammesso che contengano la stessa quantità di termini, ma se le quantità sono diverse non cambia nulla, potendo sempre aggiungere degli zeri nei posti mancanti). È un’operazione che tipicamente si fa con Excel. Si possono allora, per esempio, sommare in una terza colonna i due termini della stessa riga, o li si possono moltiplicare; ad esempio “quantità” e “prezzo unitario” per calcolare quanto si spende comprando una serie di prodotti che costano “un tanto al kg”, come si fa in una lista della spesa un po’ analitica. Saltando nella matematica, le due liste possono ottenersi anche da due funzioni di una stessa variabile, discrete o continue, f(x) e g(x).

Convoluzione

Ma c’è un’altra operazione un po’ più complessa che si può fare su due liste, un’operazione che si rivela molto importante e che ha il nome leggermente intimidatorio di “convoluzione”. È un nome che, come “evoluzione” e “involuzione”, deriva da “volgere”, girare, piegare.

La convoluzione tra due successioni o due funzioni viene indicata con un asterisco:

a*b, f(x)*g(x) oppure [f*g](x),

che si può confondere con la semplice moltiplicazione, per la quale ho infatti inizialmente usato la x.

La convoluzione trova applicazione in vari campi dell’attività umana o delle tecnologie, come l’elettrotecnica e le telecomunicazioni in cui è molto presente, ma può anche essere nascosta o non consapevole. Si tratta di qualcosa di meno immediato della sola somma o della sola moltiplicazione, dato che è una particolare combinazione delle due, una combinazione comunque lineare. (In generale, quando si riesce ad applicarla, la linearità è fondamentale perché mantiene le proporzioni e così semplifica di molto la vita).

D’ora in poi al posto di “lista” useremo il termine “successione”, per indicare più specificamente che ci riferiamo a liste di numeri.

Per ottenere la convoluzione tra due successioni a e b è visivamente più espressivo disporle su due righe (invece che su due colonne) oppure su due linee perpendicolari che danno luogo a una tabella simile alle “tabelline”, quelle che si imparano alle scuole primarie per poter fare le moltiplicazioni.

Dadi

Partiamo con un esperimento familiare: il lancio ripetuto di due dadi.

Le possibili uscite sono 36, ossia l’"insieme prodotto”. Supponiamo di voler conoscere le probabilità di ottenere dal lancio la somma S. In quanti modi si può ottenere tale somma con un lancio? Ad esempio S = 4 si ottiene con 2+2 o con 3+1 o con 1+3. La probabilità che esca una qualsiasi combinazione di dadi (il termine “combinazione” è usato qui in senso generico) è il prodotto delle probabilità di uscita di ciascuna delle due facce, ossia 1/6x1/6 = 1/36; dato in questo caso ci sono 3 combinazioni che danno S=4, la sua probabilità è 1/6x1/6 + 1/6x1/6 + 1/6x1/6 = 3/36.

4TAB

Dalla figura si vede come ogni valore dato della somma S risiede su una linea diagonale della tabella.

Se ora passiamo alla disposizione delle due successioni su due righe ci rendiamo conto che lo stesso risultato si ottiene traslando orizzontalmente la seconda successione rispetto alla prima, da sinistra a destra in modo da sovrapporre ad ogni passo le caselle in successione: prima una, poi due, etc., fino alla sovrapposizione completa (che corrisponde al massimo numero di combinazioni) e continuando fino all’assenza di sovrapposizioni. Ad ogni passo vengono eseguiti i prodotti corrispondenti e la loro somma.

Come si può dedurre dalla figura sottostante, questo procedimento corrisponde esattamente a “dispiegare” le diagonali della tabella una dopo l’altra per poi sommarne i termini.

Riferendoci alle probabilità, abbiamo dato per scontato che le facce dei dadi siano equiprobabili, cioè che ogni faccia abbia la probabilità di 1/6 di presentarsi. Consideriamo invece due dadi truccati, A e B, in cui le probabilità associate alle 6 facce siano tutte diverse da 1/6 e chiamiamole a₁, a₂, … a₆ per il dado A e b₁, b₂, …, b₆ quelle del dado B. Ora le 3 combinazioni che danno S=4 avranno ognuna una probabilità diversa, quindi la probabilità di S=4 è a₁xb3 + a₂xb₂ + a₃xb₁.

La figura mostra tutte le combinazioni di probabilità per ogni valore della somma S, da 2 a 12.

Si chiama convoluzione a_i * b_j la successione di valori ottenuti ciascuno come somma di prodotti a_ixb_j in cui i+j è costante.

Ne segue che mentre un indice aumenta, l’altro diminuisce, come si vede nella figura.

Conviene allora usare il solo indice i come in figura, ponendo j=n-i e quindi a_i e b_[n-i], dove "n" è la somma relativa ad ogni passo che qui varia tra 2 e 12. Ad esempio quando n=6, i varia da 1 a 5, come si vede in figura nel caso evidenziato di P(A+B=6).

La convoluzione assume l’aspetto di una sommatoria con indice i che varia in modo da coprire tutti i termini diversi da 0; in questo esempio i varia da 1 a n-1. La figura precedente riporta infatti 11 passi, ognuno dei quali rappresenta la probabilità che la coppia dei dadi lanciati abbia come somma quella corrispondente al passo.

Un punto da sottolineare è proprio l’inversione degli indici, nel senso che, mentre quello di a cresce, quello di b diminuisce. Perché è da sottolineare? Perché in genere confonde. Quando applicheremo la convoluzione alle funzioni continue (prossimo articolo), bisognerà invertire il segno della variabile indipendente di una delle due funzioni, il che si traduce nel “rovesciarla”, in modo che il primo valore diventi l’ultimo, il secondo il penultimo, etc. Non è un caso che in tedesco la convoluzione si chiami Faltung, che significa piegatura, come abbiamo detto sopra per l’origine del nome italiano.

Questo rovesciamento lo si è visto anche nell'illustrazione soprastante della probabilità discreta; ad esempio considerando P(A+B=6) della figura, per formare i singoli addendi conviene rovesciare la successione b₁-b₅ in modo che l’elemento b₅ si trovi sotto ad a₁, b₄ ad a₂, etc.

Al di là del procedimento operativo, possiamo dire, rinunciando al rigore matematico, che la ditribuzione probabilità associata alla somma di due eventi indipendenti (qui i lanci dei due dadi) è la convoluzione delle distribuzioni di probabilità di ognuno dei due eventi.

Altre successioni

Usciamo ora dal contesto della probabilità e consideriamo una convoluzione generica di due successioni di numeri e cioè A = (1,2,3) e B = (4,5,6)

Nella figura vengono riportati solo due dei 5 passi di scorrimento, il secondo e l’ultimo. Come si vede la seconda successione viene rovesciata per eseguire le operazioni nell’ordine corretto, usando lo scorrimento della seconda successione rispetto alla prima.

Perché nell’esempio dei dadi con facce equiprobabili non c’è l’inversione della seconda successione? Perché l’autore è stato astuto nel trovare un esempio in cui l’indice coincide con l’evento, per così dire. Appena ha introdotto i dadi truccati, però, non ha più rappresentato la traslazione delle successioni ma ha semplicemente riportato le diagonali “in dritto”, girando la tabella di 45° ottenendo una riga per diagonale.

Consideriamo ora il prodotto di due polinomi con coefficienti espressi dalle due successioni di cui sopra, ordinati per potenze crescenti: esso non è altro che un polinomio uguale alla convoluzione dei polinomi.

La cosa funziona bene anche se i polinomi sono ordinati per grado decrescente, come si può facilmente verificare.

E naturalmente funziona per la moltiplicazione ordinaria tra due numeri:

Quando noi eseguiamo “a mano” una moltiplicazione in pratica facciamo un’operazione di convoluzione dove, invece di traslare il secondo numero (la seconda successione), trasliamo il suo risultato a sinistra. Qui è mostrata una moltiplicazione tra due numeri di 3 cifre, che produce una tabella quadrata, ma la cosa funziona ovviamente anche con numeri di cifre diverse.

Riassumendo, potremmo dire che la convoluzione è un’operazione lineare, cioè una particolare combinazione lineare fatta tra due successioni di numeri (due righe) sovrapposte orizzontalmente, in cui la seconda successione, dopo che è stata invertita, i termini cioè sono stati posti in ordine inverso (l’ultimo è diventato il primo, il penultimo è diventato il secondo, etc.), scorre da sinistra a destra mentre la prima rimane ferma. Per ogni passo di scorrimento avvengono due operazioni successive: prodotto di ogni coppia di termini soprastanti e somma di tali prodotti, il cui risultato è un termine di una nuova successione, che è appunto la convoluzione delle prime due.

Come abbiamo visto in un esempio precedente, una successione può essere anche un insieme di coefficienti di un polinomio. Nel caso particolare in cui due successioni coincidono, la convoluzione corrisponde a elevare al quadrato il polinomio. Se poi vogliamo elevare il polinomio al cubo basterà eseguire la convoluzione tra il polinomio al quadrato così ottenuto e il polinomio alla prima potenza. Il procedimento si può reiterare per potenze maggiori. Nel caso di un binomio, poi, si potrebbero vedere le relazioni tra la convoluzione e il triangolo di Tartaglia.

in definitiva la convoluzione di due successioni è una terza successione, ogni termine della quale è ottenuto con le formule seguenti:

Def

In questa seconda formula si vede esplicitamente come le due successioni possano avere anche quantità diverse di termini, come già si era detto pe la moltiplicazione eseguita “a mano”.

Sempre per lo stesso motivo si può dedurre che la convoluzione è commutativa, ossia, per l’esempio sopra è y(n) = h(n) * h(n) = h(n) * x(n).

Conclusione

Quanto scritto in questo articolo cerca di gettare un po’ di luce su un concetto che, come viene spesso presentato nei libri, non è proprio immediatamente intuitivo, ma è un concetto che ha applicazioni piuttosto ampie. A questo proposito riporto direttamente la voce Convoluzione di Wikipedia:

“La convoluzione e le relative operazioni sono usate in diverse applicazioni dell'ingegneria e della matematica.

· In statistica, una media mobile pesata è una convoluzione. Anche la distribuzione di probabilità della somma di due variabili casuali indipendenti corrisponde alla convoluzione di ognuna delle loro distribuzioni.

· In ottica, molte specie di "blur" sono descritte tramite la convoluzione. Un'ombra (ad esempio l'ombra su un tavolo che si vede quando gli si interpone un oggetto innanzi la fonte luminosa) è la convoluzione della forma della fonte di luce che sta proiettando l'ombra dell'oggetto illuminato e l'oggetto stesso. Una foto fuori fuoco è la convoluzione dell'immagine a fuoco con la forma del diaframma. Il termine fotografico per tale effetto è bokeh.

· Analogamente, nell'elaborazione digitale delle immagini, i filtri convoluzionali assumono un importante compito negli algoritmi di calcolo dei margini e dei processi correlati.

· Nell'elaborazione digitale dei segnali, il filtraggio di frequenza può essere semplificato convolvendo due funzioni (dati con un filtro) nel dominio del tempo, il che equivale a moltiplicare i dati con un filtro nel dominio di frequenza.

· In acustica lineare, un'eco è la convoluzione del suono originale con una funzione geometrica che descrive i vari oggetti che stanno riflettendo il segnale sonoro.

· In elaborazione digitale dei segnali, nella riverberazione artificiale la convoluzione è utilizzata per codificare la risposta ad impulso di una stanza reale ad un segnale audio digitale.

· In ingegneria elettrica e in altre discipline, l'output (risposta) di un sistema dinamico lineare (stazionario) è la convoluzione di un input (eccitazione d'ingresso) con la risposta impulsiva del sistema (ovvero la risposta quando l'eccitazione d'ingresso è la funzione Delta di Dirac). Nel dominio discreto il concetto di convoluzione viene esteso a una sommatoria, applicata al prodotto di segnale e risposta impulsiva [4], con la sequenza h(n) che prende il nome di "kernel di convoluzione" o "maschera di convoluzione".

· Nella spettroscopia a fluorescenza determinata a tempo, il segnale di eccitazione può essere trattato come una catena di impulsi delta, e la fluorescenza misurata è data dalla somma dei decadimenti esponenziali di ogni impulso delta.”

Nel prossimo articolo cercherò di illustrare, partendo da esempi semplici e intuitivi, la convoluzione applicata al tempo, cosa che come “elettrici” ci riguarda più da vicino.