对于稀疏信号,压缩感知(compressive sensing,CS)可以在特定的条件下对信号进行采集的同时对其压缩,并以比奈奎斯特采样定理低得多的采样频率进行高质量的信号重构[1-4]。CS的数学模型如式(1)所示:
min ‖x‖0 s.t. y=Φx
(1)
其中,y是测量数据,y∈RM;Φ是测量矩阵,Φ∈RM×N,M<N,M为测量矩阵的行数,N为测量矩阵的列数;x是稀疏信号,x∈RN;K是稀疏度,K≼N;min ‖x‖0是目标函数,y=Φx是约束函数;‖·‖0是l0范数。
CS的约束等距特性(restricted isometry property,RIP)如式(2)所示:
(1-σK)‖x‖2≤‖Φx‖2≤(1+σK)‖x‖2
(2)
其中σK∈[0,1)。
如果测量矩阵满足RIP,并将式(1)中的目标函数替换为min‖x‖1,则式(1)可转化为凸优化问题[1,5,6],‖·‖1是l1范数。因此,可以获得稀疏信号的最优解。
测量矩阵满足RIP准则是实现压缩采样信号有效重构的关键,但是判断测量矩阵是否满足RIP很难。因而RIP缺乏实用性和可用性[7]。当前判断测量矩阵性能的主要判据是测量矩阵列间相关系数绝对值的最大值(μcmax),如式(3)所示:
(3)
其中,Φi和Φj分别是测量矩阵的第i和j列。测量矩阵的μcmax越小,其性能越好。从而在重构过程中可以获得更好的重构效果[8]。
压缩感知中测量矩阵的设计、优化和性能是关系信号重构的关键因素。高斯矩阵、0-1随机矩阵(简称为随机矩阵)与0-1循环矩阵(简称为循环矩阵)是在压缩感知研究和应用中广泛使用的3种测量矩阵[1,5,9]。高斯矩阵虽然具有好的RIP、信号重构能力和普适性,但难以硬件实现。随机矩阵和循环矩阵都易于通过数字微镜(digital micromirror device,DMD)实现。循环矩阵在硬件实现和编程设计方面比随机矩阵更有优势。尽管随机矩阵和循环矩阵的列不相关性差,但通过测量矩阵的优化算法可以极大改善和提高测量矩阵的列不相关性,从而获得不弱于高斯矩阵的信号重构效果[7-8]。
矩阵优化设计的准则主要是列间相关性最小化[10-12]。Elad和Duarte[11-12]以列间相关性最小化为目标进行矩阵优化。尽管取得了较好的优化效果,但存在方法复杂、操作不便的弊端,而且是非直接优化。对测量矩阵Φ做各行正交规范化处理后,可得到优化矩阵ΦO,优化矩阵的性能好于测量矩阵。通过优化矩阵可求得过渡矩阵T=ΦOΦT(ΦΦT)-1以及近似矩阵ΦT[7-8]。在重构阶段以测量阶段的测量数据,通过式(4)可重构得到更好的重构效果[7-8]。
min‖x‖0 s.t. yT=ΦTx
(4)
其中yT=Τy,ΦT=ΤΦ。
256是小压缩比(测量矩阵的列数与行数之比)压缩感知研究中常用的测量矩阵列数[7-8,13];4 096是大压缩比压缩感知研究中常用的测量矩阵列数[14-17]。如何从优化设计角度选择合适大小的测量矩阵缺少相关研究。因此,本文基于列不相关性,研究了不同压缩比的最大列数为256和 4 096的随机矩阵、循环矩阵与高斯矩阵,为测量矩阵优化提供指引和方向,避免压缩感知中测量矩阵选择的盲目性。
为构建筛选测量矩阵的依据,分别研究最大列数为256和4 096的随机矩阵、循环矩阵与高斯矩阵优化前后的性能变化,并总结其分布规律。 随机矩阵和循环矩阵中每行随机分布k个1,k=N×13/36 (如k不为整数,则取小于该数的最大整数),除1外其它元素均为0。循环矩阵中各行向量都是前一行向量各元素依次右移2位的结果。k=N×13/36是经过大量筛选实验获得的经验值。它能较好满足同一矩阵中不出现相同行或列,而且1的数量尽量少的要求。
最大列数为256的测量矩阵,行数依次取32、44、56、68、80、92、104、116和128,列数依次取128、144、160、176、192、208、224、240和256。然后,行数和列数排列组合成不同行列数的测量矩阵。因为128行和128列的矩阵已是方阵,不再满足压缩感知的适用条件,所以行数的最大值和列数的最小值只能取到128。最大列数为4 096的测量矩阵,行数依次取32、256、480、704、928、1 152、1 376、1 600、1 824和2 048,列数依次取2 048、2 304、2 560、2 816、3 072、3 328、3 584、3 840和4 096。然后,行数和列数排列组合成不同行列数的测量矩阵。因为2 048行和2 048列的矩阵已是方阵,不再满足压缩感知的适用条件,所以行数的最大值和列数的最小值只能取到2 048。一般数量大于等于30份的样本,称为大样本。这时研究对象都会具有较好的概率稳定性。因此最小行数取值32。最大列数为256的测量矩阵,随机生成每种测量矩阵100个。最大列数为4 096的测量矩阵,随机生成每种行列数的测量矩阵50个。计算相应的μcmax,取平均值并将以等值线的形式绘于图1~图6,图中相邻等值线之差为0.05。
图1是最大列数为256的随机矩阵优化前后及其差值的等值线图。由图1可知,优化前介于0.58和0.82,优化后介于0和0.70。优化后,列间相关性降低,降低量介于0.12和0.58。随机矩阵的性能都得到改善。图1~图6的(c)图中红线表示压缩比为2的行列数不同的测量矩阵。红线上方压缩比小于2,红线下方压缩比大于2。由图1(c)可见,压缩比为2时优化前后的差值约0.325。随机矩阵性能得到较好改善。压缩比越大,随机矩阵性能改善越小;压缩比越小,则反之。
图2是最大列数为4 096的随机矩阵优化前后及其差值的等值线图。由图2可知,优化前介于0.44和0.93,优化后介于0和0.90。优化后,列间相关性降低,降低量介于0.03和0.44。随机矩阵的性能都得到改善。由图2(c)可见,压缩比为2时优化前后的差值约为0.35。随机矩阵的性能得到较好改善。压缩比越大,随机矩阵性能改善越小;压缩比越小,则反之。当行数在256行以下时,随机矩阵优化前和优化后的不随列数的增加而改变,等值线都是平稳的波浪线。因此,图2(c)的相应等值线也是平稳的波浪线。
图1 最大列数为256的随机矩阵优化前后及其差值的等值线图
Fig.1 Contour map of and its difference before and after optimization of a random matrix with a maximum number of 256 columns
图2 最大列数为4 096的随机矩阵优化前后及其差值的等值线图
Fig.2 Contour map of and its difference before and after optimization of a random matrix with a maximum number of 4 096
图3是最大列数为256的循环矩阵优化前后及其差值的等值线图。由图3可知,优化前介于0.52和0.79,优化后介于0.22和0.66。优化后,列间相关性降低,降低量介于0.13和0.35。循环矩阵的性能都得到改善。由图3(c)可见,压缩比为2时优化前后的差值约0.3。循环矩阵的性能得到较好改善。压缩比越大,循环矩阵性能改善越小;压缩比越小,则反之。 比较图1和图3的上部可以发现,随机矩阵的等值线都是阶梯状。而循环矩阵优化前和优化后的等值线出现楔形山谷状形貌。山谷区域列间相关性小,范围很大,不同压缩比和行列数的循环矩阵都存在于该区域。因此是优质的循环矩阵候选区,可根据需要筛选得到性能优良的循环矩阵。图3(c)中存在等值线山峰形貌。山峰区域是循环矩阵优化效果最明显的区域。
图4是最大列数为4 096的随机矩阵优化前后及其差值的等值线图。由图4可知,优化前介于0.42和0.91,优化后介于0.07和0.87。优化后,列间相关性降低,降低量介于0.04和0.36。随机矩阵的性能都得到改善。由图4(c)可见,压缩比为2时优化前后的差值约0.35。随机矩阵的性能得到较好改善。压缩比越大,随机矩阵性能改善越小;压缩比越小,则反之。当行数在256行以下时,随机矩阵优化前和优化后的不随列数的增加而改变,等值线都是平稳的波浪线。因此,图4(c)的相应等值线也是平稳的波浪线。
图3 最大列数为256的循环矩阵优化前后及其差值的等值线图
Fig.3 Contour map of and its difference before and after optimization of the circulant matrix with the maximum number of columns of 256
图4 最大列数为4 096的循环矩阵优化前后及其差值的等值线图
Fig.4 Contour map of and its difference before and after optimization of the circulant matrix with the maximum number of columns of 4 096
图5是最大列数为256的高斯矩阵优化前后及其差值的等值线图。由图5可知,优化前介于0.34和0.67,优化后介于0和0.65。优化后,列间相关性降低,降低量介于0.02和0.34。高斯矩阵的性能都得到改善。由图5(c)可见,压缩比为2时优化前后的差值约0.1。而随机矩阵和循环矩阵都达到0.35。高斯矩阵的性能改善幅度小于随机矩阵和循环矩阵。压缩比越大,高斯矩阵性能改善越小;压缩比越小,则反之。
图6是最大列数为4 096的高斯矩阵优化前后及其差值的等值线图。
由图6可知,优化前介于0.11和0.79,优化后介于0和0.79。优化后,列间相关性降低,降低量介于0和0.11。高斯矩阵的性能都得到改善。由图6(c)可见,压缩比为2时优化前后的差值约0.05。而随机矩阵和循环矩阵都达到0.35。高斯矩阵的性能改善幅度远小于随机矩阵和循环矩阵。高斯矩阵的性能得到的改善有限。压缩比越大,高斯矩阵性能改善越小;压缩比越小,则反之。图6(c)是50次试验后的均值图,有时单个高斯矩阵优化后,列间相关性不但没有降低,反而升高,优化失效。
图5 最大列数为256的高斯矩阵优化前后及其差值的等值线图
Fig.5 The contour map of and its difference before and after optimization of the Gaussian matrix with the maximum number of columns of 256
图6 最大列数为4 096的高斯矩阵优化前后及其差值的等值线图
Fig.6 The contour map of and its difference before and after optimization of the Gaussian matrix with the maximum number of columns of 4 096
当高斯矩阵列数很大时,如果行数很大,各列包含的元素很多,各列之间已经近似正交。即使对高斯矩阵优化,可优化的空间和潜力都非常有限。如果行数较少,各列包含的元素不多,样本容量不够。而列数很大,导致大概率出现列相关性较大的列。因此,图6(a)中行数小于256的高斯矩阵的等值线迅速趋近于1。这时对高斯矩阵优化,可优化的空间和潜力也非常有限。因此,测量矩阵优化适用于随机矩阵和循环矩阵和最大列数较少的高斯矩阵,不适用于最大列数很大的高斯矩阵。
128×256是各种压缩感知研究中经常采量矩阵用的测大小[7,13]。当测量矩阵列数采用4 096时,多采用超大压缩比[16]。图7和图8采用正交匹配追踪( orthogonal matching pursuit,OMP)算法[13]给出了128×256和32×4 096的随机矩阵、循环矩阵和高斯矩阵优化前后对相同信号的重构结果。信号采用高斯稀疏信号,对每个稀疏度都重复试验50次,然后计算信号的精确重构概率,仿真软件采用Matlab R2015b。
由图7可见,128×256的随机矩阵、循环矩阵和高斯矩阵优化后的曲线位于优化前的上方,重构质量和效果获得很大改善。由图8可见,32×4 096的随机矩阵和循环矩阵优化后的曲线位于优化前的上方,重构质量和效果获得较大改善。但是高斯矩阵优化前后的曲线几乎重合在一起,重构效果没有改善。
图7 128×256的3类矩阵优化前后重构概率与信号稀疏度的关系曲线
Fig.7 The relationship curve between reconstruction probability and signal sparsity before and after optimization of 128×256 three types of matrices
图8 32×4 096的3类矩阵优化前后重构概率与信号稀疏度的关系曲线
Fig.8 The relationship curve between reconstruction probability and signal sparsity before and after optimization of 3 types of 32×4 096 matrices
表1为128×256和32×4 096的随机矩阵、循环矩阵和高斯矩阵优化前后的μcmax及其差值。由表1可见,128×256的随机矩阵、循环矩阵和高斯矩阵优化前后的μcmax分别提高0.333、0.310和0.099。由表1可见,32×4 096的随机矩阵、循环矩阵和高斯矩阵优化前后的μcmax分别提高0.018、0.024和0.003。对图7、图8和表1综合考虑,测量矩阵优化后的μcmax提高约0.01,就能获得明显的重构效果改善。32×4 096的高斯矩阵优化后的μcmax仅提高约0.003,因此导致重构效果无改善。
表1 3类矩阵优化前后μcmax及其差值
Table 1 μcmax and its difference before and after optimization of three types of matrices
128×256随机矩阵循环矩阵高斯矩阵32×4 096随机矩阵循环矩阵高斯矩阵优化前0.5930.4820.3610.9350.9610.778优化后0.2600.1820.2620.9170.9370.775优化前后之差0.3330.3100.0990.0180.0240.003
统计并绘制了最大列数为256和4 096的随机矩阵、循环矩阵和高斯矩阵优化前后的及其差值的等值线图。在压缩感知研究和应用中,可查阅等值线图筛选所需的测量矩阵和具有优化潜力的测量矩阵,避免了测量矩阵选择的盲目性。研究发现,测量矩阵优化适用于最大列数为256和 4 096的随机矩阵和循环矩阵,以及最大列数为256的高斯矩阵;但是测量矩阵优化不适用于最大列数为4 096的高斯矩阵;给出了相应的理论分析。发现最大列数为256的循环矩阵优化前和优化后的等值线出现楔形山谷状形貌,山谷区域列间相关性小,覆盖范围很大,是优质的循环矩阵候选区;可根据需要筛选得到性能优良的各种大小的循环矩阵。
[1] DONOHO D L.Compressed sensing[J].IEEE Transactions on Information Theory,2006,52(4):1289-1306.
[2] 曾帆,黄惠详,童峰.采用压缩感知的麦克风阵列远场声源方位估计[J].兵器装备工程学报,2018,39(05):134-138.
ZENG F,HUANG H X,TONG F.Far field compressed sensing microphone array DOA estimation[J].Journal of Ordnance Equipment Engineering,2018,39(05):134-138.
[3] 周珺,黄尉.多面体块稀疏表示和非凸压缩感知[J].中国科学:数学,2020,50(1):1-16.
ZHOU J,HUANG Y.Block sparse representation of a polytope and non-convex compressed sensing[J].Scientia Sinica Mathematica,2020,50(1):1-16.
[4] LIANG J,ZHU L,WANG L.Singl-shot real-time femtosecond imaging of temporal focusing[J].Light,Science & Applications,2018,7(1):1951-1963.
[5] TSAIG Y,DONOHO D L.Extensions of compressed sensing[J].Signal Processing,2006,86(3):549-571.
[6] LIANG J,WANG P,ZHU L,et al.Singl-shot stereo-polarimetric compressed ultrafast photography for light-speed observation of high-dimensional optical transients with picosecond resolution[J].Nature Communications,2020,11(10):52521-52510.
[7] 程涛,朱国宾,刘玉安.基于0-1稀疏循环矩阵的测量矩阵分离研究[J].光学学报,2013,33(02):172-177.
CHENG T,ZHU G B,LIU Y A.Separation research of measurement matrices based on 0-1 sparse circulant matrix[J].Acta Optica Sinica,2013,33(02):172-177.
[8] CHENG T.Reconstruction improvement of single-pixel camera based on operator matrix-induced compressive sensing[J].Geodetski list,2020,41(3):283-296.
[9] 邹劲松,潘东洋,周启武,等.一种改进的低压电力线载波通信压缩感知信道估计方法[J].重庆理工大学学报(自然科学),2019,33(11):155-161.
ZOU J S,PAN D Y,ZHOU Q W,et al.An improved compressed sensing channel estimation method for low voltage power line carrier communication[J].Journal of Chongqing Univerity of Technology(Natural Science),2019,33(11):155-161.
[10] 赵瑞珍,秦周,胡绍海.一种基于特征值分解的测量矩阵优化方法[J].信号处理,2012,28(5):653-658.
ZHAO R Z,QIN Z,HU S H.An optimization method for measurement matrix based on eigenvalue decomposition[J].Signal Processing,2012,28(5):653-658.
[11] ELAD M.Optimized projections for compressed sensing[J].IEEE Transactions on Signal Processing,2007,55(12):5695-5702.
[12] DUARTE-CARVAJALINO J M,SAPIRO G.Learning to sense sparse signals:simultaneous sensing matrix and sparsifying dictionary optimization[J].IEEE Transactions on Image Processing,2009,18(7):1395-1408.
[13] 方红,杨海蓉.贪婪算法与压缩感知理论[J].自动化学报,2011,37(12):1413-1421.
FANG H,YANG H R.Greedy algorithms and compressed sensing[J].Acta Automatica Sinica,2011,37(12):1413-1421.
[14] 程涛,陈丹妮,于斌.STORM原始图像和基于点扩散函数测量矩阵的压缩感知后处理方法[J].探测与控制学报,2017,39(4):31-38.
CHENG T,CHEN D N,YU B.Compressive sensing post processing of STORM’s raw images and measurement matrix based on PSF[J].Journal of Detection & Control,2017,39(4):31-38.
[15] CHENG T,CHEN D,YU B,et al.Reconstruction of super-resolution STORM images using compressed sensing based on low-resolution raw images and interpolation[J].Biomedical Optics Express,2017,8(5):2445-2457.
[16] ZHU L,ZHANG W,ELNATAN D,et al.Faster STORM using compressed sensing[J].Nature methods,2012,9(7):721-723.
[17] BABCOCK H P,MOFFITT J R,CAO Y,et al.Fast compressed sensing analysis for super-resolution imaging using L1-homotopy[J].Optics Express,2013,21(23):28583-28596.
Citation format:WU Xiaolong, CHENG Tao, LI Degao, et al.Applicability of Contour map and Optimization of Measurement Matrix Screening in Compressed Sensing[J].Journal of Ordnance Equipment Engineering,2021,42(12):203-209.