Kompressionsføling

Komprimeret sensing , også kendt som compressive sensing , compressive sampling og sparse sampling  , er teknikken til at erhverve og rekonstruere et signal ved at bruge viden om dets tidligere værdier, der er sparsomme eller komprimerede. Dette felt af signalbehandling har eksisteret i 40 år, men har først for nylig vundet bred accept, delvist takket være adskillige vigtige resultater af David Donoho , Emmanuel Candès , Justin Romberg og Terence Tao .

Historie

Idéerne til at beskrive kompressionsføling [1] begyndte i 2004, da Emanuel Cande, en Caltech -matematiker , arbejdede på problemer med magnetisk resonansbilleddannelse . Han opdagede, at testbilledet kunne rekonstrueres nøjagtigt selv med data, der anses for utilstrækkelige i henhold til Nyquist-Shannon-kriteriet . Derudover blev en forløber for komprimeret sansning set i 1970'erne, da seismologer byggede billeder af reflekterende niveauer i jorden baseret på data, der ikke så ud til at opfylde Nyquist-Shannon-kriteriet [2] .

Metode

Den grundlæggende idé er, at de fleste signaler af interesse har en vis struktur og redundans - de er ikke ren støj. Især er de fleste signaler sparsomme , det vil sige, at de indeholder mange koefficienter tæt på eller lig med nul, når de præsenteres på et eller andet grundlag [3] . (De samme ideer ligger til grund for mange former for komprimering med tab .)

Komprimeret sensing starter normalt med at tage et begrænset (muligvis tilfældigt) antal prøver til en anden basis end den, hvor signalet er sparsomt. Da antallet af samples er begrænset, vil opgaven med at konvertere billedet tilbage til målområdet indebære løsning af en underbestemt matrixligning  - det vil sige, at der er et stort antal forskellige kandidatbilleder, der kan resultere for en given prøve, da antallet af prøver er mindre end antallet af koefficienter i det fulde billede. Der skal derfor indføres en vis yderligere begrænsning for at udvælge den "bedste" kandidat.

Den klassiske løsning på sådanne problemer er at minimere normen  - det vil sige at minimere mængden af ​​energi i systemet. Dette er normalt simpel matematik (kun involverer matrix multiplikation ved hjælp af en pseudo -invers sampling basis). Dette fører dog til dårlige resultater for de fleste praktiske anvendelser, da ukendte (mangler i prøven) koefficienter sjældent har nul energi.

En mere attraktiv løsning ville være at minimere normen eller tilsvarende maksimere antallet af nulkoefficienter i det nye grundlag. Dette er dog et NP-hårdt problem (det inkluderer problemer med delmængdesum ) og er også beregningsmæssigt umuligt for alle undtagen de mindste datasæt. Ifølge ideerne fra Tao Terence et al. er det således sædvanligt at minimere den tilnærmende -norm eller summen i absolutte tal. Minimumsnormproblemet er formuleret som et lineært programmeringsproblem , hvortil der findes effektive løsningsmetoder. Dette fører til sammenlignelige resultater ved brug af normen, hvilket ofte resulterer i resultater, hvor mange af koefficienterne er nul.

Links

  1. ↑ Donoho, DL, Compressed Sensing , IEEE Transactions on Information Theory, V. 52(4), 1289-1306, 2006 [1] Arkiveret 26. juni 2010 på Wayback Machine
  2. ↑ Hayes, Brian, The Best Bits , American Scientist, juli 2009 Arkiveret 12. april 2010.
  3. ↑ Candès, EJ, & Wakin, MB, An Introduction To Compressive Sampling , IEEE Signal Processing Magazine, V.21, marts 2008 [2]

For yderligere læsning