翻譯 壓縮感知

壓縮感知1、范圍香濃/尼奎特斯采樣定理告訴我們當(dāng)我們采集一個(gè)信號(hào)，為了避免丟失信息，我們必須采集兩倍于原信號(hào)的頻率。在很多應(yīng)用領(lǐng)域包括數(shù)字成像和攝影機(jī)，尼奎特斯率對(duì)于它們太高了，我們會(huì)得到非常多的采樣樣品，并旦為了儲(chǔ)存和傳輸必須將它們壓縮。在另外的一些領(lǐng)域例如成像系統(tǒng)（醫(yī)學(xué)掃描儀，雷達(dá)）和高速模數(shù)轉(zhuǎn)換器，在超出當(dāng)代最先進(jìn)的水平下增加采樣頻率或密度的成本是非常高昂的。在本次講座中，我們將會(huì)了解到用來(lái)解決這些問(wèn)題的新技術(shù)一一壓縮感知。我們會(huì)一種更具通用性的最優(yōu)化的線性耦合測(cè)量方法來(lái)獲取一定的遠(yuǎn)遠(yuǎn)低于尼奎特斯率信號(hào)來(lái)取代傳統(tǒng)采樣和重構(gòu)方法。2、相關(guān)性這里提出的想法可以用來(lái)舉例說(shuō)明數(shù)據(jù)采集，線性代數(shù)，基礎(chǔ)擴(kuò)展，逆問(wèn)題，壓縮，降維和進(jìn)程優(yōu)化之間的關(guān)聯(lián)，從本科生或研究生的數(shù)字信號(hào)處理到統(tǒng)計(jì)數(shù)學(xué)和應(yīng)用數(shù)學(xué)。3、先決條件理解和講解本材料的預(yù)備知識(shí)是線性代數(shù)，基礎(chǔ)優(yōu)化和基礎(chǔ)概率。4、問(wèn)題陳述尼奎特斯率采樣通過(guò)利用信號(hào)的有限帶寬來(lái)完整的描述信號(hào)。我們的目標(biāo)是通過(guò)信號(hào)的可壓縮性來(lái)減少所需的測(cè)量量來(lái)描述完整信號(hào)。這要求我們不用點(diǎn)采樣的方法而用更普遍的線性函數(shù)的信號(hào)采集。假設(shè)一個(gè)實(shí)數(shù)域有限長(zhǎng)一維離散時(shí)間的信號(hào)X,我們把它看做RN中的n*1個(gè)列向量,睥中的元素為x［n］,n=l,2,...,N。我們把一個(gè)圖像或更高維度的數(shù)據(jù)向量化為一個(gè)長(zhǎng)的一維向量中。任何一個(gè)信號(hào)在rn中可以表示為基礎(chǔ)的n*i向量｛巾』i?］。為簡(jiǎn)單起見(jiàn)，假設(shè)基礎(chǔ)是正交的。通過(guò)把矩陣｛。i｝轉(zhuǎn)換形成N*N的基矩陣W:=［叩1餌項(xiàng)...I%］，我們可以把任何信號(hào)X表示為：X=Zi=lS］電。rX=Us（1）其中s是N*1列的加權(quán)系數(shù)向量si=<X,電>=甲以，其中.7表示轉(zhuǎn)置。亳無(wú)疑問(wèn)，X和S是同一信號(hào)的等價(jià)表示，X表示時(shí)域，S表示W(wǎng)域。我們把目光集中于具有稀疏性的信號(hào)，其中X是基向量的K線性組合且K?N。就是說(shuō)在（1）S,中只有K個(gè)非零值和（N-K）個(gè)零值。實(shí)際上，稀疏性使很多自然信號(hào)和人造信號(hào)具有可壓縮性，這就存在表現(xiàn)在（1）中的W，有很少的小系數(shù)和很多的大系數(shù)。可壓縮的信號(hào)可以近似表示為K-稀疏值；這是轉(zhuǎn)換編碼的基礎(chǔ)。例如，JPEG和JPEG-2000壓縮標(biāo)準(zhǔn)就是自然圖像可以用離散余弦變換和小波變換壓縮。音頻信號(hào)和許多通信信號(hào)在局部傅里葉變換基中是可壓縮的。轉(zhuǎn)換編碼在數(shù)據(jù)收集系統(tǒng)中扮演了中心角色,例如數(shù)碼相機(jī)采樣數(shù)量非常高但信號(hào)是可壓縮的。在這個(gè)框架中，我們獲取完整的N-采樣信號(hào)X：通過(guò)S=W『X計(jì)算完整的轉(zhuǎn)換系數(shù)伉｝：查找K個(gè)最大系數(shù)，舍棄（N-K）個(gè)最小系數(shù)；并且將這K個(gè)值編碼定位這些最大系數(shù)。（在實(shí)際中，我們也把這些值和位置轉(zhuǎn)化為二進(jìn)制編碼。）不幸的是，這種采樣然后壓縮的框架有三個(gè)自身缺陷：第一，即使所需的K很少，我們也必須開(kāi)始時(shí)采集大量潛在的N點(diǎn)。第二，即使只需要K個(gè)轉(zhuǎn)置系數(shù)，編碼器也必須計(jì)算所有的N個(gè)轉(zhuǎn)置系數(shù)伉｝°第三，編碼器要面對(duì)大系數(shù)定位編碼的開(kāi)銷。作為一種選擇，我們將學(xué)習(xí)一種更為普遍的數(shù)據(jù)收集方法，將信號(hào)直接用壓縮表示而不

必經(jīng)過(guò)采樣N點(diǎn)的中間步驟。運(yùn)用一種更為普遍的線性測(cè)量過(guò)程計(jì)算X和收集向量沽｝中M<N個(gè)內(nèi)積，設(shè)h=<X,兮〉。將測(cè)量值弘轉(zhuǎn)置成為M*1的向量y并且把測(cè)量向量作為行形成一個(gè)M*N的矩陣①，并將其代入（1）式，得到：Y=（Dx=（D,4Js=0s（2）其中0：=（DW是一個(gè)M*N的矩陣。圖1（a）是（2）的描述。注意測(cè)量過(guò)程是非適應(yīng)性的。就是說(shuō)（D不取決于信號(hào)X。接下來(lái)我們的目標(biāo)是設(shè)計(jì)一個(gè)測(cè)量矩陣（D和一個(gè)基于K—稀疏旦可壓縮信號(hào)的重構(gòu)算法，只要獲得M@K或者稍多一點(diǎn)的測(cè)量值或者與傳統(tǒng)變換編碼一樣多的測(cè)量值。我們的方法是基于最近的壓縮感知理論。5、解決方法解決方法包括兩步。第一步我們?cè)O(shè)計(jì)一個(gè)穩(wěn)定的測(cè)量矩陣（D來(lái)確保任何K-稀疏可壓縮信號(hào)的顯著特征在維度從X*減少到時(shí)不被破壞。第二步，我們開(kāi)發(fā)一個(gè)將測(cè)量值V恢復(fù)成x的重構(gòu)算法。首先，我們先關(guān)注確切的K-稀疏信號(hào)。5.1穩(wěn)定的測(cè)量矩陣首先，我們?cè)O(shè)計(jì)一個(gè)依靠矩陣0的數(shù)據(jù)收集系統(tǒng)的測(cè)量方法。我們的目標(biāo)是從可以穩(wěn)固的重構(gòu)長(zhǎng)度N的信號(hào)X或者在W中相等的稀疏向量中獲得M個(gè)測(cè)量值。很明顯，如果測(cè)量過(guò)程中破壞了x中的信息，將不能重構(gòu)為原信號(hào)。不幸的是，通常情況下會(huì)是這樣：在測(cè)量過(guò)程中矩陣W和（D是線性有限的，在（2）中通過(guò)y求解s是一個(gè)線性代數(shù)問(wèn)題，由于M<N,方程的個(gè)數(shù)少于未知量，用通常的方法不適合解這個(gè)問(wèn)題。然而s的K-稀疏帶給我們解決方法。在這種情況下測(cè)量向量是0的列K的線性組合,Sj知（見(jiàn)圖1（b））°如果我們知道先驗(yàn)條目s中有K個(gè)非零值，那么我們可以組成一個(gè)M*K的線性方程來(lái)求解這些非零值，其中已知方程M等于或大于未知數(shù)K。一個(gè)確保矩陣M*K狀態(tài)良好的充分必要條件是對(duì)于任意具有相同K個(gè)非零值的向量V滿足llQv||2

llv||2<1+0(3)總之，矩陣。必須保證K-llQv||2

llv||2<1+0(3)當(dāng)然，在實(shí)際中我們并不需要知道s中K-稀疏的位置。有趣的是，K-稀疏和可壓縮信號(hào)s有穩(wěn)定的逆的充分條件是。符合（3）o這就是為什么稱之為有限等距約束。一種可選的保持穩(wěn)定的方法是確保測(cè)量矩陣（D與W是不相關(guān)的，向量｛甲?。荒芟∈璞硎鞠蛄浚姡?反之亦然。典型的例子是：傅里葉的不確定性立即屈服于這種不相關(guān)性。所以，給定一個(gè)稀疏基W，我們?cè)鯓訕?gòu)建一個(gè)測(cè)量矩陣①使0=（D^滿足有限等距約束。不幸的是，僅僅驗(yàn)證0滿足有限等距約束是一個(gè)復(fù)雜的組合問(wèn)題；我們必須驗(yàn)證長(zhǎng)度為N的向量v中K個(gè)非零值所有的（修）種可能性。A在壓縮感知中，我們通過(guò)選擇隨機(jī)矩陣①來(lái)回避這個(gè)問(wèn)題。例如，我們從均值為零方差為1/N的高斯矩陣（白噪聲）隨機(jī)抽取相互獨(dú)立均勻分布的元素％,/然后測(cè)量值y僅僅是M中x中元素的線性隨機(jī)組合。一個(gè)高斯矩陣（D有兩有趣有用的特點(diǎn)。第一，（D有很高的概率與W=l不相關(guān)，因?yàn)樗浞值乩肗個(gè)脈沖表示①的每一行。更嚴(yán)格地說(shuō)，運(yùn)用濃縮的測(cè)量參數(shù)，如果M^cKlog(N/K)旦c是一個(gè)小常量則一個(gè)M*N的相互獨(dú)立均勻分布的高斯矩陣0=(DI=(D滿足有限等距約束。因此我們可以認(rèn)為有很高的概率從一個(gè)滿足M>cKlog(N/K)?N的隨機(jī)高斯測(cè)量矩陣回復(fù)出一個(gè)長(zhǎng)度為N的K-稀疏可壓縮信號(hào)。第二，由于高斯分布矩陣W的互相獨(dú)立均勻分布的特性，不論如何選取稀疏矩陣W，矩陣O=(DW也是高斯分布的。因此隨機(jī)選取的高斯測(cè)量矩陣(D對(duì)于每個(gè)可能的W都有很高的概率嚴(yán)格意義上普遍讓O=(DW滿足有限等距約束。在其他情況下，隨機(jī)值±1的德拉馬赫矩陣也滿足有限等距約束和普適性。5.2信號(hào)重構(gòu)算法有限等距約束性質(zhì)提供了理論上通過(guò)y中M個(gè)測(cè)量值完整地描述一個(gè)K-稀疏可壓縮信號(hào)，但并沒(méi)有告訴我們?cè)趺椿謴?fù)它。信號(hào)重構(gòu)的步驟必須采用測(cè)量值y,隨機(jī)測(cè)量矩陣0(或生產(chǎn)它的隨機(jī)種子)，以及稀疏矩陣W來(lái)再生出長(zhǎng)度為N的信號(hào)x,或者其等價(jià)的稀疏系數(shù)向量s。我們將再次關(guān)注K-稀疏信號(hào)。由于(2)中M<N,因此有非常多的s，滿足Os^y；他們都依賴于R”中(N-M)維超平面H:=N(0)+s相應(yīng)的是0對(duì)于零空間N(€>)化為稀疏解so這是因?yàn)槿绻?s=y那么對(duì)于任何零空間的向量v都有。(s+!?)=y°一次，我們的目標(biāo)是在零空間里找到信號(hào)的稀疏系數(shù)向量s。定義向量s的范數(shù)；為(||s||p)P=￡；L|Sj|P。當(dāng)p=0時(shí)，我們計(jì)算s中非零值的數(shù)量得到范數(shù)Z。。因此K-稀疏向量具有I。范數(shù)K。最小范數(shù)侃重構(gòu)：經(jīng)典的解決這種類型的反問(wèn)題的方法是最小二乘法；既在被轉(zhuǎn)化為零空間H中選擇具有最小范數(shù)侃的向量：s'argmin|Is'lb例如0sz=y(4)甚至有一個(gè)更方便的閉型解s*=0r(€>?r)Ty。但不幸的是當(dāng)向量我們尋找的向量s是K-稀疏的，最小的侃總是不能被發(fā)現(xiàn)。相反我們找到的是非稀疏的廠(詳見(jiàn)6.1節(jié))最小范數(shù)1。重構(gòu)：由于范數(shù)侃在(4)中并不能反映信號(hào)的稀疏性，一種合理的選擇是尋找被轉(zhuǎn)化為零空間H的最稀疏向量：s"=argmin||s'||o例如0sr=y(5)由上式知只要有M=K+1個(gè)相互獨(dú)立均勻分布的高斯測(cè)量值，就有很高的概率最優(yōu)化地恢復(fù)出一個(gè)K-稀疏信號(hào)。但不幸的是解(5)不僅在數(shù)學(xué)上不穩(wěn)定而旦還是一個(gè)NP完全問(wèn)題，它要求我們?cè)敱M地列舉出s中非零值位置的所有(^)種可能的組合。最小范數(shù)九重構(gòu)：壓縮感知的驚奇之處在于我們可以從M^cKlog(N/K)個(gè)相互獨(dú)立均勻分布的高斯測(cè)量值中正確地重構(gòu)出K-稀疏向量并且通過(guò)九高概率的最優(yōu)化近似壓縮向量。s'argmin||s'||i例如Os'=y(6)這是一個(gè)被成為基追蹤的減少到線性問(wèn)題的凸優(yōu)化問(wèn)題，其計(jì)算復(fù)雜度大概是0(N3)?？偠灾?，一個(gè)壓縮感知數(shù)據(jù)收集系統(tǒng)由基于(D隨機(jī)測(cè)量值組成，通過(guò)線性問(wèn)題重構(gòu)得到信號(hào)X。6討論6.1幾何解釋壓縮感知問(wèn)題在空間睥中的幾何結(jié)構(gòu)可?以幫助我們形象的理解為什么九的重構(gòu)能成功而侃卻會(huì)失敗。首先，要注意在空間RV中的所有K-稀疏向量s是由在坐標(biāo)軸上對(duì)其的所有K維超空間組成的高度非線性空間(見(jiàn)圖2(a))°因此在空間A”中稀疏向量十分靠近坐標(biāo)軸。為形象得理解為什么Z2的重構(gòu)會(huì)失敗，注意被轉(zhuǎn)化為零空間H=N(0)+s是(N-M)維,并且由于矩陣。的隨機(jī)性H被定向成了一個(gè)隨機(jī)角度。觀察圖2(b)，但要注意在實(shí)際中N,M,K>>3,你需要將直覺(jué)外推到高維度中。(4)中侃的極小變化量廠在H上是一個(gè)非常靠近原點(diǎn)的點(diǎn)。我們可以找到這個(gè)點(diǎn)通過(guò)在超球面(侃球)接觸H前放大它。由于H方向的隨機(jī)性，最接近的點(diǎn)廠有很高概率遠(yuǎn)離坐標(biāo)軸，因此它可能既不稀疏也不接近正確答案s。與球形成鮮明對(duì)比的是，。球在圖2(c)是沿著坐標(biāo)軸對(duì)齊的點(diǎn)形成的尖銳形狀(并且會(huì)隨著維度N的增長(zhǎng)變得更加尖銳)。因此當(dāng)我們放大九球時(shí)，它會(huì)第一時(shí)間在靠近坐標(biāo)軸的點(diǎn)上觸碰到轉(zhuǎn)化為零空間的H,這個(gè)點(diǎn)恰恰就是稀疏向量S的位置。6.2模擬信號(hào)當(dāng)我們集中于離散時(shí)間信號(hào)X上時(shí)，壓縮感知也能應(yīng)用于模擬信號(hào)X(t),其稀疏性可用從一些連續(xù)基或字典{乳(t)}?Li中的N種可能元素表示。當(dāng)每個(gè)弭(t)擁有大大帶寬(或一個(gè)高的尼奎斯特頻率)時(shí)信號(hào)x(t)只有K自由度，并且我們可以用以上理論以一個(gè)低于尼奎斯特定律的值去測(cè)量這個(gè)信號(hào)。一給模擬壓縮感知系統(tǒng)的實(shí)例被稱為“模擬-信息”的采集器在【7】中給出。7實(shí)例想一想不先收集N個(gè)像素值而收集M隨機(jī)線性測(cè)量值的單像素壓縮數(shù)字相機(jī)。期待圖形的入射光并未集中在CCD或是CMOS采樣組上，而是反射到由N個(gè)小鏡子組成的數(shù)字微鏡裝置上(數(shù)字微鏡裝置多用于電腦放映機(jī)和投影儀上)。反射光稍后由第二個(gè)透鏡收集并聚集在一個(gè)單光電二極管上(單像素)。每個(gè)鏡子可■以獨(dú)立的調(diào)整是朝向光電二極管或者遠(yuǎn)離光電二極管。每個(gè)測(cè)量值為用如下方法獲得：隨機(jī)數(shù)字發(fā)生器以偽隨機(jī)序列0/1設(shè)置鏡子朝向來(lái)創(chuàng)造測(cè)量向量<p廣光電二極管的電壓等于力，就是甲/和期待圖形x的內(nèi)積。這個(gè)過(guò)程充分M次來(lái)獲得所有y中的值。圖3(b)和(c)以次圖像和目標(biāo)物體闡明單像素照相機(jī)樣機(jī)使用比重構(gòu)信號(hào)所需少％60的隨機(jī)測(cè)量值獲