Komprimerad avkänning utlöser en stor utveckling inom signalförvärv. Den består av provtagning av en gles signal med låg hastighet och senare användning av beräkningskraft för dess exakta rekonstruktion, så att endast den nödvändiga informationen mäts. För närvarande används dock rekonstruktionstekniker som är begränsade till förvärvsfrekvenser som är större än signalens verkliga densitet. Vi utformar ett nytt förfarande som kan rekonstruera exakt signalen med ett antal mätningar som närmar sig den teoretiska gränsen i gränsen för stora system. Den bygger på gemensam användning av tre viktiga ingredienser: en probabilistisk inställning till signalrekonstruktion, en meddelandepasserande algoritm anpassad från trosförökning, och en noggrann utformning av mätmatrisen inspirerad av teorin om kristallkärnor. Prestandan av denna nya algoritm analyseras med statistiska fysikmetoder. Den uppnådda förbättringen bekräftas av numeriska studier av flera fall. Förmågan att återvinna högdimensionella signaler med endast ett begränsat antal mätningar är avgörande inom många områden, allt från bildbehandling till astronomi eller systembiologi. Exempel på direkta tillämpningar är att påskynda magnetisk resonanstomografi utan att förlora upplösning, avkänning och kompression av data samtidigt [1] och enpixelkameran [2]. Komprimerad avkänning är utformad för att direkt förvärva endast nödvändig information om signalen. Detta är möjligt när signalen är sparsam i någon känd grund. I ett andra steg använder man beräkningskraft för att rekonstruera signalen exakt [1, 3, 4]. För närvarande är den mest kända generiska metoden för exakt rekonstruktion baserad på att omvandla återuppbyggnadsproblemet till en konvex optimering, som kan lösas effektivt med linjär programmeringsteknik [3, 4]. Den 1 rekonstruktion kan rekonstruera exakt, förutsatt att systemets storlek är stor och förhållandet mellan antalet mätningar M till antalet icke-noll K överstiger en specific gräns som kan bevisas genom noggrann analys [4, 5]. Den begränsande kvoten är dock avsevärt större än 1. I detta dokument förbättrar vi prestandan av 1 minimering, och på bästa möjliga sätt: vi introducerar ett nytt förfarande som kan nå den optimala gränsen M/K → 1. Detta förfarande, som vi kallar seeded Belief Propagation (s-BP) är baserat på en ny, noggrant utformad, mätmatris. Den är mycket kraftfull, som illustreras i bild. 1................................................................ Dess prestanda kommer att studeras här med en gemensam användning av numeriska och analytiska studier med hjälp av metoder från statistisk fysik [6]. Det matematiska problem som uppstår vid en komprimerad återuppbyggnad är lätt att förklara. Med tanke på en okänd signal som är en N-dimensionell vektor, gör vi M-mätningar, där varje mätning uppgår till en projektion av s på någon känd vektor. Mätningarna grupperas i en M-komponentvektorn y, som erhålls från s genom en linjär omvandling y = Fs. Beroende på applikationen kan denna linjära omvandling till exempel associeras med mätningar av Fourier-lägen eller vågets koefficienter. Observatören vet M × N matris F och M mätningar y, med M < N. Hans mål är att rekonstruera s. Detta är omöjligt i allmänhet, men komprimerad avkänning handlar om fallet där signalen s är gles, i den meningen att endast K < N av dess komponenter är icke-noll. Vi ska studera fallet där icke-nollkomponenterna är reella tal och mätningarna är linjärt oberoende. I detta fall är exakt signalrekonstruktion i princip möjlig när M ≥ K + 1, med hjälp av en uttömmande uppräkningsmetod som försöker lösa y = Fx för alla N K möjliga val av platser för icke-noll komponenter i x: endast ett sådant val ger ett konsekvent linjärt system, som sedan kan inverteras. Dock är man vanligtvis intresserad av stora fall där N 1, med M = αN och K = ρ 0 N. Uppräkningsmetoden löser problemet med komprimerad avkänning i systemet där mäthastigheten är minst lika stor som signaltätheten, α ≥ ρ 0, men i en tid som växer exponentiellt med N, vilket gör det helt opraktiskt. Därför är α = ρ 0 den grundläggande återuppbyggnadsgränsen för perfekt återuppbyggnad i det ljudlösa fallet, när icke-nollkomponenterna i signalen är reella tal hämtade från en kontinuerlig distribution. En allmän och detaljerad diskussion om informations-teoretiskt optimal återuppbyggnad
Vi introducerade sådda mätmatriser för CS i REF, och visade där, både numeriskt och med hjälp av densitetsutvecklingen, att med sådana matriser är det möjligt att uppnå den teoretiskt optimala mäthastigheten.
Statistical physics-based reconstruction in compressed sensing
{'venue': 'Phys. Rev. X 2, 021005 (2012)', 'journal': None, 'mag_field_of_study': ['Physics', 'Computer Science', 'Mathematics']}