一种基于KSVD-ETF的测量矩阵优化方法 The Optimization Design of Measurement Matrix Based on KSVD-ETF

doi:10.12677/JISP.2014.31003

设为首页加入收藏期刊导航网站地图

期刊菜单

文章导航

Journal of Image and Signal Processing 图像与信号处理, 2014, 3, 15-18

http://dx.doi.org/10.12677/jisp.2014.31003 Published Online January 2014 (http://www.hanspub.org/journal/jisp.html)

The Optimization Design of Measurement Matrix

Based on KSVD-ETF

Yizhi Zhao2, Lixin Wang1,2, Jian Qian2

1No. 36 Research Institute of China Electronics Technology Group Corporation, Jiaxing

2School of Communication Engineering, Hangzhou Dianzi University, Hangzhou

Email: zhao_yizhi@163.com

Received: Nov. 26th, 2013; revised: Dec. 9th, 2013; accepted: Dec. 14th, 2013

stricted use, distribution, and reproduction in any medium, provided the origin al work is properly cited. In accordance of th e Creative Commons At-

guarded by law and by Hans as a guardian.

Abstract: Compressive sensing, a novel signal acquisition method, is a joint sensing-compression process which re-

quires a small number of measurements to reconstruct signal. Measurement matrix, a very important part in compres-

sive sensing, directly affects the adaptive sparsity, the required number of measurements and the reconstruct perform-

ance of the signal. In order to decrease the mutual coherence between the measurement matrix and sparse transformed

matrix and improve the quality of reconstruction, this pap er addr esses the joint optimization between measurement ma-

trix and sparse dictionary based on the KSVD-ETF. While optimizing the measurement matrix by ETF, we use th e

KSVD method to update the dictionary. The PSNR of the reconstructed signal is improved with the optimized meas-

urement matrix from the experimental results, indicating that this method of optimizing the measurement matrix has

certain advantages in the effect of reconstruction.

Keywords: Compressed Sensing; Measurement Matrix; Sparse Dictionary; Mutual Coherence; KSVD-ETF

一种基于 KSVD-ETF 的测量矩阵优化方法

赵毅智 2，汪立新 1,2，钱建2

1中国电子科技集团公司第 36 研究所，嘉兴

2杭州电子科技大学通信工程学院，杭州

Email: zhao_yizhi@163.com

收稿日期：2013 年11 月26 日；修回日期：2013 年12 月9日；录用日期：2013 年12 月14 日

摘要：压缩感知将数据的采样和压缩同时处理，仅需少量测量就能重建信号。测量矩阵直接影响着信号适应

的稀疏度范围和重建效果。为了减小测量矩阵与稀疏变换矩阵的互相干性，提出一种基于 KSVD-ETF 的测量矩

阵和稀疏表达字典联合优化的方法，在对测量矩阵进行 ETF 优化的同时利用 KSVD 方法更新优化表达字典，实

验结果中利用该方法优化矩阵所得重建信号 PSNR 有所提高，表明优化测量矩阵的方法在重建效果方面有一定

的优势。

关键词：压缩感知；测量矩阵；稀疏字典；互相干性；KSVD-ETF

1. 引言

压缩感知是信号处理领域中的一个新颖理论[1]，

它的核心步骤是在数据采样的同时对数据压缩，充分

利用了信号的稀疏性或者可压缩性，为突破传统的信

号处理方法提供了新的方向。压缩感知理论指出，只

要信号在某个变换域是稀疏的或者是可压缩的，那么

OPEN ACCESS 15

一种基于 KSVD-ETF的测量矩阵优化方法

就可以用一个跟变换基不相关的测量矩阵将变换所

得到高维信号投影到一个低维空间上，然后通过求解

一个非线性的优化问题就可以从这些少量的投影中

以高概率恢复出原信号[2]。该理论突破了传统的奈奎

斯特采样原理需要至少两倍信号带宽的限制，克服了

采样数据量巨大，传感元、采样时间以及数据存储空

间等物理资源浪费严重的问题，理论一经提出便得到

众多学者的高度关注。

测量向量获取和信号重建是压缩感知的核心步

骤，而测量矩阵直接影响着信号适应的稀疏度范围和

重建信号所需测量数目以及重建效果[3]，因此测量矩

阵的选取在压缩感知中起着关键作用，所以研究如何

构造性能更好的测量矩阵，或如何优化现有测量矩阵

的性能具有重要的意义。目前应用的测量矩阵主要有

两种，一种是随机测量矩阵，如高斯矩阵、贝努利矩

阵，亚高斯矩阵等；另一种是确定性测量矩阵，如部

分啥达玛矩阵、托普利兹矩阵、多项式矩阵等[4]。近

来研究表明，通过减小测量矩阵与稀疏变换矩阵的互

相干系数可以提高压缩感知的整体性能，互相干系数

影响着信号适应的稀疏度范围和重建信号所需测量

数目以及重建效果：互相干系数越小，信号适应的稀

疏度范围越大，重建信号需要的测量值的数目越少，

信号的重建效果也越好[5]。此类方法首先通过测量矩

阵和稀疏变换矩阵的乘积，构造其对应的 Gram 矩阵，

该矩阵非对角线元素即是测量矩阵和稀疏变换矩阵

的互相关系数，然后通过研究Gram 矩阵的特性改善

测量矩阵的性能[6]。Elad 通过阈值法来减小 Gram 矩

阵非对角线元素，进而减少测量矩阵和稀疏变换矩阵

的相关性[7]；Va hid Abolgha se mi采用梯度下降迭代法

来使得 Gram 矩阵接近于单位阵[8]；文献[9]则是通过

ETF(等角紧框架)来逐步更新 Gram 矩阵，让Gram矩

阵的非对角线元素都等于矩阵的最大的互相干系数，

以获得较好的性能。上述方法都是在减小Gram 矩阵

非对角线元素，进而得到优化的测量矩阵。本文从另

一角度出发，在对测量矩阵进行优化的同时采用

KSVD 方法对稀疏变换矩阵也进行优化，即测量矩阵

和表达字典的联合优化，通过仿真结果验证表明，联

合优化可以产生更好的信号重建效果。

2. 基于 Gram 矩阵的测量矩阵优化

压缩感知主要包括两个部分：编码(即信号的测量

采样)和解码(即信号重建)，本文的研究重点在信号的

编码部分。压缩感知理论的两个重要前提是稀疏性和

不相干性，稀疏信号在适当的表达基上可以由少量的

非零系数表达出来[10]。

设

∈x

是一个时域稀疏信号，如果

中只有

个非零元素，则

称为

的稀疏度。压缩感知的测量

过程可表示为

=Φyx

(1)

其中

∈y

为测量值，

[ ]

1mN

φφ

= ∈Φ

是测

量矩阵，一般有

mN

[11]。假设

在时域中不是稀疏

的，但是它可以在另外的基中被稀疏表示。即有

=Ψxθ

(2)

的稀疏表示形式，则

[ ]

1NK

ψψ

= ∈ΨR

称为稀

疏变换矩阵或表达字典，

[ ]

θθ

=θ

是信号

在

上的表达系数矢量。为了达到较好的压缩感知效

果，我们寻找与稀疏变换矩阵

相干性很小的测量矩

阵

，即使得矩阵

=ΦΨ

(3)

有很小的列向量相干系数，这里

称为恢复矩阵[12]。

Elad 引入了互相干系数概念

( )

max ij

ij dd

≠

=

，

然后构造

的Gram 矩阵

=G DD

(4)

通过优化 Gram 矩阵[13]，使其逼近单位阵

min

= −G GI

(5)

来减小

( )

。

通过使Gram 矩阵逼近等角紧框架(ETF)来减小

相干性时，设

是一组

mN×

的ETF 对应的 Gram

矩阵集合[14]：

N NNG

Λ ΛΛ

≠





=∈==









GR GG

(6)

使

的Gram矩阵逼近

，即：

min F

−GG

( 7)

这是一个迭代更新

的过程：首先计算出

1P−

=G DD

，然后将它投影到

上得到

，最后

通过

( )

PP P

γγ

+−

= +−GG G

得到更新的 Gram矩阵

，

对

进行 QR 分解可得到更新的

[15]。本文则是利用

奇异值分解(SVD)的方法获得

，最后测量矩阵可由

OPEN ACCESS

一种基于 KSVD-ETF的测量矩阵优化方法

1−

=Φ ΨD

得到，经过一系列的迭代运算，就能达到优

化测量矩阵的效果。

3. 测量矩阵和表达字典的联合优化

KSVD 方法是一个字典训练算法，若

nK×

∈D

，

∈x

，

y∈

分别代表字典、训练信号、训练新号

的稀疏表示稀疏向量，

{ }

为

个训练信号的

集合，

{ }

为

的解向量集合，则 KSVD 训练

方法的目标方程为：

min. .,

st is

− ∀≤



Y DX

(8)

其中

为稀疏表示系数中非零分量的数目上限。上式

的求解是一个迭代过程。首先，假设字典

是固定的，

用MP、OMP 或BP 算法可以得到字典

上

的稀疏

表示系数矩阵

；然后根据系数矩阵

找到更好的

字典

。

联合优化的思想是利用基于 KSVD 方法更新表

达字典和基于等角紧框架(ETF)方法更新测量矩阵的

综合，来解决下面的问题：

{ }

min. .,

st i

ΨΦΘ − +−∀XYΨΘ ΨΦΘ

≤



(9)

是

在

上的稀疏表示，常量参数

≤≤

用来控制

−ΨΘX

的加权误差。

(9)可以写成下面的形式

min. .,

st is

αα θ

ΨΦΘ

 

− ∀≤

 

 

ΨΘ



(10)

若定义



=



，



=



，则上式可写成

min. .,DΘ

eq i

st is

ΨΦΘ

− ∀≤



(11)

这里

eq eq

eq K



== 

ΨDW

。上式的解可以

通过 ETF优化测量矩阵和 KSVD 方法获得。具体

算法步骤如下：

输入：

-字典，

-随机矩阵，

-调整元素，

Iter-迭代次数；

初始化：设

∈X

为任意的训练信号序列；

循环：设定

0k=

，循环 Iter 此

(1) 将

投影到

上

=ΦYX

，

(2) ETF 优化

得到

，

(3) (1)、(2)结果带入(11)式中运用正交匹配算

法(OMP)得到

，然后由 KSVD 方法得到

(4) 利用ETF 优化后的

从

中得到更新字

典

，而在下一轮的迭代中再用

去优化测量矩阵

，继续利用 KSVD 方法获得更新的字典

(5)

1Kk= +

，重复上述过程

输出：以上算法输出为

Iter

和

Iter

。

4. 仿真实验

我们随机选取

64 5000×

的训练序列

NP×

∈X

，通

过ETF优化和 KSVD方法来获得优化的测量矩阵

和更新字典

。实验中选择了随机高斯矩阵和 ETF

优化矩阵方法进行对比仿真。

文献[12]中提出了基于 Gram 矩阵的

t−

平均互相

干性，这样能够更好的描述互相干性的意义。

t−

平

均互相干性定义为Gram 矩阵中所有非对角的值大于

的元素和的平均值，如下式：

{ }

()

( )

1, ;

ij ij

i jnij

g tg

≤≤≠

≥⋅

=≥

∑

(11)

选取本文优化的表达字典，我们分别计算三种测

量矩阵的

{ }

如表 1。

从表中可以看出 KSVD-ETF 优化矩阵的

{ }

值最小，即本文方法可以减小

t−

平均互相干性。

下面我们讨论测量值数目 m对图像重建结果的

影响。对于给定的 m值，我们利用正交匹配追踪重建

算法进行重建，计算重建图像的峰值信噪比 PSNR。

实验中，我们设定测量值数目m从20到160 变化，

重建图像的峰值信噪比 PSNR随测量值数目 m的变化

情况如图 1所示，很明显可以看到采用本文提出的优

化方法后的测量矩进行图像重建可以提高重建信号

的PSNR，改善重建质量。

我们也测试了 KSVD-ETF 方法更新的表达字典

和傅里叶正交变换矩阵两个不同表达基的稀疏对比

情况，设定信号稀疏度 s从6到20变化，经正交匹配

追踪重建算法进行重建的信号峰值信噪比 PSNR随信

号稀疏度 s的变化情况如图 2，可以看出本文方法所

得表达字典具有更好的性能。

5. 结论

本文提出一种在压缩感知中优化测量矩阵的算

OPEN ACCESS 17

一种基于 KSVD-ETF的测量矩阵优化方法

Table 1. Different measurement matrix of

t−

average mutual

coherence,

0.8t=

表1. 不同测量矩阵的

t−

平均互相干性，

0.8

测量数目 m

{ }

，

0.8t=

KSVD-ET 优化矩阵 ET 优化矩阵随机高斯矩阵

10 0.6431 0.7383 0.8024

15 0.7023 0.8174 0.8491

20 0.7173 0.8062 0.8589

25 0.7854 0.8393 0.8805

Figure 1. The reconstructed signal PSNR with measured value

changes in number of M

图l. 重建信号的 PSNR随测量值数目m的变化情况

Figure 2. The reconstructed signal of PSNR changes with the signal

sparsity S

图2. 重建信号的 PSNR 随信号稀疏度 s的变化情况

法，在对测量矩阵进行 ETF 优化的同时，利用KSVD

方法更新优化表达字典，将测量矩阵和表达字典联合

优化。实验结果表明，联合优化方法使得Gram 矩阵

的

t−

平均互相干系数

{ }

明显减小，重建信号峰

值信噪比 PSNR 也有所提高。基于以上讨论，可以证

明采用本文方法优化后的测量矩阵进行可以降低测

量矩阵和稀疏表达字典的相干性，提高压缩感知的性

能和重建质量。

参考文献 (References)

[1] Donoho, D. (2006) Compressed sensing. IEEE Transactions on

Information The ory, 52, 1289-1306.

[2] Candes, E.J. and Wakin, M.B. (2008) An introduction to com-

pressive sampling. IEEE Signal Processing Magazine, 25, 21-

30.

[3] 张凯, 杜小勇, 王壮 (2011) 基于压缩感知的空间目标三维

雷达成像方法.

信号处理

, 9, 1406-1411

[4] Tropp, J.A. and Gilbert, A.C. (2007) Signal recovery from ran-

dom measurements via orthogonal matching pursuit. IEEE

Transactions on Informati on Theory, 12, 4655-4666.

[5] 刘丹华, 石光明, 周佳社 (2008) 一种冗余字典下的信号稀

疏分解新方法.

西安电子科技大学学报

, 35, 228-232.

[6] Candes, E.J., Romberg, J. and Tao, T. (2006) Robust uncertainty

principles: Exact signal reconstruction from highly incomplete

frequency information. IEEE Transactions on Information The-

ory, 52, 489-509.

[7] Strohmer, T. (2008) A note on equiangular tight frames. Linear

Algebra, 429, 326-330.

[8] Renes, J.M. (2007) Equiangular tight frames from paley tour-

namenrs. Linear Algebra, 426, 497-501.

[9] Zahedi, R., Pezeshki, A. and Chong, E.K.P. (2010) Robust mea-

surement design for detecting sparse signals: Equiangular uni-

form tight frames and grassmannian packings. American Control

Conference, Baltimore, June 30-July 2 2010, 4070-4075.

[10] Tropp, J.A., Dhillon, I.S., Heath, R.W. and Strohmer, T. (2005)

Designing structured tight frames via an alternating projection

method. IEEE Transactions on Information Theory, 51, 188-

209.

[11] Endra (2011) Color image reconstruction from compressive

sensing with optimized measurement matrix, Binus ICT Na-

tional Conference, 15-16.

[12] Elad, M. (2007) Optimized projections for compressed sensing.

IEEE Transactions on Signal Processing, 55, 5695-5702.

[13] Duarte-Carvajalino, J.M. and Sapiro, G. (2009) Learning to

sense sparse signals: Simultaneous sensing matrix and sparsify-

ing dictionary optimization. IEEE Transactions on Image Pro-

cessing, 18, 1395-1408.

[14] Xu, J.P., Pi Y.M. and Cao, Z.J. (2010) Optimized projection

matrix for compressive sensing. EURASIP Journal on Advances

in Signal Processing, 2010, 560349.

[15] Oey, E. and Gunawan, D. (2011) Image reconstruction from

compressive sensing with optimized measurement matrix, 12th

International Conference on Quality in Research (QiR), 4-7 July

2011.

20 40 60 80 100 120 140 160

PSNR(dB)

随机高斯矩阵

ETF 优化矩阵

KSVD-ETF优化矩阵

68 10121416 1820

PSNR(dB)

傅里叶正交变换矩阵

KSVD-ETF 更新字典

OPEN ACCESS