Regularization techniques based on Krylov subspace methods for ill-posed linear systems

This thesis is focussed on the regularization of large-scale linear discrete ill-posed problems. Problems of this kind arise in a variety of applications, and, in a continuous setting, they are often formulated as Fredholm integral equations of the first kind, with smooth kernel, modeling an inverse problem (i.e., the unknown of these equations is the cause of an observed effect). Upon discretization, linear systems whose coefficient matrix is ill-conditioned and whose right-hand side vector is affected by some perturbations (noise) must be solved. %Because of the ill-conditioning of the system matrix and the errors in the data, In this setting, a straightforward solution of the available linear system is meaningless because the computed solution would be dominated by errors; moreover, for large-scale problems, solving directly the available system could be computationally infeasible. Therefore, in order to recover a meaningful approximation of the original solution, some regularization must be employed, i.e., the original linear system must be replaced by a nearby problem having better numerical properties. The first part of this thesis (Chapter 1) gives an overview on inverse problems and briefly describes their properties in the continuous setting; then, in a discrete setting, the most well-known regularization techniques relying on some factorization of the system matrix are surveyed. The remaining part of the thesis is concerned with iterative regularization strategies based on some Krylov subspaces methods, which are well-suited for large-scale problems. More precisely, in Chapter 2, an extensive overview of the Krylov subspace methods most successfully employed with regularizing purposes is presented: historically, the first methods to be used were related to the normal equations and many issues linked to the analysis of their behavior have already been addressed. The situation is different for the methods based on the Arnoldi algorithm, whose regularizing properties are not well understood or widely accepted, yet. Therefore, still in Chapter 2, a novel analysis of the approximation properties of the Arnoldi algorithm when employed to solve linear discrete ill-posed problems is presented, in order to provide some insight on the use of Arnoldi-based methods for regularization purposes. The core results of this thesis are related to class of the Arnoldi-Tikhonov methods, first introduced about ten years ago, and described in Chapter 3. The Arnoldi-Tikhonov approach to regularization consists in solving a Tikhonov-regularized problem by means of an iterative strategy based on the Arnoldi algorithm. With respect to a purely iterative approach to regularization, Arnoldi-Tikhonov methods can deliver more accurate approximations by easily incorporating some information about the behavior of the solution within the reconstruction process. In connection with Arnoldi-Tikhonov methods, many open questions still remain, the most significant ones being the choice of the regularization parameters and the choice of the regularization matrices. The first issues are addressed in Chapter 4, where two new efficient and original parameter selection strategies to be employed with the Arnoldi-Tikhonov methods are derived and extensively tested; still in Chapter 4, a novel extension of the Arnoldi-Tikhonov method to the multi-parameter Tikhonov regularization case is described. Finally, in Chapter 5, two efficient and innovative schemes to approximate the solution of nonlinear regularized problems are presented: more precisely, the regularization terms originally defined by the 1-norm or by the Total Variation functional are approximated by adaptively updating suitable regularization matrices within the Arnoldi-Tikhonov iterations. Along this thesis, the results of many numerical experiments are presented in order to show the performance of the newly proposed methods, and to compare them with the already existing strategies.Questa tesi è incentrata sulle tecniche di regolarizzazione per problemi lineari discreti malposti e di grandi dimensioni. Molteplici applicazioni fisiche ed ingegneristiche sono modellate da questo genere di problemi che, in ambito continuo, sono spesso formulati mediante equazioni integrali di Fredholm di prima specie con nucleo regolare. Più precisamente, queste equazioni modellano i cosiddetti problemi inversi, cioè problemi in cui la causa di un effetto osservato deve essere ricostruita. Una volta discretizzati, questi problemi si presentano come sistemi lineari, la cui matrice dei coefficienti è fortemente malcondizionata e il cui vettore dei termini noti è affetto da qualche perturbazione (spesso chiamata rumore). In questo contesto, risolvere direttamente il sistema lineare discretizzato produrrebbe una soluzione priva di significato, in quanto pesantemente dominata da errori; inoltre, a causa delle grandi dimensioni del sistema, tale procedimento potrebbe risultare infattibile, perchè computazionalmente troppo costoso. Pertanto, qualche forma di regolarizzazione deve essere applicata in modo da poter calcolare una approssimazione fisicamente significativa della soluzione esatta del problema trattato: regolarizzare significa appunto sostituire il sistema lineare con un problema ad esso collegato ma avente migliori proprietà numeriche. La prima parte di questa tesi (Capitolo 1) offre una panoramica sui problemi inversi e descrive brevemente le loro proprietà nel continuo. Quindi, nel discreto, vengono esaminati i più comuni metodi di regolarizzazione basati su una qualche fattorizzazione della matrice del sistema. La restante parte della tesi riguarda le tecniche di regolarizzazione iterative che consistono nell'applicazione di metodi di Krylov: questo tipo di regolarizzazione è particolarmente appropriato quando devono essere risolti sistemi lineari di grandi dimensioni. Più precisamente, nel Capitolo 2, viene proposta un'accurata descrizione dei metodi di Krylov più popolari nell'ambito della regolarizzazione: storicamente, i primi metodi ad essere utilizzati a tale scopo sono stati quelli legati alle equazioni normali e le proprietà regolarizzanti di molti di essi sono già state analizzate. Per quanto riguarda i metodi basati sull'algoritmo di Arnoldi, la situazione è differente: nella maggior parte dei casi, le loro proprietà regolarizzanti non sono ancora state rigorosamente studiate. Pertanto, sempre nel Capitolo 2, viene proposta un'analisi originale delle proprietà approssimanti dell'algoritmo di Arnoldi nel caso in cui esso venga impiegato per la risoluzione di sistemi lineari malposti: l'obbiettivo di questa analisi è di fornire maggiori spiegazioni riguardo all'utilizzo dei metodi basati sull'algoritmo di Arnoldi per la regolarizzazione. I risultati più significativi presentati nella tesi riguardano la classe dei metodi di tipo Arnoldi-Tikhonov, introdotti per la prima volta una decina di anni fa e descritti nel Capitolo 3. L'approccio di tipo Arnoldi-Tikhonov consiste nel risolvere, mediante un metodo iterativo basato sull'algoritmo di Arnoldi, un problema regolarizzato tramite il metodo di Tikhonov. Rispetto ad un approccio regolarizzante puramente iterativo, i metodi di tipo Arnoldi-Tikhonov sono in grado di calcolare soluzioni approssimate più accurate, in quanto all'interno del procedimento iterativo di tipo Arnoldi-Tikhonov possono essere facilmente incorporate alcune informazioni sul comportamento e sulla regolarità della soluzione. Fra i maggiori problemi aperti legati all'utilizzo dei metodi di tipo Arnoldi-Tikhonov figurano la ricerca di metodi efficienti per la scelta dei parametri di regolarizzazione e la scelta di opportune matrici di regolarizzazione. Le problematiche relative alla scelta dei parametri sono trattate nel Capitolo 4, dove vengono derivate due nuove tecniche che possono essere utilizzate congiuntamente ai metodi di tipo Arnoldi-Tikhonov; sempre nel Capitolo 4 viene descritta una nuova estensione del metodo di Arnoldi-Tikhonov al caso della regolarizzazione di Tikhonov a più parametri. Infine, nel Capitolo 5, vengono presentate due innovative ed efficienti strategie per approssimare la soluzione di problemi regolarizzati nonlineari: più precisamente, i termini di regolarizzazione inizialmente definiti utilizzando la norma 1 o il funzionale di Variazione Totale (TV) sono approssimati mediante opportune matrici di regolarizzazione che vengono aggiornate adattivamente durante le iterazioni del metodo di Arnoldi-Tikhonov. In generale, nel corso della trattazione, vengono illustrati i risultati di molteplici esperimenti numerici, con l'obbiettivo di mostrare il comportamento dei nuovi metodi proposti e di confrontarli con quelli già esistenti