Fondamenti di Compressed Sensing

Abstract

L'oggetto di questa tesi è il compressed sensing, una tecnica che consente la ricostruzione di segnali sparsi a partire da un numero ridotto di misurazioni lineari. A differenza delle tecniche classiche, che richiedono un numero di misurazioni almeno pari alla dimensione del segnale, il compressed sensing sfrutta la sparsità dei dati per ottenere una ricostruzione esatta anche quando il numero di misurazioni è molto minore

Dopo una breve introduzione al problema, vengono introdotte due condizioni sull'operatore di misurazione: la Null Space Property e la Restricted Isometry Property (RIP). La Null Space Property garantisce la ricostruzione esatta di vettori sparsi tramite minimizzazione della norma 1 (nota come basis pursuit), mentre la RIP fornisce un modo semplice per verificare che la Null Space Property sia rispettata.

La tesi prosegue con l’analisi delle matrici gaussiane, dimostrando che esse soddisfano la RIP con alta probabilità, a patto che il numero di misurazioni cresca linearmente a meno di termini logaritmici rispetto alla sparsità. Viene quindi presentata una stima esplicita del numero minimo di misurazioni necessarie per la ricostruzione.

Infine, tramite simulazioni numeriche realizzate in MATLAB, si verifica sperimentalmente il successo del metodo di basis pursuit. I risultati confermano l’efficacia del compressed sensing anche in casi reali, evidenziando la relazione quasi lineare tra sparsità del segnale e numero di misurazioni richieste.

The subject of this thesis is compressed sensing, a technique that allows the reconstruction of sparse signals from a small number of linear measurements. Unlike classical techniques, which require a number of measurements at least equal to the size of the signal, compressed sensing exploits the sparsity of the data to achieve an exact reconstruction even when the number of measurements is much smaller

After a brief introduction to the problem, two conditions on the measurement operator are introduced: the Null Space Property and the Restricted Isometry Property (RIP). The Null Space Property guarantees the exact reconstruction of sparse vectors by 1-norm minization (known as basis pursuit), while the RIP provides a simple way of verifying that the Null Space Property is respected.

The thesis continues with an analysis of Gaussian matrices, showing that they satisfy RIP with high probability, provided that the growth of the number of measurements with respect to sparsity is linear with the addition of logarithmic terms. An explicit estimate of the minimum number of measurements required for reconstruction is then presented.

In conclusion, the success of the basis pursuit method is experimentally verified through numerical simulations in MATLAB. The results confirm the effectiveness of compressed sensing in real cases, highlighting the almost linear relationship between signal sparsity and the number of measurements required.