亞高斯隨機(jī)矩陣的稀疏恢復(fù)

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

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

1 引言

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

來取代NP-困難非凸優(yōu)化問題

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

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

其中

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

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

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

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

2 預(yù)備知識

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

3 亞高斯尾衰減

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

5 稀疏恢復(fù)

6 主要定理

7 實例驗證

圖1 不同稀疏度的信號重建

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

8 結(jié)束語

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