王 超,梁大鵬

（北京科技大學(xué)信息工程學(xué)院,北京 100083）

壓縮感知測(cè)量方法的機(jī)密性

王 超,梁大鵬

（北京科技大學(xué)信息工程學(xué)院,北京 100083）

分析了壓縮感知（CS）的安全性問題,討論了在攻擊者不知道測(cè)量矩陣情況下是否可以有效對(duì)信號(hào)進(jìn)行重構(gòu)的問題,論證了壓縮感知可以達(dá)到保密性但達(dá)不到完善的保密性。最后聯(lián)合信道容量和速率失真函數(shù),討論了壓縮感知恢復(fù)信號(hào)所需測(cè)量數(shù)據(jù)量的下限,并分析了測(cè)量噪聲對(duì)信號(hào)重構(gòu)性能的影響。

壓縮感知;測(cè)量矩陣;機(jī)密性;信道容量;率失真函數(shù)

1 引 言

近年來(lái)在信號(hào)處理領(lǐng)域中,壓縮感知（Compressed Sensing,CS）作為一種新的理論備受關(guān)注。壓縮感知理論框架下,處理高度可壓縮的信號(hào)時(shí),可以摒棄掉傳統(tǒng)的采樣方式而只采樣對(duì)整個(gè)數(shù)據(jù)流有用的樣本,然后通過(guò)解決線性規(guī)劃問題來(lái)重構(gòu)原始信號(hào)。壓縮感知的優(yōu)點(diǎn)在于信號(hào)的投影測(cè)量數(shù)據(jù)量遠(yuǎn)遠(yuǎn)小于傳統(tǒng)采樣方法所獲的數(shù)據(jù)量,突破了香農(nóng)采樣定理的瓶頸,使得高分辨率信號(hào)采集成為可能。

文獻(xiàn)[1-6]研究表明,利用少數(shù)稀疏線性信號(hào)的測(cè)量值來(lái)恢復(fù)稀疏信號(hào)是可行的。但是否可以利用壓縮感知中的測(cè)量矩陣在對(duì)信號(hào)進(jìn)行壓縮采樣的同時(shí)完成對(duì)信號(hào)的加密呢?以及從信息論角度上講,這種加密是否安全?如果安全,在壓縮采樣的過(guò)程中壓縮與加密同時(shí)進(jìn)行,可以避免采用額外的加密方式帶來(lái)的開銷。這對(duì)一些特殊的應(yīng)用場(chǎng)合是很有用的,例如在傳感器網(wǎng)絡(luò)中低功耗設(shè)備需要捕獲和發(fā)送低速數(shù)據(jù),并且傳感器網(wǎng)絡(luò)有可能布置在無(wú)人或是敵方區(qū)域,信息安全和傳輸?shù)目煽啃院苤匾?。在有噪聲的情況下,如何利用信息論框架計(jì)算出恢復(fù)數(shù)據(jù)所需的測(cè)量值的下限。本文主要討論壓縮傳感的安全性問題,并分析了在噪聲條件下恢復(fù)數(shù)據(jù)所需的測(cè)量數(shù)據(jù)的下限。

2 背景知識(shí)

壓縮感知理論與傳統(tǒng)奈奎斯特采樣定理不同,只要信號(hào)是可壓縮的或在某個(gè)變換域是稀疏的,那么就可以用一個(gè)與變換基不相關(guān)的觀測(cè)矩陣將變換所得高維信號(hào)投影到一個(gè)低維空間上,然后通過(guò)求解一個(gè)優(yōu)化問題就可以從這些少量的投影中高概率地重構(gòu)出原信號(hào),可以證明這樣的投影包含了重構(gòu)信號(hào)所需的足夠信息。在該理論框架下,采樣速率不決定于信號(hào)的帶寬,而決定于信息在信號(hào)中的結(jié)構(gòu)和內(nèi)容。

最簡(jiǎn)單的模型是一個(gè)n維信號(hào)X僅含有少量的k個(gè)非0值,這樣的信號(hào)稱為k稀疏。一個(gè)與變換基 Χ不相關(guān)的觀測(cè)基Υ:m×n（m<

Candes和Tao指出[7]使用最小1范數(shù)通過(guò)解決線性方程可以重構(gòu)信號(hào):

式中,Υ滿足約束等距性（RIP）。

目前為止,出現(xiàn)的重構(gòu)算法都可歸入以下三大類[8]:

（1）貪婪追蹤算法:這類方法是通過(guò)每次迭代時(shí)選擇一個(gè)局部最優(yōu)解來(lái)逐步逼近原始信號(hào),這類算法包括MP算法、OMP算法、正則化OMP（ROMP）算法、CoSaMP算法、SP 算法 ;

（2）凸松弛法:這類方法通過(guò)將非凸問題轉(zhuǎn)化為凸問題求解找到信號(hào)的逼近,如BP算法、內(nèi)點(diǎn)法和迭代閾值法;

（3）組合算法:這類方法要求信號(hào)的采樣支持通過(guò)分組測(cè)試快速重建,如傅里葉采樣、鏈?zhǔn)阶粉櫟取?/p>

3 無(wú)噪聲情況下CS機(jī)密性

為了討論壓縮感知測(cè)量的機(jī)密性能,引入以下模型。對(duì)于一個(gè)k稀疏的信號(hào)x∈Rn,密鑰i∈{1,2,3,…,S}對(duì)應(yīng)于m×n矩陣 Υi。在這個(gè)模型中,A lice想要向Bob發(fā)送一則加密的信息。Alice選擇i使用 Υi和y=Υix來(lái)加密x。只有密文y傳送給Bob,Bob方知道加密用的密鑰。給定 Υi、y以及x的稀疏度和密鑰知識(shí),Bob可以重構(gòu)x。Eve竊聽到y(tǒng),但他不知道加密用的Key,也就是i。接下來(lái)我們討論在Eve只知道y、信號(hào)x的稀疏度、密鑰組和相應(yīng)的 Υ矩陣來(lái)重構(gòu)x的難度。

“一次一密”系統(tǒng)在理論上被認(rèn)為是不可破譯的,而壓縮傳感系統(tǒng)可以作為一次一密系統(tǒng),實(shí)際的加密系統(tǒng)是通過(guò)雙方共享重復(fù)使用的有限長(zhǎng)度的主密鑰,利用算法復(fù)雜性產(chǎn)生偽隨機(jī)數(shù)進(jìn)行加密。

在實(shí)際中,通過(guò)共享一個(gè)足夠大的隨機(jī)種子產(chǎn)生器,將會(huì)使密鑰數(shù)量S達(dá)到足夠大,而編碼加密所用密鑰隨機(jī)從密鑰數(shù)S中選取,這可以當(dāng)作一次一密,而且由于對(duì)所有密鑰逐一估算很困難,可以認(rèn)為此系統(tǒng)具有安全機(jī)密性。文獻(xiàn)[9]中指出由于y=Υx,即y和x存在相關(guān)性,因此有則壓縮感知達(dá)不到完善保密性。

隨機(jī)產(chǎn)生的m×n高斯隨機(jī)矩陣Υ和Υ′,對(duì)于k稀疏向量x滿足y=Υx,當(dāng)m>k+1時(shí),基于 Υ和 Υ′所有滿足y=Υx′的x′是m稀疏。

首先對(duì)于 Υ和 Υ′的m列組有唯一的恢復(fù)結(jié)果,Υ′的m列標(biāo)記為 Υm,Υm與 Υ′相互獨(dú)立,則Υ′Ψm的秩為m,并且此矩陣的逆矩陣可以唯一決定x的m個(gè)值,使y=Υ′x。

最后說(shuō)明當(dāng)tk+1時(shí),使用聚合矩陣[ΥΨk,ΥΨt];又當(dāng)k+t>m時(shí),聚合矩陣在 Υ和 Υ′秩為m,交集部分為k+t-m。由于tm+1時(shí),使用錯(cuò)誤密鑰進(jìn)行信號(hào)重構(gòu)得到的將是m稀疏信號(hào)而不是k稀疏信號(hào)。

Eve對(duì)k稀疏信號(hào)使用錯(cuò)誤的密鑰進(jìn)行重構(gòu)得到的信號(hào)將是m稀疏的,因此利用1范數(shù)時(shí)可以認(rèn)為該壓縮感知測(cè)量具有保密性。

4 信號(hào)重構(gòu)性能限制

率失真函數(shù)理論指出為了達(dá)到在目標(biāo)數(shù)據(jù)率的條件下使傳輸信號(hào)的失真最小,在編碼比特率和信號(hào)失真之間必須選擇一個(gè)恰當(dāng)?shù)恼壑?這是香農(nóng)信息論中的率失真理論問題[10]。率失真理論討論的主要問題是:在允許一定程度失真的條件下,能夠把信息壓縮到什么程度。若定義最大允許失真度為D,則其對(duì)應(yīng)的編碼比特率的下限R（D）是D的單調(diào)遞減函數(shù),稱為率失真函數(shù)。率失真函數(shù)的定義表明:一個(gè)具有率失真函數(shù)R（D）的信源,倘若R

對(duì)于壓縮感知理論,假設(shè)X是時(shí)間離散幅度連續(xù)的信源,測(cè)量值Y可以看作高斯信道的輸出,無(wú)噪情況下的Y0作為信道輸入。由于信道容量有限則每個(gè)測(cè)量?jī)H獲得有限的信息量,也說(shuō)明了完美信號(hào)重構(gòu)是不可能的。由率失真函數(shù)理論可知,使用CS測(cè)量重構(gòu)方案重構(gòu)信號(hào)X,并要求達(dá)到一定的保真度,則最小測(cè)量速率需要達(dá)到一定大小。

4.1 求信道容量C

CS測(cè)量值所獲得信息是由測(cè)量信道的容量決定的,要尋找特定失真率下測(cè)量速率δ（δ=m/n,n為信號(hào)長(zhǎng)度）的下限,就要先求得信道容量。

當(dāng)Y0是對(duì)角矩陣且對(duì)角元素都等于SNR時(shí)上式取等號(hào),所以最好的CS測(cè)量系統(tǒng)是測(cè)量向量相互獨(dú)立并且方差相同。通過(guò)信道容量C可以從m個(gè)有噪測(cè)量值Y中獲取最大信息。

4.2 使用信源信道分離定理來(lái)估計(jì)誤差界

根據(jù)文獻(xiàn)[12],對(duì)于時(shí)間離散幅度連續(xù)平穩(wěn)遍歷信號(hào),信源X經(jīng)m個(gè)信道傳播,當(dāng)且僅當(dāng)從信道獲取的信息量mC大于量化信源信息量nR（D）時(shí)X的失真度為D。

4.3 計(jì)算結(jié)果

通過(guò)上面的分析可知,達(dá)到D誤差率的CS測(cè)量速率的下限為

式中,R（·）是速率失真函數(shù)。對(duì)于高斯信源速率失真函數(shù)為

利用信息論理論討論在噪聲環(huán)境下CS恢復(fù)信號(hào)所需測(cè)量數(shù)量的下限。主要思想是將噪聲情況下信號(hào)獲取過(guò)程當(dāng)作通信信道模型處理,信道容量表示出測(cè)量值所包含的信息量,使用這個(gè)結(jié)果和信源率失真函數(shù)可以得到所需的測(cè)量速率。

5 總 結(jié)

本文在壓縮感知理論基礎(chǔ)上,討論了無(wú)噪情況下采集壓縮感知數(shù)據(jù)的安全性問題,指出其具有保密性但達(dá)不到完善保密性。利用信息論知識(shí)給出了有噪的情況下,CS恢復(fù)信號(hào)所需測(cè)量數(shù)量的下限。有噪情況下CS的安全性能問題將是進(jìn)一步研究的內(nèi)容。

[1] 石光明,劉丹華,高大化,等.壓縮感知理論及其研究進(jìn)展[J].電子學(xué)報(bào),2009,37（5）:1071-1081.

SHI Guang-ming,LIU Dan-hua,GAO Da-hua,et al.Advances in theory and applicationof compressed sensing[J].Acta Electronica Sinica,2009,37（5）:1071-1081.（in Chinese）

[2] Candes E,Romberg J,Terence Tao.Robust uncertainty principles:Exact signal reconstruction from highly incomplete frequency information[J].IEEE Transactions on Information Theory,2006,52（2）:489-509.

[3] Candes E,Tao T.Near optimal signal recovery from random projections:Universal encoding strategies?[J].IEEE Transactions on Information Theory,2006,52（12）:5406-5425.

[4] Donoho D.Compressed Sensing[J].IEEE Transactions on Information Theory,2006,52（4）:1289-1306.

[5] Baraniuk RG.Compressive sensing[J].IEEE Signal Processing Magazine,2007,24（4）:118-121.

[6] Candes E,Wakin M.An introduction to compressive sampling[J].IEEESignalProcessing Magazine,2008,25（2）:21-30.

[7] Candes E J,Tao T.Decoding by linear p rogramming[J].IEEE Transactions on Information Theory,2005,51（12）:4203-4215.

[8] Needell D,Tropp J A.CoSaMP:Iterative signal recovery from incomplete and inaccurate samp les[J].Comp Harmonic Anal,2009,26（3）:301-321.

[9] Rachlin Y,Baron D.The secrecy of compressed sensing measurements[C]//Proceedings of Allerton Conference on Communication Control and Computing.Urbana-Champaign,IL:IEEE,2008:813-817.

[10] 傅祖蕓.信息論——基礎(chǔ)理論與應(yīng)用[M].北京:電子工業(yè)出版社,2001.

FU Zu-yun.Information theory——basic theory and application[M].Beijing:Publishing House of Electronics Industry,2001.（in Chinese）

[11] Cover T M,Thomas J A.Elements of Information Theory[M].New York:Wiley Press,1991.

[12] Berger T.Rate Distortion Theory:A Mathematical Basis for Data Compression[M].Englewood,NJ:Prentice-Hall,1971.

Secrecy of Compressed Sensing Measurements

WANG Chao,LIANGDa-peng
（School of Information Engineering,University of Science and Technology Beijing,Beijing 100083,China）

The security of compressed sensing（CS）is analysed.Wheather the attacker can effectively recover signal when it does not know measurement matrix is discussed.The CS can achieve the confidentiality but is fail to achieve the perfect secrecy.The lower bound of measure number for the signal recovery of CS is discussed by combining channel capacity with rate-distortion function.The influence of measurement noise on the signal reconstruction performance limitation is also analysed.

compressed sensing（CS）;measurement matrix;privacy;channel capacity;rate-distortion function

The National High-Tech Research and Development Program（863 Program）of China（No.2009AA01z209）;The National Natural Science Foundation of China（No.60902042）;The Natural Science Foundation of Beijing（No.4082020）

TP952

A

10.3969/j.issn.1001-893x.2010.11.006

1001-893X（2010）11-0026-04

2010-07-15;

2010-09-08

國(guó)家高技術(shù)研究發(fā)展計(jì)劃（863計(jì)劃）項(xiàng)目（2009AA01z209）;國(guó)家自然科學(xué)基金資助項(xiàng)目（60902042）;北京市自然科學(xué)基金資助項(xiàng)目（4082020）

王 超（1978-）,男,河北人,博士,北京科技大學(xué)信息工程學(xué)院講師,主要研究方向?yàn)闊o(wú)線通信、信號(hào)處理;

WANG Chao was born in Hebei Province,in 1978.He is now a lecturer with the Ph.D.degree.His research interests include the wireless communication networks and signal processing.

Email:wanch3307@sohu.com

梁大鵬,碩士研究生,主要研究方向?yàn)闊o(wú)線通信網(wǎng)絡(luò)和認(rèn)知無(wú)線電。

LIANG Da-peng is now a graduate student.His research interests include the wireless communication networks and cognitive radio.