Compressed sensing: differenze tra le versioni

Versione delle 11:10, 20 feb 2016

Versione attuale delle 20:43, 18 mar 2024

(18 versioni intermedie di 12 utenti non mostrate)

Riga 1:

Il termine '''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 lineare|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 [[Matrice sparsa|sparso]] o [[Compressione dei dati|comprimibile]].

==Storia==

Vari campi scientifici hanno usato tecniche<ref>[httphttps://2.bp.blogspot.com/_0ZCyAOBrUtA/TTwqLEeLvdI/AAAAAAAAEXI/7S0_SnWoC0E/s1600/l1-minimization.JPG List of L1 regularization ideas] from Vivek Goyal, Alyson Fletcher, Sundeep Rangan, [http://www.math.uiuc.edu/%7Elaugesen/imaha10/goyal_talk.pdf The Optimistic Bayesian: Replica Method Analysis of Compressed Sensing]</ref> basate sullo spazio [[Spazio Lp|L1]]. In statistica, il [[metodo dei minimi quadrati]], introdotto da Laplace, fu complementato mediante la norma [[Spazio Lp|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 [[Stimatore corretto|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 [[Teorema del campionamento di Nyquist-Shannon|Nyquist–Shannon]].<ref>[httphttps://www.americanscientist.org/issues/pub/the-best-bits/7 Hayes, Brian, ''The Best Bits'', American Scientist, July 2009] {{webarchive|url=https://web.archive.org/web/20100412153356/http://www.americanscientist.org/issues/pub/the-best-bits/7 |data=12 aprile 2010 }}</ref> La norma L1 fu usata nella tecnica numerica di ''[[matching pursuit]]'' nel 1993, nell'estimatore LASSO di [[Robert Tibshirani]] nel 1996<ref>[http://www-stat.stanford.edu/~tibs/lasso.html The Lasso page], at Robert Tibshirani's homepage. "Regression shrinkage and selection via the lasso". J. Royal. Statist. Soc B., Vol. 58, No. 1, pages 267-288</ref> e nel problema di ottimizzazione ''[[basis pursuit]]'' in 1998.<ref>"Atomic decomposition by basis pursuit", by Scott Shaobing Chen, David L. Donoho, Michael, A. Saunders. SIAM Journal on Scientific Computing</ref> 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 [[Teorema del campionamento di Nyquist-Shannon|criterio di Nyquist–Shannon]].<ref>E. J. Candès, J. Romberg and T. Tao. Stable signal recovery from incomplete and inaccurate measurements. Comm. Pure Appl. Math., 59 1207-1223, 2006 [http://www-stat.stanford.edu/~candes/papers/StableRecovery.pdf] {{Webarchive|url=https://web.archive.org/web/20120311192231/http://www-stat.stanford.edu/~candes/papers/StableRecovery.pdf|data=11 marzo 2012}}</ref><ref name="Donoho">Donoho, D. L., ''Compressed Sensing'', IEEE Transactions on Information Theory, V. 52(4), 1289–1306, 2006 [http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1614066]</ref>

==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.

Line 17 ⟶ 16:

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 (matematica)|"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]] <math>(x_n) \mapsto \sum_n{2^{-n} x_n/(1+x_n)}</math>.<ref>Stefan Rolewicz. ''Metric Linear Spaces''.</ref>

[[Emmanuel Candès|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.<ref>[http://www.acm.caltech.edu/l1magic/ L1-MAGIC is a collection of MATLAB routines]</ref> 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]]<ref>Pouryazdanpanah Kermani, Ali. "[https://pdfs.semanticscholar.org:443/1d44/68b6c27584851e15fd28a587d51d9ff62414.pdf Sparse MRI and CT Reconstruction.] {{Webarchive|url=https://web.archive.org/web/20190917181815/https://pdfs.semanticscholar.org/1d44/68b6c27584851e15fd28a587d51d9ff62414.pdf |date=17 settembre 2019 }}" (2017).</ref>.

A partire dalla camera a singolo pixel<ref name=cscamera>[{{Cita web|url=http://dsp.rice.edu/cscamera |titolo=Compressive Imaging: A New Single-Pixel Camera | sito=Rice DSP<!--University|lingua=en|accesso=17 Titologiugno generato2021|urlarchivio=https://web.archive.org/web/20161231160210/http://dsp.rice.edu/cscamera|dataarchivio=31 automaticamentedicembre -->]2016}}</ref> 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.<ref>Compressive Sensing Hardware, httphttps://sites.google.com/site/igorcarron2/compressedsensinghardware {{Webarchive|url=https://web.archive.org/web/20201101135833/https://sites.google.com/site/igorcarron2/compressedsensinghardware |date=1 novembre 2020 }}</ref> Alcune implementazioni pratiche (tipo quella usata nella ricostruzione di [[Imaging a risonanza magnetica|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''.

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<ref name=cscamera>[http://dsp.rice.edu/cscamera Compressive Imaging: A New Single-Pixel Camera | Rice DSP<!-- Titolo generato automaticamente -->]</ref> 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.<ref>Compressive Sensing Hardware, http://sites.google.com/site/igorcarron2/compressedsensinghardware</ref> Alcune implementazioni pratiche (tipo quella usata nella ricostruzione di [[Imaging a risonanza magnetica|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<ref name=cscamera/> a pixel singolo dell'[[Università Rice|Università di Rice]]. Vari aspetti della tecnica sono stati caratterizzati nell'articolo "Engineers Test Highly Accurate Face Recognition".<ref>[httphttps://www.wired.com/science/discoveries/news/2008/03/new_face_recognition Engineers Test Highly Accurate Face Recognition]</ref> della rivista Wired. Un articolo di Wired più recente, "Using Math to Turn Lo-Res Datasets Into Hi-Res Samples",<ref>[httphttps://www.wired.com/magazine/2010/02/ff_algorithm/all/1 Fill in the Blanks: Using Math to Turn Lo-Res Datasets Into Hi-Res Samples | Wired Magazine | Wired.com<!-- Titolo generato automaticamente -->]</ref> 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, [[Imaging a risonanza magnetica|RMI]], qualche confusione può essere sorta.<ref>[httphttps://nuit-blanche.blogspot.com/2010/03/why-compressed-sensing-is-not-csi.html Why Compressed Sensing is NOT a CSI "Enhance" technology ... yet !]</ref><ref>[httphttps://nuit-blanche.blogspot.com/2010/03/surely-you-must-be-joking-mr.html Surely You Must Be Joking Mr. Screenwriter]</ref> 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 [[schiera di antenne|schiere di antenne]], l'''imaging radar'', le tecniche di ''remote sensing eand testing'' non distruttivo, e la rilevazione della direzione di arrivo di onde elettromagnetiche<ref>{{Cita pubblicazione|autore = Andrea Massa, Paolo Rocca, Giacomo Oliveri|titolo = Compressive Sensing in Electromagnetics - A Review|rivista = IEEE Antennas and Propagation Magazine|volume = 57|numero = 1|anno = 2015|pp = 224-238|doi = 10.1109/MAP.2015.2397092|url = http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7046378}}</ref>.

== Note ==

La tecnica di ''compressive sensing'' è stata citata nella camera<ref name=cscamera/> a pixel singolo dell'[[Università Rice|Università di Rice]]. Vari aspetti della tecnica sono stati caratterizzati nell'articolo "Engineers Test Highly Accurate Face Recognition".<ref>[http://www.wired.com/science/discoveries/news/2008/03/new_face_recognition Engineers Test Highly Accurate Face Recognition]</ref> della rivista Wired. Un articolo di Wired più recente, "Using Math to Turn Lo-Res Datasets Into Hi-Res Samples",<ref>[http://www.wired.com/magazine/2010/02/ff_algorithm/all/1 Fill in the Blanks: Using Math to Turn Lo-Res Datasets Into Hi-Res Samples | Wired Magazine | Wired.com<!-- Titolo generato automaticamente -->]</ref> 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, [[Imaging a risonanza magnetica|RMI]], qualche confusione può essere sorta.<ref>[http://nuit-blanche.blogspot.com/2010/03/why-compressed-sensing-is-not-csi.html Why Compressed Sensing is NOT a CSI "Enhance" technology ... yet !]</ref><ref>[http://nuit-blanche.blogspot.com/2010/03/surely-you-must-be-joking-mr.html Surely You Must Be Joking Mr. Screenwriter]</ref> 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 e testing non distruttivo, e la rilevazione della direzione di arrivo di onde elettromagnetiche<ref>{{Cita pubblicazione|autore = Andrea Massa, Paolo Rocca, Giacomo Oliveri|titolo = Compressive Sensing in Electromagnetics - A Review|rivista = IEEE Antennas and Propagation Magazine|volume = 57|numero = 1|anno = 2015|pp = 224-238|doi = 10.1109/MAP.2015.2397092|url = http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7046378}}</ref>.

{{<references}}/>

== Bibliografia ==

* [httphttps://www.wired.com/magazine/2010/02/ff_algorithm/all/1 Using Math to Turn Lo-Res Datasets Into Hi-Res Samples] articolo di Wired Magazine

* [http://arquivo.pt/wayback/20160516193158/http://dsp.rice.edu/cs/ Compressive Sensing Resources] all'[[Università Rice|Università di Rice]].

* {{cita web | 1 = http://igorcarron.googlepages.com/cs | 2 = Compressed Sensing: The Big Picture | accesso = 9 marzo 2012 | dataarchivio = 22 agosto 2009 | urlarchivio = https://web.archive.org/web/20090822094803/http://igorcarron.googlepages.com/cs | urlmorto = sì }}

* {{cita web | 1 = http://igorcarron.googlepages.com/compressedsensinghardware | 2 = Una lista di differenti implementazioni pratiche della tecnica di ''Compressive Sensing'' | accesso = 9 marzo 2012 | dataarchivio = 22 agosto 2009 | urlarchivio = https://web.archive.org/web/20090822123227/http://igorcarron.googlepages.com/compressedsensinghardware | urlmorto = sì }}

* {{cita web | 1 = http://compressedsensing.googlepages.com/home | 2 = ''Compressed Sensing'' 2.0 | accesso = 9 marzo 2012 | dataarchivio = 22 agosto 2009 | urlarchivio = https://web.archive.org/web/20090822231531/http://compressedsensing.googlepages.com/home | urlmorto = sì }}

* [http://www.ams.org/happening-series/hap7-pixel.pdf Compressed Sensing Makes Every Pixel Count] – articolo della serie ''What's Happening in the Mathematical Sciences'' dell'[[American Mathematical Society|AMS]].

* [httphttps://nuit-blanche.blogspot.com/search/label/CS Nuit Blanche] Un [[blog]] sulla tecnica di ''Compressive Sensing'' caratterizzato dalle informazioni più recenti in materia (''preprint'', ''presentation'', Q/As)

* {{cita web | 1 = http://igorcarron.googlepages.com/csvideos | 2 = Online Talks focused on Compressive Sensing | accesso = 9 marzo 2012 | dataarchivio = 28 agosto 2009 | urlarchivio = https://web.archive.org/web/20090828154350/http://igorcarron.googlepages.com/csvideos | urlmorto = sì }}

== Voci correlate ==

* [[Noiselet]]

{{Controllo di autorità}}

== Note ==

{{Portale|matematica|elettronica}}

{{references}}

== Letture ulteriori ==

* [http://www.wired.com/magazine/2010/02/ff_algorithm/all/1 Using Math to Turn Lo-Res Datasets Into Hi-Res Samples] articolo di Wired Magazine

* [http://dsp.rice.edu/cs Compressive Sensing Resources] all'[[Università Rice|Università di Rice]].

* {{cita web|http://igorcarron.googlepages.com/cs|Compressed Sensing: The Big Picture}}

* {{cita web|http://igorcarron.googlepages.com/compressedsensinghardware|Una lista di differenti implementazioni pratiche della tecnica di ''Compressive Sensing''}}

* {{cita web|http://compressedsensing.googlepages.com/home|''Compressed Sensing'' 2.0}}

* [http://www.ams.org/happening-series/hap7-pixel.pdf Compressed Sensing Makes Every Pixel Count] – articolo della serie ''What's Happening in the Mathematical Sciences'' dell'[[American Mathematical Society|AMS]].

* [http://nuit-blanche.blogspot.com/search/label/CS Nuit Blanche] Un blog sulla tecnica di ''Compressive Sensing'' caratterizzato dalle informazioni più recenti in materia (''preprint'', ''presentation'', Q/As)

* {{cita web|http://igorcarron.googlepages.com/csvideos|Online Talks focused on Compressive Sensing}}

{{Portale|matematica}}

[[Categoria:Teoria dell'informazione]]

[[Categoria:Teoria dei segnali]]

[[Categoria:Algebra lineare]]

[[Categoria:Analisi di regressione]]

[[Categoria:Ottimizzazione]]

[[Categoria:Teoria dell'informazione]]

[[Categoria:Teoria dei segnali]]