Compressed sensing

Compressed sensing (espressione della lingua inglese, noto anche come compressive sensing, compressive sampling e sparse sampling) indica una tecnica per trovare soluzioni sparse di un sistema di equazioni lineari sottodeterminato. In elettrotecnica, in particolare nella teoria dei segnali, la tecnica di compressed sensing implica un processo di acquisizione e di ricostruzione di un segnale elettrico che è supposto essere sparso o comprimibile.

Storia

Vari campi scientifici hanno usato tecniche basate sullo spazio L1. In statistica, il metodo dei minimi quadrati, introdotto da Laplace, fu complementato mediante la norma L1. Conseguentemente all'introduzione della programmazione lineare e dell'algoritmo del simplesso, la norma L1 fu usata in statistica computazionale. In statistica teorica, la norma L1 fu usata da George W. Brown e da autori seguenti applicandola agli estimatori non distorti di mediana. Fu anche usata da Peter Huber e da altri studiosi della statistica robusta. La norma L1 fu anche usata nell'analisi dei segnali, per esempio, negli anni settanta, quando i sismologi costruirono immagini degli strati riflettenti posti all'interno della terra e basate su dati che non sembrano soddisfare il criterio di Nyquist–Shannon. La norma L1 fu usata nella tecnica numerica di matching pursuit nel 1993, nell'estimatore LASSO di Robert Tibshirani nel 1996 e nel problema di ottimizzazione basis pursuit in 1998. Al tempo già esistevano risultati teorici descriventi i casi in cui questi algoritmi erano in grado di recuperare soluzioni sparse, ma il tipo e il numero di misurazioni richieste erano sub-ottimali e solo successivamente furono grandemente migliorate mediante la tecnica di compressed sensing. Attorno al 2004 Emmanuel Candès, Terence Tao e David Donoho scoprirono importanti risultati sul numero minimo di dati necessari per ricostruire un'immagine nonostante questo numero fosse insufficiente sulla base del criterio di Nyquist–Shannon.

Sistema lineare sotto determinato

Un sistema sotto determinato di equazioni lineari ha più incognite che equazioni e generalmente ha un numero infinito di soluzioni. Tuttavia, se c'è un'unica soluzione sparsa al sistema sotto determinato, allora tale soluzione è recuperabile nell'ambito del compressed sensing. Non tutti i sistemi di equazioni lineari hanno soluzioni sparse.

Metodo di soluzione/ricostruzione

La tecnica compressed sensing si avvantaggia della ridondanza presente in molti segnali di interesse in quanto essi non rappresentano il puro rumore. In particolare, molti segnali sono sparsi, cioè, essi contengono molte componenti vicine a zero, quando vengono rappresentati in qualche dominio. Questa stessa intuizione è utilizzata in molte forme di compressione dati con perdita.

La tecnica di compressed sensing tipicamente inizia considerando una combinazione lineare pesata di campioni chiamati anche "misurazioni compressive" (compressive measurements) in una base differente da quella nella quale il segnale è noto essere sparso. I risultati trovati da David Donoho, Emmanuel Candès, Justin Romberg e Terence Tao, mostrarono che il numero di queste misurazioni può essere piccolo e ciò nonostante contenere tutta l'informazione a cui si è interessati. Quindi, il recupero dell'immagine originale implica la risoluzione di un'equazione matriciale sotto determinata poiché si parte da un numero di misurazioni che è inferiore al numero di pixel dell'immagine originale stessa. Tuttavia, il fatto che il segnale iniziale sia sparso consente di risolvere questo sistema di equazioni lineari sotto determinato.

La soluzione a tali problemi con la tecnica dei minimi quadrati consiste nel minimizzare la norma L2 cioè minimizzare l'ammontare di energia nel sistema. Questo è solitamente semplice dal punto di vista matematico (implicando solo la moltiplicazione di una matrice per la sua pseudo-inversa). Tuttavia, questo conduce a risultati non soddisfacenti in molte applicazioni pratiche nelle quali i coefficienti incogniti hanno energia non nulla.

Per rafforzare il vincolo di sparsità quando si risolvono sistemi sottodeterminati di equazioni lineari, si può minimizzare il numero di componenti non nulle della soluzione.

La cardinalità del numero di componenti non nulle di un vettore fu chiamata da David Donoho norma "norma" L0. Le virgolette suggeriscono due avvertenze. Primo, la norma L0, rappresentante il numero di componenti non nulle, non è propriamente una F-norma, in quanto non è continua nel suo argomento scalare: nnzs(αx) è costante come α si approssima a zero. Sfortunatamente, i successivi autori hanno tralasciato le virgolette introdotte da Donoho compiendo un abuso di notazione, collidendo con l'uso consolidato della norma L0 per lo spazio delle funzioni misurabili (equipaggiato con una metrica appropriata) o per lo spazio delle successioni con F-norma $(x_{n})\mapsto \sum _{n}{2^{-n}x_{n}/(1+x_{n})}$.

Candès. et. al., dimostrarono che per molti problemi è probabile che la norma L1 sia equivalente alla norma L0, in termini tecnici: questo risultato di equivalenza permette di risolvere il problema L1, il quale è più semplice del problema L0. La ricerca del candidato con la norma L1 minore può essere espressa in maniera relativamente semplice come un programma lineare, per il quale esistono metodi di risoluzione efficienti. Quando le misure possono contenere un ammontare finito di rumore, la tecnica di basis pursuit denoising è preferibile rispetto alla programmazione lineare, in quanto essa preserva la sparsità a dispetto della presenza di rumore e può condurre a risoluzioni più rapide rispetto ad un programma lineare.

Implementazioni

Il campo del compressive sensing è collegato ad altri argomenti dell'analisi dei segnali e della computazione matematica, quali i sistemi di equazioni sottodeterminati, i problemi aventi come obbiettivo la riduzione del costo di individuazione degli elementi di un insieme (group testing), la codificazione in forma sparsa delle informazioni nell'ambito degli studi di codifica neurale, la multiplazione, il campionamento sparso, lo studio della velocità di crescita finita dell'innovazione. Le tecniche applicate nell'ambito della scienza delle immagini hanno una forte affinità con la tecnica di compressive sensing inclusa l'apertura codificata (coded aperture) impiegata per la rilevazione strumentale selettiva di immagini (ad esempio in ambito astronomico o radiologico) e la fotografia computazionale.

A partire dalla camera a singolo pixel della Università Rice, una lista aggiornata delle più recenti implementazioni pratiche della tecnica di compressive sensing nei differenti livelli di implementazione tecnologica (Technology readiness level) è disponibile. Alcune implementazioni pratiche (tipo quella usata nella ricostruzione di immagini a risonanza magnetica o in genotipazione quando certe informazioni genetiche assumono una forma sparsa) non richiedono una modifica fisica effettiva mentre altre richiedono una sostanziale re-ingegnerizzazione per eseguire questo nuovo tipo di campionamento del segnale. Similmente, prima del 2004 già esisteva un certo numero di implementazioni pratiche. Tuttavia, se da una parte il segnale era acquisito in forma compressa, dall'altra la ricostruzione del segnale originale non sfruttava la tecnica di compressive sensing. I risultati di tali ricostruzioni erano sub-ottimali mentre ora sono stati grandemente migliorati proprio grazie alla tecnica di compressive sensing.

Compressive sensing in giornali e riviste

La tecnica di compressive sensing è stata citata nella camera a pixel singolo dell'Università di Rice. Vari aspetti della tecnica sono stati caratterizzati nell'articolo "Engineers Test Highly Accurate Face Recognition". della rivista Wired. Un articolo di Wired più recente, "Using Math to Turn Lo-Res Datasets Into Hi-Res Samples", descrive la tecnica di compressive sensing come una tecnica già matura. Tuttavia poiché l'argomento dell'articolo era la tecnica di immagini mediante risonanza magnetica, RMI, qualche confusione può essere sorta. Attualmente, le tecniche di Compressive Sensing sono applicate in numerosi ambiti al di là della compressione e ricostruzione di immagini e video, quali ad esempio la sintesi di schiere di antenne, l'imaging radar, le tecniche di remote sensing and testing non distruttivo, e la rilevazione della direzione di arrivo di onde elettromagnetiche.

Bibliografia

• Using Math to Turn Lo-Res Datasets Into Hi-Res Samples articolo di Wired Magazine
• Compressive Sensing Resources all'Università di Rice.
• Compressed Sensing: The Big Picture, su igorcarron.googlepages.com. URL consultato il 9 marzo 2012 (archiviato dall'url originale il 22 agosto 2009).
• Una lista di differenti implementazioni pratiche della tecnica di Compressive Sensing, su igorcarron.googlepages.com. URL consultato il 9 marzo 2012 (archiviato dall'url originale il 22 agosto 2009).
• Compressed Sensing 2.0, su compressedsensing.googlepages.com. URL consultato il 9 marzo 2012 (archiviato dall'url originale il 22 agosto 2009).
• Compressed Sensing Makes Every Pixel Count – articolo della serie What's Happening in the Mathematical Sciences dell'AMS.
• Nuit Blanche Un blog sulla tecnica di Compressive Sensing caratterizzato dalle informazioni più recenti in materia (preprint, presentation, Q/As)
• Online Talks focused on Compressive Sensing, su igorcarron.googlepages.com. URL consultato il 9 marzo 2012 (archiviato dall'url originale il 28 agosto 2009).

Voci correlate

• Noiselet