壓縮感知測量方法的機密性

王 超,梁大鵬

（北京科技大學信息工程學院,北京 100083）

壓縮感知測量方法的機密性

王 超,梁大鵬

（北京科技大學信息工程學院,北京 100083）

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

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

1 引 言

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

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

2 背景知識

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

最簡單的模型是一個n維信號X僅含有少量的k個非0值,這樣的信號稱為k稀疏。一個與變換基 Χ不相關的觀測基Υ:m×n（m<

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

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

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

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

（2）凸松弛法:這類方法通過將非凸問題轉化為凸問題求解找到信號的逼近,如BP算法、內點法和迭代閾值法;

（3）組合算法:這類方法要求信號的采樣支持通過分組測試快速重建,如傅里葉采樣、鏈式追蹤等。

3 無噪聲情況下CS機密性

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

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

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

隨機產生的m×n高斯隨機矩陣Υ和Υ′,對于k稀疏向量x滿足y=Υx,當m>k+1時,基于 Υ和 Υ′所有滿足y=Υx′的x′是m稀疏。

首先對于 Υ和 Υ′的m列組有唯一的恢復結果,Υ′的m列標記為 Υm,Υm與 Υ′相互獨立,則Υ′Ψm的秩為m,并且此矩陣的逆矩陣可以唯一決定x的m個值,使y=Υ′x。

最后說明當tk+1時,使用聚合矩陣[ΥΨk,ΥΨt];又當k+t>m時,聚合矩陣在 Υ和 Υ′秩為m,交集部分為k+t-m。由于tm+1時,使用錯誤密鑰進行信號重構得到的將是m稀疏信號而不是k稀疏信號。

Eve對k稀疏信號使用錯誤的密鑰進行重構得到的信號將是m稀疏的,因此利用1范數(shù)時可以認為該壓縮感知測量具有保密性。

4 信號重構性能限制

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

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

4.1 求信道容量C

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

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

4.2 使用信源信道分離定理來估計誤差界

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

4.3 計算結果

通過上面的分析可知,達到D誤差率的CS測量速率的下限為

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

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

5 總 結

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

[1] 石光明,劉丹華,高大化,等.壓縮感知理論及其研究進展[J].電子學報,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] 傅祖蕓.信息論——基礎理論與應用[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

國家高技術研究發(fā)展計劃（863計劃）項目（2009AA01z209）;國家自然科學基金資助項目（60902042）;北京市自然科學基金資助項目（4082020）

王 超（1978-）,男,河北人,博士,北京科技大學信息工程學院講師,主要研究方向為無線通信、信號處理;

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

梁大鵬,碩士研究生,主要研究方向為無線通信網(wǎng)絡和認知無線電。

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