COmpRessed SolvING: sparse approximation of PDEs based on compressed sensing

In this thesis, we deal with a new framework for the numerical approximation of partial differential equations which employs main ideas and tools from compressed sensing in a Petrov-Galerkin setting. The goal is to compute an s-sparse approximation with respect to a trial basis of dimension N (with s << N) by picking m << N randomly chosen test functions, and to employ sparse optimization techniques to solve the resulting m x N underdetermined linear system. This approach has been named COmpRessed SolvING (in short, CORSING). First, we carry out an extensive numerical assessment of CORSING on advection-diffusion-reaction equations, both in a one- and a two-dimensional setting, showing that the proposed strategy is able to reduce the computational burden associated with a standard Petrov-Galerkin formulation. Successively, we focus on the theoretical analysis of the method. In particular, we prove recovery error estimates both in expectation and in probability, comparing the error associated with the CORSING solution with the best s-term approximation error. With this aim, we propose a new theoretical framework based on a variant of the classical inf-sup property for sparse vectors, that is named Restricted Inf-Sup Property, and on the concept of local a-coherence, that generalizes the notion of local coherence to bilinear forms in Hilbert spaces. The recovery results and the corresponding hypotheses are then theoretically assessed on one-dimensional advection-diffusion-reaction problems, while in the two-dimensional setting the verification is carried out through numerical tests. Finally, a preliminary application of CORSING to three-dimensional advection-diffusion-reaction equations and to the two-dimensional Stokes problem is also provided.

In questa tesi viene proposto un nuovo metodo per l’approssimazione numerica di equazioni differenziali alle derivate parziali, basato sull’applicazione di tecniche e idee del compressed sensing a discretizzazioni di tipo Petrov-Galerkin. L’obiettivo è quello di calcolare una approssimazione s-sparsa rispetto ad una base trial di dimensione N (con s << N), selezionando m << N funzioni test in maniera randomizzata e, successivamente, risolvere il sistema sottodeterminato ottenuto, di dimensione m × N, tramite tecniche di ottimizzazione sparsa. Questo approccio è stato denominato COmpRessed SolvING (in breve, CORSING). In primis, viene condotta una vasta indagine numerica del CORSING su equazioni di tipo diffusione-trasporto-reazione monodimensionali e bidimensionali, mostrando come la strategia proposta sia capace di ridurre il costo computazionale associato a discretizzazioni di Petrov-Galerkin standard. Successivamente, il metodo viene studiato dal punto di vista teorico. In particolare, si dimostrano delle stime di errore in valore atteso e in probabilità, mettendo a confronto l’errore della soluzione CORSING e l’errore di miglior approssimazione s-sparsa. L’analisi teorica è basata su una variante della classica proprietà di inf-sup per vettori sparsi, denominata proprietà di inf-sup ristretta, e sul concetto di a-coerenza locale, che generalizza la nozione di coerenza locale al caso di forme bilineari su spazi di Hilbert. I risultati teorici e le corrispettive ipotesi vengono poi specializzati al caso di equazioni di diffusione-traporto-reazione monodimensionali, mentre nel caso bidimensionale le ipotesi vengono verificate numericamente. Infine, risultati preliminari mostrano come il CORSING possa essere applicato al caso di equazioni di diffusione-trasporto-reazione tridimensionali e al problema di Stokes bidimensionale.