压缩感知测量方法的机密性
2010-01-26梁大鹏
王 超,梁大鹏
（北京科技大学信息工程学院,北京 100083）
压缩感知测量方法的机密性
王 超,梁大鹏
（北京科技大学信息工程学院,北京 100083）
分析了压缩感知（CS）的安全性问题,讨论了在攻击者不知道测量矩阵情况下是否可以有效对信号进行重构的问题,论证了压缩感知可以达到保密性但达不到完善的保密性。最后联合信道容量和速率失真函数,讨论了压缩感知恢复信号所需测量数据量的下限,并分析了测量噪声对信号重构性能的影响。
压缩感知;测量矩阵;机密性;信道容量;率失真函数
1 引 言
近年来在信号处理领域中,压缩感知（Compressed Sensing,CS）作为一种新的理论备受关注。压缩感知理论框架下,处理高度可压缩的信号时,可以摒弃掉传统的采样方式而只采样对整个数据流有用的样本,然后通过解决线性规划问题来重构原始信号。压缩感知的优点在于信号的投影测量数据量远远小于传统采样方法所获的数据量,突破了香农采样定理的瓶颈,使得高分辨率信号采集成为可能。
文献[1-6]研究表明,利用少数稀疏线性信号的测量值来恢复稀疏信号是可行的。但是否可以利用压缩感知中的测量矩阵在对信号进行压缩采样的同时完成对信号的加密呢?以及从信息论角度上讲,这种加密是否安全?如果安全,在压缩采样的过程中压缩与加密同时进行,可以避免采用额外的加密方式带来的开销。这对一些特殊的应用场合是很有用的,例如在传感器网络中低功耗设备需要捕获和发送低速数据,并且传感器网络有可能布置在无人或是敌方区域,信息安全和传输的可靠性很重要。在有噪声的情况下,如何利用信息论框架计算出恢复数据所需的测量值的下限。本文主要讨论压缩传感的安全性问题,并分析了在噪声条件下恢复数据所需的测量数据的下限。
2 背景知识
压缩感知理论与传统奈奎斯特采样定理不同,只要信号是可压缩的或在某个变换域是稀疏的,那么就可以用一个与变换基不相关的观测矩阵将变换所得高维信号投影到一个低维空间上,然后通过求解一个优化问题就可以从这些少量的投影中高概率地重构出原信号,可以证明这样的投影包含了重构信号所需的足够信息。在该理论框架下,采样速率不决定于信号的带宽,而决定于信息在信号中的结构和内容。
最简单的模型是一个n维信号X仅含有少量的k个非0值,这样的信号称为k稀疏。一个与变换基 Χ不相关的观测基Υ:m×n（m< Candes和Tao指出[7]使用最小1范数通过解决线性方程可以重构信号: 式中,Υ满足约束等距性（RIP）。 目前为止,出现的重构算法都可归入以下三大类[8]: （1）贪婪追踪算法:这类方法是通过每次迭代时选择一个局部最优解来逐步逼近原始信号,这类算法包括MP算法、OMP算法、正则化OMP（ROMP）算法、CoSaMP算法、SP 算法 ; （2）凸松弛法:这类方法通过将非凸问题转化为凸问题求解找到信号的逼近,如BP算法、内点法和迭代阈值法; （3）组合算法:这类方法要求信号的采样支持通过分组测试快速重建,如傅里叶采样、链式追踪等。 为了讨论压缩感知测量的机密性能,引入以下模型。对于一个k稀疏的信号x∈Rn,密钥i∈{1,2,3,…,S}对应于m×n矩阵 Υi。在这个模型中,A lice想要向Bob发送一则加密的信息。Alice选择i使用 Υi和y=Υix来加密x。只有密文y传送给Bob,Bob方知道加密用的密钥。给定 Υi、y以及x的稀疏度和密钥知识,Bob可以重构x。Eve窃听到y,但他不知道加密用的Key,也就是i。接下来我们讨论在Eve只知道y、信号x的稀疏度、密钥组和相应的 Υ矩阵来重构x的难度。 “一次一密”系统在理论上被认为是不可破译的,而压缩传感系统可以作为一次一密系统,实际的加密系统是通过双方共享重复使用的有限长度的主密钥,利用算法复杂性产生伪随机数进行加密。 在实际中,通过共享一个足够大的随机种子产生器,将会使密钥数量S达到足够大,而编码加密所用密钥随机从密钥数S中选取,这可以当作一次一密,而且由于对所有密钥逐一估算很困难,可以认为此系统具有安全机密性。文献[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。 最后说明当t Eve对k稀疏信号使用错误的密钥进行重构得到的信号将是m稀疏的,因此利用1范数时可以认为该压缩感知测量具有保密性。 率失真函数理论指出为了达到在目标数据率的条件下使传输信号的失真最小,在编码比特率和信号失真之间必须选择一个恰当的折衷,这是香农信息论中的率失真理论问题[10]。率失真理论讨论的主要问题是:在允许一定程度失真的条件下,能够把信息压缩到什么程度。若定义最大允许失真度为D,则其对应的编码比特率的下限R（D）是D的单调递减函数,称为率失真函数。率失真函数的定义表明:一个具有率失真函数R（D）的信源,倘若R 对于压缩感知理论,假设X是时间离散幅度连续的信源,测量值Y可以看作高斯信道的输出,无噪情况下的Y0作为信道输入。由于信道容量有限则每个测量仅获得有限的信息量,也说明了完美信号重构是不可能的。由率失真函数理论可知,使用CS测量重构方案重构信号X,并要求达到一定的保真度,则最小测量速率需要达到一定大小。 CS测量值所获得信息是由测量信道的容量决定的,要寻找特定失真率下测量速率δ（δ=m/n,n为信号长度）的下限,就要先求得信道容量。 当Y0是对角矩阵且对角元素都等于SNR时上式取等号,所以最好的CS测量系统是测量向量相互独立并且方差相同。通过信道容量C可以从m个有噪测量值Y中获取最大信息。 根据文献[12],对于时间离散幅度连续平稳遍历信号,信源X经m个信道传播,当且仅当从信道获取的信息量mC大于量化信源信息量nR（D）时X的失真度为D。 通过上面的分析可知,达到D误差率的CS测量速率的下限为 式中,R（·）是速率失真函数。对于高斯信源速率失真函数为 利用信息论理论讨论在噪声环境下CS恢复信号所需测量数量的下限。主要思想是将噪声情况下信号获取过程当作通信信道模型处理,信道容量表示出测量值所包含的信息量,使用这个结果和信源率失真函数可以得到所需的测量速率。 本文在压缩感知理论基础上,讨论了无噪情况下采集压缩感知数据的安全性问题,指出其具有保密性但达不到完善保密性。利用信息论知识给出了有噪的情况下,CS恢复信号所需测量数量的下限。有噪情况下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].北京:电子工业出版社,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 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 国家高技术研究发展计划（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 梁大鹏,硕士研究生,主要研究方向为无线通信网络和认知无线电。 LIANG Da-peng is now a graduate student.His research interests include the wireless communication networks and cognitive radio.
3 无噪声情况下CS机密性
4 信号重构性能限制
4.1 求信道容量C
4.2 使用信源信道分离定理来估计误差界
4.3 计算结果
5 总 结
（School of Information Engineering,University of Science and Technology Beijing,Beijing 100083,China）
