Approssimazioni greedy in spazi di Banach e di Hilbert

Uno dei problemi dell'Analisi Matematica consiste, dati spazi con specifiche proprietà, nella definizione di sistemi di elementi (dello spazio stesso) tramite i quali sia possibile esprimere tutti gli elementi dello spazio considerato. Esempi di sistemi sono le basi ortonormali per gli spazi di Hilbert e le basi di Schauder per i maggiormente generali spazi di Banach. In entrambi i casi proposti, un elemento dello spazio può essere opportunamente espresso in modo unico (si parla per questo di sistemi non ridondanti) tramite una serie (infinita) i cui termini sono il prodotto di un opportuno coefficiente con un elemento della base. In ambiti applicativi dell'Analisi, come lo studio e la trasmissione dei segnali, risulta inoltre essere un problema rilevante l'approssimazione degli elementi di uno spazio (problema successivo alla loro rappresentazione). Sulla scia di quanto precedentemente detto, una prima idea di partenza consisterebbe nell'approssimare un elemento tramite una ridotta $m$-esima della serie che lo definisce. In tal modo, scegliendo una ridotta con un numero sufficientemente grande di addendi, si otterebbe un'approssimazione dell'elemento considerato buona a piacere. Se dal punto di visto puramente teorico una soluzione come quella appena presentata risolve il problema, dal punto di vista della sua applicabilità nel concreto (studio per esempio di enormi moli di dati) questa presenta in particolare due limiti evidenti. In primo luogo, l'enorme costo a livello di memoria che potrebbe chiedere la memorizzazione di un elemento: per lavorare con una buona approssimazione potrebbe essere necessario a priori considerare un elevato numero di coefficienti (numero inoltre variabile a seconda dell'elemento fissato); In secondo luogo, un'approssimazione di questo tipo richiederebbe che i coefficienti siano già noti, fatto che nuovamente può ripercuotersi in elevati costi computazionali antecedenti. La tesi in questione si propone, alla luce di quanto detto, di introdurre il lettore ad una nuova classe di algoritmi di approssimazione, la cosiddetta classe degli algoritmi greedy. Il principio di questi consiste, ad un certo passo, nel selezionare un elemento del sistema fissato cercando di massimizzare un apposito funzionale che dipende dal passo precedente. Tale elemento viene poi utilizzato per costruire una nuova approssimazione a partire da quella già in possesso. La scelta del funzionale e dei coefficienti presenti nell'elemento approssimante differenziano fra di loro i vari algoritmi greedy che verrano descritti. Ciascuno è contraddistinto da proprietà più o meno favorevoli a livello computazionale, come per esempio l'eventuale possibilità di costruire come elemento approssimante un'espansione in serie, da condizioni che ne limitano o meno l'applicabilità, da una propria velocità di convergenza. Si sottolinea inoltre che a partire dal secondo capitolo la scelta dei sistemi con cui lavorare non cadrà più su delle basi, come nel primo capitolo, ma su dei sistemi ridondanti (ovvero tali per cui un elemento può avere più rappresentazioni rispetto al sistema scelto) noti come dizionari. La scelta di operare con sistemi ridondanti è ancora una volta mossa da motivi computazionali (che qui non saranno trattati). Si pensi tuttavia all'importanza che alcuni sistemi ridondanti possiedono anche nella matematica teorica, come i frames e i sistemi di Gabor nell'analisi armonica.