基于矩阵分解的压缩感知算法研究

138 2011年第06期，第44卷 通 信 技 术 Vol.44，No.06,2011 总第234期 Communications Technology No.234,Totally 基于矩阵分解的压缩感知算法研究 王蓟翔， 张 扬 （电子科技大学 电子工程学院，四川 成都 610000） 【摘 要】奈奎斯特采样定律是长久以来具有指导意义的经典信号处理技术，它提出信号在采样过程中，当且仅当采样率大于信号带宽的2倍时，才能精确重构信号。压缩感知理论突破了奈奎斯特采样定理对信号采样率的限制，以更低采样率采样信号，并通过适当的重构算法恢复信号。文中以压缩感知理论为基础，结合目前广泛采用的正交匹配追踪算法，基于矩阵分解思想，提出2种改进算法，在运算复杂度方面取得优化，并且满足信号处理时对重构精度的要求。 【关键词】压缩感知；正交匹配追踪算法；矩阵分解；信号重构 【中图分类号】TP312 【文献标识码】A 【文章编号】1002-0802(2011)06-0138-03 Compressed Sensing Algorithm based on Matrix Decomposition WANG Ji-xiang (School of Electronic Engineering, University of Electronic Science and Technology of China, Chengdu Sichuan 610000, China) 【Abstract】Nyquist Sampling Theorem is a classic signal processing technology. It proposes that, in order to accurately reconstruct the signal, the sampling rate must be greater than twice as wide as the signal bandwidth. Different from the traditional signal acquisition process, compressed sensing theory breaks through the limitation of signal sampling rate by Nyquist rate, samples the signal at a lower rate, and then reconstructs the signal by a proper algorithm like Orthogonal Matching Pursuit(OMP). This paper, based on matrix decomposition and in combination of OMP algorithm, proposes two modified algorithms, thus to optimize the computing complexity and satisfy the accuracy requirement of signal of reconstruction. 【Key words】compressed sensing; OMP; matrix decomposition; signal reconstruction 0 引言 Candes和Donoho提出的压缩感知(CS,Compressed Sensing)理论[1-2],证明了当信号是稀疏或者可压缩时，可以通过远远小于奈奎斯特定理规定的数据采样率采样信号，并且高概率精确重构信号。相对于奈奎斯特定理的均匀等间隔采样，采用随机采样的压缩感知理论是信号处理领域的变革，突破了通信数据中大信息量与高采样率难以兼得的瓶颈，在大数据量通信领域[3]具有重大研究意义。 本文首先简要介绍了压缩感知理论以及流行的正交匹配追踪(OMP,Orthogonal Matching Pursuit)重构算法，然后针对该算法缺陷，提出2种改进算法，最后通过实验仿真及复杂度分析加以验证。 1 压缩感知 压缩感知(CS,Compressed Sensing)主要包含稀疏性理 论[1]、编码测量以及重构算法3方面内容。稀疏性(可压缩性)是压缩感知的理论前提；编码测量是通过投影，在采样的同时完成信号压缩；重构算法则是通过求解下面这个最优化问题。快速、稳定、精确的求解稀疏基底下的1×Ns，进而获得时域原始信号1×Nx： 02||||||||minssyλ+Θ−, (1) 其中HNNMNMN×××Θ=ΦΨ，NMnthen； ③求解w：Tˆ{}IkLwθ=Θ，更新TT01LLwww⎡⎤=⎢⎥−⎢⎥⎣⎦； ④End if ； ⑤()kIIˆ,=； ⑥csI=，c为等式的解：TILLcα=； ⑦IIsyrΘ−=； ⑧1+=nn； ⑨End while。 如果大规模信号的译码过程都是基于同一字典进行，那么预先计算部分数据以减少译码整个集合的总工作量[8]是有必要的。 设Trα=Θ，0Tyα=Θ，并且TG=ΘΘ,可以得出： 00T(())()IIIIyyGyααα++=Θ−ΘΘ=−Θ=− 01,()IIIIGGα−， (3) 这意味着若提前计算好0α和G，在每次迭代后无需明确计算r的值，而仅需更新α即可。且每一步的更新只是与矩阵IG相乘，而不是采用完备字典TΘ。注意到矩阵IIG,求逆可以通过使用上文讨论的Cholesky分解方法解答。 这一方法的限制在于因为残差没有明确计算出来，基于差错的停止迭代准则不好使用。接下来，通过派生出一个2l范数误差下的高效增量公式，将这一方法延伸到基于差错容限的案例。这使得改进的OMP算法在很多有差错限 制的译码情况下更有用。 若nr与ns是残差和稀疏估计，在第n次迭代结束后，两者的关系为： 1111(),nnnnnnnnrysysssrss−−−−=−Θ=−Θ+Θ−Θ=+Θ− (4) OMP的正交化过程保证了在每次迭代时，残差与当前估计信号都是正交的。因此，能够得到对于所有的n， T()0nnrsΘ=， (5) 通过表达式(4)与式(5)，获得了以下逼近误差平方的扩展： 2111TTT211111TTT221TT11T222111TTTT2()()(())()()(())()()()()()nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnrrrrrssrrrsrssrrsrysysrrssrssrsss−−−−−−−−−−−−−−==+Θ−=+Θ=+Θ−+Θ=−Θ+Θ=−+ΘΘ++ΘΘ=−ΘΘ+⋅ 21111TTT2()(),nnnnnnsrsGssGs−−−−ΘΘ=−+ (6) 简单地说，以22nnr=ε指定了逼近误差平方，设T()nnnsGsδ=。误差的更新过程为： 11−−+−=nnnnδδεε， (7) 注意到每次迭代中nδ在计算代价方面损失很小，这在总工作量中可以忽略不记。 称这种改进算法为改进算法2，以下是完整表述。表1归纳了这个算法中将会使用到的符号。 表1 算法2中使用的符号 符号注释 I 按顺序排列的被选择原子索引值s 原始信号的稀疏表示 r 残差)(syΘ− 0αTyΘ α TrΘ β Gs L IIG,的Cholesky因子 nδTsGs nε误差二范数22r 输入：0Tyα=Θ，T0yyε=，TG=ΘΘ，目标误差容限ε； 输出：信号的稀疏表示s，使得syΘ≈； 初始化：设()=I,[]1=L,0=s,0αα=,00=δ,1=n。 循环执行步骤： ①While(基于ε的停止准则)doˆArgmax{||}kkkα=； ②If1>nthen； ③求解w：}{ˆ,kIGwL=，更新TT01LLwww⎡⎤=⎢⎥−⎢⎥⎣⎦； ④End if； ⑤()kIIˆ,=； 140 ⑥csI=，c为等式的解：0TILLcα=； ⑦IIsG=β，βαα−=0； ⑧TnIIsδβ=； ⑨11−−+−=nnnnδδεε； ⑩1+=nn； End while。 3 改进算法性能分析 3.1 算法仿真 同样是基于Cholesky分解的改进算法，改进算法2是改进算法1的演变，其优势主要表现在提前计算矩阵乘积使复杂度降低，而重构精度区别不大，为验证算法思想，产生一个1024点的信号，如图1所示。改进算法的稀疏基底为离散余弦基，测量矩阵符合高斯分布，以改进算法2对原始信号进行重构，重构结果如图2所示。 0100200300400500-0.6-0.4-0.200.20.40.60.8 图1 原始信号 0100200300400500-0.6-0.4-0.200.20.40.60.8 图2 改进算法2的重构图 由仿真结果可知，基于Cholesky矩阵分解的改进算法能够精确重构原始信号。 3.2 算法复杂度分析 现在来考察2种基于Cholesky分解的改进算法复杂度问题。首先关注提前计算G带来的复杂度增益。为便于分析，假设信号Myℜ∈，并且字典NM×ℜ∈Θ。设调用

TΘ和Θ参与残差计算的复杂度为MNT2=

Θ。 从改进算法1开始。第n次迭代包括了计算TrΘ(复杂度ΘT)，计算并且比较产生最大的绝对值(复杂度N2)，w的计算(复杂度2n)，更新信号的稀疏表示(复杂度22n)，并且更新残差，这一步包含了IIsΘ与M次减法操作的计算量，而IIsΘ的复杂度为nM2。K次迭代之后总的操作数为： 321)(22KMNKMKKTT++++=Θ， (8) 改进算法2的分析与之类似。假设G是提前计算得到的，最后来考察其复杂度。这个算法在初始化时要求调用TΘ和Θ(复杂度ΘT)，此后每次迭代只需更新α寻找最优解。在第n次迭代时，最大绝对值的计算(复杂度N2)，w的计算(复杂度2n)，更新信号的稀疏表示(复杂度22n),δ的计算(复杂度为nN2)，以及更新α(复杂度N)。K次迭代之后总的操作数为： 3223KKNNKTT+++=Θ。 (9) 与改进算法1相比，我们发现调用Θ时产生的复杂度大幅度降低。这种方式在字典调用消耗较大的问题上是一种进步。 表格2归纳了两种改进算法的复杂度概括(设改进算法2中提前计算G的复杂度为GT)。注意到： NMTG2=， (10) 为方便起见，可以考虑引入对称矩阵作为字典。 随着信号规模的增大，发现OMP改进算法2提前计算G附加的代价消耗可以忽略，其优势相对于改进算法1更加突显出来。 表2 复杂度概括(改进算法2的复杂度考虑两方面： 算法内容的计算量与提前的计算量GT) 改进算法2 改进算法3 2322()KTKMKMNKΘ++++233TKNKNKΘ+++GT 字典规模：MN× 迭代次数：K 4 结语 压缩感知理论作为当今通信及信号处理领域的研究热点，基于它的研究也得到人们广泛的关注。其中，如何完整重构信号、重构精度以及收敛速度等方面的研究更成为重中之重。本文借鉴经典OMP重构算法，提出两种基于Cholesky矩阵分解的改进算法，它们从理论意义上提升了传统OMP算法的性能，降低了运算复杂度，最后通过算法仿真及定量比较验证理论的可行性。 参考文献 [1] DONOHO D L. Compressed Sensing[J]. IEEE Transactions on Information Theory, 2006,52(04):1289-1306. [2] CANDES E. Compressed Sampling[C]// Proceedings of International Congress of Mathematicians.Madrid,Spain: European Mathematical Society Publishing House, 2006:1422-1452. [3] 肖龙帅,黄华,夏建刚,等.压缩传感方位估计[J].通信技术, 2009,42(11):182-184. [4] CANDES E,TAO T.Decoding by Linear Programming[J]. IEEE Transactions on Information Theory, 2004,51(04):4203-4215. （下转第143页）