宋儒瑛,鄭珂,關(guān)晉瑞

(太原師范學(xué)院數(shù)學(xué)系,山西 晉中 030619)

1 引言

壓縮感知是一種尋找欠定線性系統(tǒng)的稀疏解的技術(shù).近些年來(lái),該領(lǐng)域進(jìn)行了大量的研究.Donoho和Cand`es及Tao[1-2]的開(kāi)創(chuàng)性工作成功地解決了這些問(wèn)題,即通過(guò)研究m×N測(cè)量矩陣A以及恢復(fù)算法,找到壓縮感知模型y=Ax的最稀疏解.選擇合適矩陣是利用了概率論的方法,得出結(jié)論:大多數(shù)隨機(jī)選擇的矩陣可以有效地重建稀疏向量.重建問(wèn)題在于解決可計(jì)算的凸優(yōu)化問(wèn)題

來(lái)取代NP-困難非凸優(yōu)化問(wèn)題

時(shí)具有第k階限制等距性質(zhì).其中滿足不等式(1)的最小常數(shù)用δk表示,并稱其為矩陣A的最小限制等距常數(shù),詳見(jiàn)文獻(xiàn)[4].對(duì)于滿足集中不等式的隨機(jī)矩陣,由限制等距性質(zhì)(1)以及測(cè)量值滿足m≥csln(eN/s)的條件下,推導(dǎo)出?1最小化稀疏恢復(fù)是可能的,文獻(xiàn)[5]有相關(guān)證明.當(dāng)隨機(jī)矩陣是亞高斯隨機(jī)矩陣時(shí),詳見(jiàn)文獻(xiàn)[6].

對(duì)于亞高斯隨機(jī)矩陣,經(jīng)典的限制等距性質(zhì)可以做出一些相應(yīng)的修正.取限制等距性質(zhì)中內(nèi)范數(shù)為?2范數(shù),外范數(shù)為文獻(xiàn)[7]中涉及到的外部范數(shù),即

其中

如果每個(gè)νi,j的第一個(gè)絕對(duì)矩是有限的,那么很容易驗(yàn)證出現(xiàn)在文獻(xiàn)[8-10]中的這種表達(dá)式定義了RN上的范數(shù).該外部范數(shù)依賴于概率分布構(gòu)成了研究的新穎性.由此得到的修正限制等距性質(zhì)如下:

一個(gè)項(xiàng)ai,j是根據(jù)中心概率測(cè)度νi,j分布的隨機(jī)矩陣A∈Rm×N,它的最小限制等距常數(shù)δ∈(0,1),使得

成立,其中k稀疏向量x∈RN.

本文在第一部分中介紹了相關(guān)的預(yù)備知識(shí),第二部分建立了關(guān)于范數(shù)(2)的集中不等式,在第三部分中證明了修正了的限制等距常數(shù)是足夠小的,第四部分中證明了測(cè)量矩陣滿足修正限制等距性質(zhì)(3),相對(duì)于歐幾里得范數(shù)而言,可以通過(guò)?1-最小化進(jìn)行稀疏恢復(fù).第五部分結(jié)合前面的結(jié)果得出主要定理.第六部分運(yùn)用實(shí)驗(yàn)驗(yàn)證了定理結(jié)果的正確性.為了解釋的清楚,可以選擇只處理從完美測(cè)量中恢復(fù)精確稀疏向量的問(wèn)題.

2 預(yù)備知識(shí)

首先從亞高斯隨機(jī)變量的定義以及它的等價(jià)性條件開(kāi)始.

3 亞高斯尾衰減

4 修正限制等距性質(zhì)

5 稀疏恢復(fù)

6 主要定理

7 實(shí)例驗(yàn)證

圖1 不同稀疏度的信號(hào)重建

根據(jù)圖1可知,隨著測(cè)量值的不斷增大,信號(hào)成功恢復(fù)的概率也不斷增大,那么根據(jù)常數(shù)C2的大小可知,本文所證明的定理中測(cè)量值的條件足以使得信號(hào)進(jìn)行稀疏恢復(fù),定理得以驗(yàn)證.

8 結(jié)束語(yǔ)

本文通過(guò)應(yīng)用依賴于概率分布的范數(shù),證明了一個(gè)具有獨(dú)立亞高斯隨機(jī)系數(shù)的m×N欠定線性方程組滿足限制等距性質(zhì)時(shí),在最優(yōu)條件m≥csln(eN/s)下,系統(tǒng)的s稀疏解可以通過(guò)?1最小化得到.在Simon Foucart,Ming-Jun Lai等人對(duì)于預(yù)高斯隨機(jī)矩陣稀疏恢復(fù)的基礎(chǔ)上,對(duì)亞高斯隨機(jī)矩陣稀疏恢復(fù)進(jìn)行了證明,并且將文獻(xiàn)[11]限制等距性質(zhì)中?2范數(shù)用依賴于概率分布的范數(shù)取代,得出了新的結(jié)果.