基于主成分分析的压缩感知重构算法

李 梁，田文飚

(1.中国人民解放军91872部队，北京 102442；2.海军航空大学 信号与信息处理山东省重点实验室，山东 烟台 264001)

0 引 言

目前，采集信号通常需要先用常规方式、固定分辨率高速采样再压缩[1]，但是，现有压缩体制需要对所有采集到的数据进行处理，计算后舍弃绝大多数小系数，这样做既浪费传感器资源，还增加了对编码端计算能力的要求，因此不得不考虑如何充分挖掘这些有限采集资源的应用潜力。

实际上，人们感兴趣的信号往往具有稀疏性，压缩感知(Compressive Sensing，CS)理论“少采样、巧重构”的思想[2-6]，为从相对稀少的观测数据中重构稀疏信号提供了可能，即以少量的观测值对待重构信号进行观测，然后利用最优化算法思想对其进行重构。

压缩感知框架的实现高度依赖信号的稀疏性，而实际信号的稀疏性很可能未知甚至时变，且稀疏度很可能无法满足CS重构的要求。本文利用主成分分析[7-8](Principal Component Analysis,PCA)充分挖掘信号的稀疏性，提出主成分追踪算法，在少量观测数据的基础上重构原信号。

1 主成分分析压缩感知

1.1 主成分分析

在自然环境中，许多信号具有直观的稀疏性，如一段时间的气温、飞机巡航的速度等等。然而，目前并没有相关研究论证这些信号究竟在哪些变换域上稀疏。本文从分析其主成分着手讨论信号的稀疏性。实际上，可以证明任意信号在其理想PCA基下都是绝对稀疏的。

定理：对于信号x=[x1,x2,…,xN]T∈N，则x在PCA基上绝对稀疏，且稀疏度为1。

证明：设信号x的自相关矩阵Rx为：

Rx=xxT，

(1)

因为Rx为实对称阵，故必存在正交阵U可将其特征值分解，使得：

UTRxU=Λ，

(2)

式中，Λ为非零特征值构成的对角阵，U为对应特征向量组成的正交阵，且UT=U-1。由于U是通过对信号x的自相关矩阵进行特征值分解得到的，故称其为信号x的PCA基。同时，信号x在其PCA基上的投影矢量α满足:

α=UTx,

(3)

可以证明α是绝对稀疏的，且稀疏度为1。

由式(1)～式(3)得：

ααT=(UTx)(UTx)T=UTxxTU=UTRxU=Λ,

(4)

由Λ的对角阵特性可知：

(5)

式中，Λij代表Λ的第i行、第j列元素，αi为α的第i个元素。因此，由式(5)知，存在一个固定的j使得

(6)

换句话说，α∈N当中仅有一个元素非零，即α为一个稀疏度为1的绝对稀疏信号，证毕。

信号经过PCA后体现的绝对稀疏性为后续的压缩感知重构奠定了理论基础。

1.2 压缩感知观测模型

压缩感知理论首先由Candès、Romberg、Tao和Donoho等人在2004年提出，文献直到2006年才发表[9-10]。Candès证明了只要信号在某一个正交空间具有稀疏性，就能以较低的频率采样信号，而且可以以高概率重构该信号[11-13]。

(7)

1.3 主成分追踪算法

这里需要注意的是，理论上对不同时刻的信号进行PCA，每次都需要重新进行酉变换得到变换矩阵U，但是可令一段时间之内的观测共用一个变换矩阵U，通过合理设置学习时间，能够在复杂度和性能当中寻求一个平衡。

算法1为主成分子空间追踪(PCSP)算法，具体数据如下：

输入:观测值矢量YM×1，观测矩阵ΦM×N，时间t，学习间隔T；

步骤2 (PCA分解)判断t是否被T整除，如果是则重新学习得到PCA基U，否则跳过此步骤；

步骤3 (计算相关系数)v=UTΦTrl,l=l+1；

2 数值实验及结果分析

利用全球海洋大气(Tropical Atmosphere Ocean,TAO)项目(网址：https:∥www.pmel.noaa.gov/tao /drupal/disdel)中2017年8月20日0时(UTC)起1 000 min实测水温数据，进行主成分分析的压缩感知重构仿真实验。

利用压缩感知观测模型对实测数据进行观测，依据1.3节中提出的PCSP算法对蒸发波导高度进行重构，由于PCA需要定期依据信号计算变换矩阵U，因此分别选择学习时间间隔为：20 min、100 min、500 min和1 000 min。

定量考察重构信噪比(Reconstruction-SNR,RSNR)随压缩比变化的规律，RSNR定义为：

(10)

压缩比取为0.1～0.5按步长0.05递增，即对应采集数据规模比原来的依据Shannon定律采样的数据规模减少了九成至五成，相应的传输、存储及处理成本也节省了一大半。以实际的大范围浮标系统为例，这将降低每个浮标的能耗、延长整个系统的使用寿命。另外由CS观测模型可知，每个浮标都可有“休眠”的时间，从另一个角度来看，系统还具有一定抗浮标损坏或数据丢失的能力。

对于水温这类可压缩信号，离散余弦变换(Discrete Cosine Transform,DCT)在性能上最接近最佳变换PCA[16]，因此本实验选取DCT作为对照组变换。实验结果如图1所示，PCSP算法基于PCA的感知结果由实线描绘，对照组的DCT由虚线描绘，不同学习时间间隔对应不同的标记符号。

图1 不同方法感知结果重构信噪比随压缩比变化情况

从图1中可以看出，基于主成分分析的蒸发波导压缩感知总体性能优于基于DCT的对照组性能，而且学习时间越短，RSNR越大，即重构准确性越好。随着压缩比增大RSNR有平缓上升的趋势，即使在压缩比低至0.1，学习间隔100 min时，RSNR也在20 dB以上，换而言之，在节省九成采样资源的前提下，主成分追踪算法最终的重构结果仍然能够达到重构信噪比20 dB的水平。当然，付出的代价是每100 min需要重新学习，以如今的计算能力是能够接受的，而且还可以通过调整学习时间间隔，在重构性能和复杂度之间寻求一个平衡。

3 结束语

文中所述基于主成分分析的压缩感知为从相对稀少的观测数据中重构信号提供了可能，也为提高压缩感知压缩率提供了理论支持。

从结果来看，本文PCSP算法基于PCA的感知结果总体性能优于基于DCT的对照组性能，且学习时间越短，RSNR越大，即重构准确性越好。可以通过调整学习时间间隔，在重构性能和复杂度之间寻求一个平衡。

尽管DCT在降低相关性方面不如PCA有效，但是其好处是它的基函数是固定的、可分离的，且具有快速算法，所以对于蒸发波导态势强相关的情况来说，DCT可以近似PCA。如何兼顾两者优点，则是下一步需要解决的难题。

[1] Serra J,Testa M,Molina R,et al.Bayesian K-SVD Using Fast Variational Inference[J].IEEE Transactions on Image Processing,2017,27(7): 3344-3359.

[2] Candès E J.The Restricted Isometry Property and its Implications for Compressed Sensing[J].Compte Rendus de l'Academie des Sciences,2008,Series I(346):589-592.

[3] Baraniuk R,Davenport M,DeVore R,et al.A Simple Proof of the Restricted Isometry Property for Random Matrices [J].Constructive Approximation,2008,28(3):253-263.

[4] 汪浩然,夏克文,牛文佳.分段正交匹配追踪(StOMP)算法改进研究[J].计算机工程与应用,2017,53(16):55-61.

[5] 杨亚旗,姚彦鑫.基于压缩感知和最小二乘的分布式协作频谱感知[J].电讯技术,2017,57(7):745-749.

[6] 张亚东,姚彦鑫.基于压缩感知的分布式协同估计算法[J].电讯技术,2017,57(4):377-381.

[7] Han Y,Shin W,Lee J.Projection-Based Differential Feedback for FDD Massive MIMO Systems[J].IEEE Transactions on Vehicular Technology,2017,66(1):202-212.

[8] Li J,Wang J.Robust Object Tracking Algorithm Based on Sparse Eigenbasis[J].IET Computer Vision,2014,8(6):601-610.

[9] Candès E,Romberg J,Tao T.Robust Uncertainty Principles:Exact Signal Reconstruction from highly Incomplete Frequency Information[J].IEEE Trans.on Information Theory,2006,52(2): 489-509.

[10] Candès E,Romberg J,Tao T.Stable Signal Recovery from Incomplete and Inaccurate Measurements[J].Commun.Pure Appl.Math,2006,59(8): 1207-1223.

[11] 刘朋露,杨洁.基于压缩感知DOA估计的稀疏阵列设计[J].电讯技术,2017,57(4):382-386.

[12] 童新,卿朝进,张岷涛,等.基于模式化压缩感知的帧定时同步研究[J].计算机工程与应用,2017,53(13):119-124.

[13] 李鑫滨,陈剑美.基于改进SL0压缩感知的WSN多目标定位[J].计算机工程与应用,2017,53(4):128-134.

[14] Wei D,Milenkovic O.Subspace Pursuit for Compressive Sensing Signal Reconstruction[J].IEEE Transactions on Information Theory,2009,55(5):2230-2249.

[15] Zhang Z,Xu Y,Yang J,et al.A Survey of Sparse Representation: Algorithms and Applications[J].IEEE Access,2015,3:490-530.

[16] Chen H,Zeng B.New Transforms Tightly Bounded by Dct and Klt[J].IEEE Signal Processing Letters,2012,19(6):344-347.