2020年10月第40卷第5期
天水师范学院学报
Journal of Tianshui Normal University
Oct.，2020
V〇1.40 No.5
王三福，刘劾，王艳丽，王聃聃，刘丽，李娟
(天水师范学院数学与统计学院，甘肃天水741001)
摘要：在信号处理方向上，为了对信号进行稀疏表示，利用了信号分析模型中的最小特征值方法，提出了 一种求解信号稀疏表示合成模型的新方法，该方法称为最小特征值伪逆方法（S M E M P).首先，分析了国内外专 家在此问题上的研究进展，其次，对最小特征值方法进行了收敛性证明，最后，利用最小特征值方法与矩阵伪逆 计算的结合，提出了求解信号稀疏表示合成模型的最小特征值伪逆方法.通过理论 分析和数值实验表明，用最小 特征值伪逆方法对数字信号进行稀疏表示，具有运算速度快、稀疏度灵活可控等优点，可以促进模式识别、人工 智能等领域的进一步研究.
关键词：数字信号；伪逆矩阵；稀疏表示；最小特征值
中图分类号：TN911.7 文献标识码： A 文章编号：1671-1351 (2020) 05-0022-06
随着人类社会的快速发展，人们生活中的信息 数据量急剧增加，大数据处理已成为整个世界面临 的重大课题，人们想尽各种办法来压缩数据的存储 量.信号的稀疏表示问题成为数字信号处理的热点 问题和处理大数据的重要手段.关于信号的稀疏表 示问题，已经有很多相关的模型被构建，有力地推 动了人工智能领域中智能学习的研究.
2011 年 Boaz Ophir,Michael Elad等人，在欧洲 的f目号处理会议（European Signal Processing Conference)上，发表论文"Sequential minimal eigenvalues-an approach to analysis dictionary learning"，提出了最小特征值方法（SME).111目前该论文被引用 62次，在信号稀疏表示领域具有一定的影响力. 2013 年由 Rubinstein 和 Elad等人提出了Analysis K_SVD模型，|2i从另外一个视角研究了信号的稀疏 表示问题.将K_SVD算法引入到分析字典学习模 型中，收到良好的效果. 稀疏表示及其计算已经是在信号处理和图像处 理方面的众所周知的热点问题，[3_81信号的稀疏表示
为提供了一种用低维数据表达高维数据各种信息的 手段.[91°]2019年王凯等人将信号的稀疏表示用于 相干信号测向，[1112020年司韦建等人将数字信号的 稀疏表示应用于参数估计，"2|这对信号稀疏表示的 应用研究具有推动作用.
关于信号的稀疏表示模型，主要有合成模型与 分析模型两个研究方向.目前的方法都存在对稀疏度控制不够灵活的问题.本文结合了最小特征值方 法与矩阵伪逆计算方法，提出了求解信号稀疏表示 合成模型的最小特征值伪逆方法.既加快了数字信 号稀疏表示的运算速度，也增加了对稀疏度控制的 灵活性.
1稀疏表示模型
把研究的信号的全集记为中，将信号样本训练 集 F(F,,1/2,…，F J(K,e O)，分解为字典 £»(£»,，02,…，/)…)与系数矩阵I(U2,…，义)的乘积，即为
V=D X,(1)其中，字典〇的每一列A称为字典的一个原子，X的每一列弋就是对应信号K的一组系数，有 V,= DX,.由于
V^DX,= ^x,Dr(2)
所以要求系数X是列稀疏，也就是X的第i列
半人马酋长作为I/，的系数有很少的非零元素.这 样，信号K可由很少个字典原子的线性组合来表 示，可见字典£>的构造成为图像稀疏表示问题中 的关键环节.
1.1稀疏表示的合成模型
对于一个未知信号x e圮，观察到的i;e/T往 往是它的某种线性变换后的近似结果（m<d)，即
v= P*x+ e.(3)
收稿日期：2020-10-20
作者简介：王三福（1968-)，男，甘肃甘谷人，天水师范学院数学与统计学院副教授，硕士。
基金项目：国家自然基金项目“反常扩散方程的高阶数值算法及其在天水地下水质研究中的应用”（11561060)阶段性成果22
其中ee/T是满足||e f矣s的加性噪声.这里的任 务是利用观察到的一组数据V〇/,，F2，…，FJ ，得到变 换矩阵和原信号.若不计加性噪 声（e= 0)，则问题变成：已知样本K，求矩阵£)和X，使得
V=D X.(4)为了表示一个信号v e/r，需要一个字典Z)e/r x l，D的每一列就是一个原子，它由it个原 子组成，即D(D,，D2，…，其表示过程为：
V(:，i)= =々,.£),+；^£)2+ …+\丸二D'= £)X(:，i)，（5) 其中列向量足为信号V，在字典0下的表示系数.如 果A的非零元素很少，则弋称为的稀疏表示.在稀疏表示中，字典Z)是非常重要的，字典Z)的获 得，通常使用已有的n个样本数据1/…)进行训练得到的.
增加了系数的稀疏性约束条件，该问题可以表示为
该模型称为信号稀疏表示的合成模型（synthe-s i s model).
1.2稀疏表示的分析模型
已知/I个样本信号•••，!/…)，需要求解一 个线性变换I W T—K p，使变换结果为
n K(K,，K2，…，K,)= Z(H，…，尤)，(7)使得列向量足是稀疏的，这种模型称为信号 稀疏表的分析模型（analysis model).
分析求解稀疏表示的分析字典的基本原理.
对于一组信号••，…)£ i T"，寻一个 分析的字典fte/T"，使得字典乘以样本信号，能 够得到一个稀疏的表示.
卜丨丨1。= ?，⑶
其中||*||。为向量的非零个数，公式（8)表示相乘 后的向量的非零元素很少.
设弋的长度为的稀疏度即零元素个数为，，则
丨丨弋丨丨。=/^，⑷目前，解决稀疏表示分析模型最典型的方法是 最小特征值方法（S M E).
1.3分析模型的最小特征值方法（S M E)
对于已知信号样本K(F,，l/2，…，，要求矩阵 使得
11抑。=丨丨叫||。=?-/，（1〇)其中P为戈的长度，Z为足的稀疏度即零元素个数.
设Z(X,，Z2,…，;U= ，由于列向量足中至少有/个零元素，所以，X中至少共有n x/个零元
素.Z有P行，平均每行有 <；个零元素.手机图铃
P
设f为矩阵X的第；行，则可以表示成
X(X…X2,-,x n)=s i v=(x',x\--,x y,(n)
设叫为矩阵n的第；行，则
c〇y=X\(i= 1,2,•••,/,).(12)现已知V，求叫，使得（12)式中行向量r
有W个零元素.
p
行向量的第_/个元素，是行向量叫与^的第；列的乘积，到一个与V的第列正交的向量作为叫，行向量r的第；'个元素自然就为零了，因为正交向量乘积为零.为了达到稀疏度的要求，
要的行向量w，至少要和f中的¥个列向量正
p
交，才能保证r中有 <；个零元素.
迂回运输
p
于是，利用最小特征值，在F中选取恰当的 f列向量，构成矩阵F a.
设矩阵的特征值从小到大为(《,‘•••)，它 们对应的特征向量分别为(r,，r y)，于是它们满 足公式
h(V X)= hT k,(13)只有选择最小特征值时，等于零或最 接近零，就把最小特征值对应的特征向量作为行向 量叫.
接着计算行向量义‘=w,P，将A"‘中最小的M
P 个元素设为零，并将这些元素的位置标号记做八，重新构造匕<，再重复以上的工作，直到收敛.
这样就可以得到满足稀疏要求的分析字典O的第i 行 了.
求解n中的第i行叫的方法是用迭代法，具 体步骤如下：
第一步，随机产生向量叫；
第二步，计算X‘=叫K.i=l，2,…；
第三步，将^中的最小的4个元素设为零，
P
并将这些元素的位置标号记做A，在F中到与/\ 对应的列，构造矩阵
第四步，计算VAF A’的特征值和对应的特征向 量，设最小特征值为a，它对应的特征向量为w4+1;
23
第五步，如果||a +1-叭||2大于一个预定的很小的正数，则转到二步继续循环.否则，停止循 环，所得的％+1就是要求的行向量叫.
具体算法见算法1 -1.
算法1-1求解r i 中的一行w ，的方法
(1) 输入训练样本V ，确定阈值0。，初始阈值较大，为(2) 做循环直到衫久;
(2.1) 随机产生长度为m 的向量〇>，做以下四步循环，直
到cu 收敛.
(a) T=(〇*Y ;(b )
出r 中最小的f 个零元素组成向量7；，令e
为7\中的最大值；
(C )将r A 对应的y 中的列构成矩阵匕，计算的
特征值和对应的特征向量；
⑷将如更新为的最小特征麵对应的特征向量；
(2.2) 结束如的循环•(3) 结束0的循环.
有了计算分析字典〇中的第i 行的方法，那 么，令纟从1到/>，就可以得到整个分析字典 利用矩阵的最小特征值来计算分析字典的算法记为
S M E 算法，具体算法见算法1-2
算法1-2 SME 算法
(1)输入训练样本V ，令V , = V;
⑵所求分析字典矩阵有P 行，做循环i+=l ，2，"_,P ;
聚四氟乙烯
(2.1) 以V.为样本，运行算法1-丨，得到m 维向量让
n 的第i 行等于〇>;
(2.2) 修改训练样本V.得到V ,,,
U )当i </时，从V，中移除与f t 中的前；行都正交的
所有列，得到V,..,;
(b ) 当；>!时，从V，中移除这样的列，它与f t 的前i
行中的至少Z 行正交，得到V,.,,;
(c ) 当 i = Z 时，L , = V.
(3)结束；循环，得到分析字典矩阵fl.
1.4最小特征值方法（S M E )的收敛性证明对于文献[1]中的S M E 算法，文章中没有给出 该算法的收敛性证明.为了保证该算法的可靠性， 本文给出此迭代方法的收敛性证明.
要证明信号稀疏表示的分析字典的最小特征值 (S M E )算法的收敛性，就要从矩阵的特征值入 手，给出以下引理.
引理1.1丨131假设
是qq之父
Hermitian 矩
阵，即，
B H = S ，且4和的特征值分别 是 a ,, A (»= 1.2,•••,«)，满足 a ，矣 a 2：S …矣 a …
A A 矣…矣设
C =A + B 且W =l ，2,…，n )是C
的特征值.则
a l +/3l ^v ,^a I+^n .
(14)
由引理1.1，容易看出a ，矣意味着C 对应 的特征值是最大的.基于以上引理，提出关于SME 算法的收敛性定理.
定理1.1文献[1]中的S M E 算法是收敛的，如果 存在一个向量w e 圮使得
wT Xt ^9 .
(15)
*1
梯子不用时请横放其中0是0或者是一个很小的正数，&是训练样
本数据的某个列，
证明假定对于任意随机的初始向量矿和
一个初始阈值设八是作为七中零 元素下标的集合，利用下标集合A ，构建矩阵
X Ae R
利用能量模型，Q R 模型或Givens 模型，计算的最小特征值（A ,，叫)，满足1丨叫丨12 = 1，于是我们可进行二次循环.不失一般性，对一个新的阈值^使得
中有W 个非零元素，其中1是心中 P
的第Z 列(i = l ，2，"-，A ：丨，A ：, <A ：)，是小于这个阈值02的
(否则，从Z A 中交换对应的列).令;=(Z A 1,Z A 2)， 其中尤A ,e /^对应着前面的Jf ,,
则 K
=
•设（A 2，叫）是
的最小特征值，且丨丨叫丨丨2 = 1，计算公式为
A ,= W /w d l l ;. (16)A ^co /X ^
co ^Uco/XJIl
(17)
根据引理1.1的正定性质A 2<A , , i .e .,
同样地，第三个循环中，假定；^,=凡1,，；^12)，其 中是我们已经选择好的.让(A 3，叫）是
Z A ,,X A I ,f 的最小特征值，丨丨叫丨12=1 •显然，A 3<A 2,i .e .，l l <Z A …l l 2<l l a >/XJI 2，按照这种方式进行，就 得到一个序列：
l l w rZ An 112〈…< l l w /Z A 1l l 2 < l l a ^H . (18)
这里，行向量〇/将被作为分析运算fi 的第一行，
这就证明了 S M E 算法是收敛的.
2基于最小特征值和伪逆的稀疏表示方法
在信号的稀疏表示中，通过对样本信号的训 练，得到稀疏表示的字典和稀疏系数是的目的.本 节将利用1.3中分析模型得到的结果，以及矩阵的
M P -逆运算，从而得到一种新的合成模型的求解方
法，记作S M E M P 算法.
2.1 M P -逆
24
定义2.11141非奇异矩阵/le/r"，如果存在矩 阵P e/r"，使得
PA=AP=I,(19)其中/为单位矩阵.则矩阵P称为<4的逆矩 阵，记为/r=p.
定义2.21141非奇异矩阵/U/rx"，如果存在矩阵P e/T"，满足以下四个条件：
(1) APA=A；
(2) PAP=P ；
(3)/IP为 Hermitian矩阵，即〇4P)H=/IP ;
(4) P/1为 Hermitian矩阵，即（/M)H=P4.
则矩阵P称为/!的广义逆矩阵（Moore-Penrose逆 矩阵，简写为MP-逆).记作
A*= P.(20)伪逆是矩阵计算中的基本运算，对信号稀疏表 示的计算也有重要的使用价值.
2.2合成模型的求解方法
对于某一类信号（如人脸图像、语音等），需要一个字典对其中的每个信号进行稀疏表示.字典的获得一般采用对样本信号V的训练和 学习.而本文利用信号稀疏表示的分析算法，得 到分析字典矩阵进而采用矩阵M P-逆的方 法，得到信号稀疏表示合成模型的字典这就是本节的S M E M P算法.
对于信号的稀疏表示问题，构建的优化模型是：
s-1-I l o i l o<P-
(21)
其中已知l/，求D和X，使得即
\\V-DX\\g/J\
首先，利用1.2中的最小特征值方法，得到关 于样本K的分析字典矩阵II，使得
(22)
其中；f的第；列是V中的第i个样本的系数，由信号稀疏表示分析模型可知，结果X是列 稀疏的.
其次，计算n的伪逆i r，使得f r n v=i/. 从而得到信号稀疏表示的合成模型的分解结果：
(23)其中是稀疏表示合成模型的字典矩阵，I 为稀疏的系数.
具体的算法见算法2-1的S M E M P算法.
算法2-1 SMEMP算法
(1)输入训练样本V，令V, = V;
(2)利用sm e算法，求解分析字典n;
(3)计算n的伪逆(V;
(4)输出字典矩阵IV和稀疏系数// = RY.
2.3合成模型求解算法的收敛性证明
为了证明收敛性，先提出如下引理.
引理2.2给出矩阵，那么，矩阵方程可解，当且仅当这时，方程的解为
X^AtB+(In-A*A)Z.(24)其中Z e/T p为任意矩阵.显然，Z= 是最小范数解.
矩阵方程U= B是可解的，那么，最小二乘 解与公式（24)相同，且;^=，B是最小范数 的最小二乘解.
定理2.2设有样本信号矩阵F e/r x"，则存在信 号稀疏表示的矩阵分解V=Z)X记x")，使得X是列稀疏的.
证明这是一个迭代的证明过程.
对于样本矩阵F e/T M，我们任意构造一个矩 阵的分解1/=/)。夂，这里X。并不满足稀疏性要求.
设X。是算法1-2中的训练数据.对任意给定的随机初始向量〇>#圮，利用分析算子n。，能得 到稀疏矩阵足==1^总，使芩的稀疏度满足我们的 要求.利用引理2.2，我们可得;?。= 0。'，代人 得
V^D^X^D.X,.(25)其中
同样地，得到另一个分析矩阵〇,，使得 ，比X，更稀疏，即
V^D^X^D.X,.(26)经过次迭代后，假定尤满足稀疏度的约束条件，则停止迭代.最后得到
V=Dk Xk .(27)公式（27)就是满足稀疏约束的收敛性结果.
3数值实验
这部分实验主要是验证算法1-2的功能.实验用的环境为：联想，Pentium®双核C P U，内存
2.0G B,W I N7系统，M A T L A B7.0.1 编程软件.
3.1利用S M E算法获取字典和稀疏系数X
25
°0 10 20 30
40Index
50
图1稀疏的系数X 的条形显示（随机选择4个）
0.02°0
Index
图2稀疏的系数A ：的线形显示（随机选择4个)
实验1随机产生一个矩阵K (40,80)，并随机产生 字典0(40,60)的初值.利用算法1-2计算，得到最终 字典D (40,60)，并得到稀疏的系数Z (60,80).为了 显示X 的稀疏性，随机选取了X 中的四列系数显 示如图1.
在实验过程中，把系数的稀疏度参数设置在
20%以内.根据这个实验的结果，长度为60的系
数，非零元素有11个左右.
实验2随机产生一个矩阵1/(50,200)，并随机产 生字典D (50,100)的初值.利用算法1-2计算，得 到字典1>(50,100)，并得到稀疏的系数Z (100,200). 为了显示X 的稀疏性，随机选取了X 中的四个 系数显示，如图2.在这个实验过程中，为了观 察系数的稀疏度的可控性，把系数的稀疏度参数 设置在12%以内.实验的结果表明，长度为100 的系数，非零元素有10个左右，达到了稀疏表示 的目的.
l u 3o e 033-3S J B a .
s J U 3p e 0(u 3-a >
S J B d s
J U 3p e 03;>-3S J B d
c /5
6 4 2 1
8 6 4
.l M
-:0..0.0.(>
o
o o o o o
J S P e 033-a )
S J B d s o
L o c 3p s 03;3-3s .m c l
的
c 3p s 03u -3S J B d
c /3c 3p e 033-3S J B
d 的J U 3p s 03u -3S J B d
c />
26
