基于优化近似l0范数的算法应用于欠定盲分离源信号恢复时,存在算法复杂度较高,恢复精度受步长影响较大的问题,为此,提出了基于径向基函数(RBF)网络的欠定盲分离源信号恢复算法。该算法借助RBF网络进行交替优化,同时引入修正牛顿法对最小化近似l0范数进行求解,避免了传统的近似l0范数重构算法因步长选择不当造成恢复精度较低的缺点。仿真结果表明,与现有的基于平滑l0范数的算法相比,所提方法在保证较高恢复精度的同时复杂度明显降低。
When the algorithms based on optimizing approximated l0 norm are applied to source recovery in underdetermined blind source separation, the complexity is high and the recovery accuracy is greatly affected by the step size. An algorithm for source recovery in underdetermined blind source separation based on radial basis function (RBF) network (SRRBF) was proposed in order to solve these problems. Depending on RBF network, an alternate optimization is performed in the method proposed. Additionally, the approximated l0 norm is optimized by modified Newton method to avoid inaccurate recovery caused by unsuited step size. Simulations verify that computational complexity of SRRBF is dramatically low while the recovery precision is high.
欠定盲分离是在源信号和信道传输参数未知的情况下,仅由传感器接收到的观测信号来恢复源信号的过程,且要求传感器的个数少于源信号的个数. Mohimani等[1]提出了基于平滑l0范数 (SL0, smoothed l0 norm) 的稀疏重构算法,可用于欠定盲分离源信号恢复. Eftekhari等[2]在SL0的基础上提出了稳健SL0(RSL0, robust SL0) 方法,提高了抗噪性能. Vidya等[3]提出了基于径向级联网络的稀疏重构 (RASR, radial basis function cascade network for sparse signal recovery) 算法,提高了重构精度.安澄全等[4]提出了基于混合优化的SL0稀疏重构 (HOSL0, hybrid optimization SL0) 算法,降低了复杂度.上述算法均采用梯度下降法寻找最优解,然而当迭代步长选择不当时,算法的精度较差.
针对现有的算法存在的不足,笔者在径向基函数 (RBF, radial basis function) 网络的基础上,利用反馈回路进行交替优化,同时使用修正的牛顿方向进行迭代,来提高算法的收敛速度和精度.所提出的算法在保证较高恢复精度的同时显著降低了算法的复杂度,与现有算法相比,表现出了良好的恢复性能.
1 欠定盲分离模型盲源分离在没有先验信息的情况下,仅利用观测信号来恢复源信号,其数学表达式为
$ \mathit{\boldsymbol{x}}\left( t \right) = \mathit{\boldsymbol{As}}\left( t \right) $ | (1) |
其中:x(t)=[x1(t), x2(t), …, xM(t)]T为观测信号向量;s(t)=[s1(t), s2(t), …, sN(t)]T为源信号向量;A∈
$ \mathit{\boldsymbol{x}} = \mathit{\boldsymbol{As}} $ | (2) |
其中:x=[x1, x2, …, xM]T为观测向量,s=[s1, s2, …, sN]T为源信号向量.
2 基于RBF网络的源信号恢复 2.1 RBF网络下面介绍两层级联的RBF网络,如图 1所示,Net1由RBF构成,Net2为实现最小均方误差.
常用的RBF为高斯核函数,定义为
$ K\left( {\mathit{\boldsymbol{v}},\mathit{\boldsymbol{v'}}} \right) = \exp \left( { - \frac{{\left\| {\mathit{\boldsymbol{v}} - \mathit{\boldsymbol{v'}}} \right\|_2^2}}{{2{\sigma ^2}}}} \right) $ | (3) |
其中:v、v′为输入数据,σ > 0为自由参数. 图 1中的参数和式 (3) 中的参数在后文中依次介绍.下面引入稀疏恢复模型.原始的稀疏信号恢复模型如下:
$ \min {\left\| \mathit{\boldsymbol{s}} \right\|_{{\ell _0}}}{\rm{subject}} {\rm{to}} \mathit{\boldsymbol{x = As}} $ | (4) |
其中:s为待恢复的信号向量,x为观测向量,A为混合矩阵 (任意2个列向量之间不相关). ‖s‖
根据压缩感知[5]理论可知,式 (4) 属于NP-hard问题.因此需要对式 (4) 做进一步修改使其转化成可优化的问题,一个有效的方法是使用近似
$ \min {F_1}\left( \mathit{\boldsymbol{s}} \right) {\rm{subject}} {\rm{to}} \mathit{\boldsymbol{x = As}} $ | (5) |
其中F1(s)=σ2
在实际应用中,由于受到噪声的干扰,式 (4) 或者式 (5) 中的约束条件x=As不会严格成立,更为合理的约束条件应为‖x-As‖22 < ε,ε为门限值,它与噪声强度有关.因此,图 1中的Net2(最小均方误差) 可以定义为
$ \min \frac{1}{2}\left\| {\mathit{\boldsymbol{x - As}}} \right\|_2^2 $ | (6) |
至此,图 1中的RBF网络已完成定义,输入空间由观测信号、混合矩阵和初始化参数构成.
为了使图 1中RBF网络的输出尽可能收敛至真实的源信号,实行交替优化,即式 (5) 的结果作为式 (6) 的输入,式 (6) 的结果作为式 (5) 的输入,因此在RBF网络中形成一个反馈回路,提高了源信号恢复的精度.
2.2 源信号恢复方法对于Net1的优化,为了避免最速下降法所产生的“锯齿”效应的影响以及步长选取的问题,使用牛顿法进行迭代优化.首先计算F1(s) 的梯度,可得
$ \nabla {F_1}\left( \mathit{\boldsymbol{s}} \right) = {\left[ {\frac{{{s_1}}}{{{\sigma ^2}}}{{\rm{e}}^{ - \frac{{s_1^2}}{{2{\sigma ^2}}}}},\frac{{{s_2}}}{{{\sigma ^2}}}{{\rm{e}}^{ - \frac{{s_2^2}}{{2{\sigma ^2}}}}}, \cdots ,\frac{{{s_N}}}{{{\sigma ^2}}}{{\rm{e}}^{ - \frac{{s_N^2}}{{2{\sigma ^2}}}}}} \right]^{\rm{T}}} $ | (7) |
求出式 (7) 对应的Hessen矩阵:
$ \begin{array}{*{20}{c}} {{\nabla ^2}{F_1}\left( \mathit{\boldsymbol{s}} \right) = }\\ {{\rm{diag}}\left[ {{{\rm{e}}^{ - \frac{{s_1^2}}{{2{\sigma ^2}}}}}\left( {\frac{{{\sigma ^2} - s_1^2}}{{{\sigma ^4}}}} \right),{{\rm{e}}^{ - \frac{{s_2^2}}{{2{\sigma ^2}}}}}\left( {\frac{{{\sigma ^2} - s_2^2}}{{{\sigma ^4}}}} \right), \cdots ,{{\rm{e}}^{ - \frac{{s_N^2}}{{2{\sigma ^2}}}}}\left( {\frac{{{\sigma ^2} - s_N^2}}{{{\sigma ^4}}}} \right)} \right]} \end{array} $ | (8) |
牛顿法和梯度下降法不同之处在于搜索方向的选取,牛顿方向为
$ \mathit{\boldsymbol{d = }} - {\left[ {{\nabla ^2}{F_1}\left( \mathit{\boldsymbol{s}} \right)} \right]^{ - 1}}\nabla {F_1}\left( \mathit{\boldsymbol{s}} \right) $ | (9) |
但牛顿方向不一定是F1(s) 的下降方向,这就可能导致算法失效.
为保证牛顿方向d为F1(s) 的下降方向,要求∇2F1(s) 为正定矩阵,可以简单证明:令D=(∇F1(s))Td=-(∇F1(s))T[∇2F1(s)]-1∇F1(s),要使牛顿方向d为F1(s) 的下降方向,D必须小于0,从而 (∇F1(s))T[∇2F1(s)]-1∇F1(s)>0,这意味着∇2F1(s) 为正定矩阵.
所以,需要对式 (9) 中的矩阵进行修正,使Hessen矩阵∇2F1(s) 成为正定矩阵.修正后的Hessen矩阵为G=∇2F1(s)+V(V∈
$ \mathit{\boldsymbol{V = }}{\rm{diag}}\left[ {\frac{{2s_1^2}}{{{\sigma ^4}}}{{\rm{e}}^{ - \frac{{s_1^2}}{{2{\sigma ^2}}}}},\frac{{2s_2^2}}{{{\sigma ^4}}}{{\rm{e}}^{ - \frac{{s_2^2}}{{2{\sigma ^2}}}}}, \cdots ,\frac{{2s_N^2}}{{{\sigma ^4}}}{{\rm{e}}^{ - \frac{{s_N^2}}{{2{\sigma ^2}}}}}} \right] $ | (10) |
进一步可以得到
$ \mathit{\boldsymbol{G}} = {\rm{diag}}\left[ {\frac{{{\sigma ^2} + s_1^2}}{{{\sigma ^4}}}{{\rm{e}}^{ - \frac{{s_1^2}}{{2{\sigma ^2}}}}},\frac{{{\sigma ^2} + s_2^2}}{{{\sigma ^4}}}{{\rm{e}}^{ - \frac{{s_2^2}}{{2{\sigma ^2}}}}}, \cdots ,\frac{{{\sigma ^2} + s_N^2}}{{{\sigma ^4}}}{{\rm{e}}^{ - \frac{{s_N^2}}{{2{\sigma ^2}}}}}} \right] $ | (11) |
显然,矩阵G中的对角元素全部满足恒大于0,符合正定矩阵的条件.根据上面得到的修正的Hessen矩阵以及牛顿方程公式,可以求得修正后的牛顿方向:
$ \begin{array}{*{20}{c}} {\mathit{\boldsymbol{d = }} - {\mathit{\boldsymbol{G}}^{ - 1}}\nabla {F_1}\left( \mathit{\boldsymbol{s}} \right) = }\\ {{{\left[ { - \frac{{{\sigma ^2}{s_1}}}{{{\sigma ^2} + s_1^2}}, - \frac{{{\sigma ^2}{s_2}}}{{{\sigma ^2} + s_2^2}}, \cdots ,\frac{{{\sigma ^2}{s_N}}}{{{\sigma ^2} + s_N^2}}} \right]}^{\rm{T}}}} \end{array} $ | (12) |
利用修正后的牛顿方向作为算法的迭代方向,可以得到估计信号由第k次到第k+1次迭代的递推公式为
$ {\mathit{\boldsymbol{s}}_{k + 1}} = {\mathit{\boldsymbol{s}}_k} + {\mathit{\boldsymbol{d}}_k} $ | (13) |
其中dk=
对于Net2的优化,由于式 (6) 中的目标函数的Hessen矩阵不是对角阵,在进行矩阵求逆时计算较为复杂且精度很难保证,因此采用文献[3]中的迭代方法求解式 (6),迭代公式为
$ {\mathit{\boldsymbol{s}}_{k + 1}} = {\mathit{\boldsymbol{s}}_k} + {\mu _j}\mathit{\boldsymbol{A}}_j^{\rm{T}}\left( {{x_j} - {\mathit{\boldsymbol{A}}_j}{\mathit{\boldsymbol{s}}_k}} \right), j = 1,2, \cdots ,M $ | (14) |
其中:μj=1/‖Aj‖2为迭代步长,Aj为A的第j行.具体的推导过程可参考文献[3],这里不再重复推导.
经过上述分析,使用式 (13) 和式 (14) 进行交替优化,即可在Net1和Net2之间形成反馈回路,使得RBF网络的输出尽可能收敛至真实的源信号.输入空间中的参数初始化如下:sk的初始值为s0=AT(AAT)-1x,δ为小于1的尺度参数,在仿真实验中取值为0.6,用于更新σ. σ为式 (3) 中的自由参数,当取值较小时,Net1中的F1(s) 越能够逼近向量s的
综上所述,基于RBF网络的欠定盲分离源信号恢复算法流程如下:
步骤1 初始化估计信号s0=AT(AAT)-1x,尺度参数δ=0.6,σ0=2max{s0},σmin=10-5,迭代次数k=0.
步骤2 当σk > σmin时,执行步骤3至步骤6.
步骤3 根据式 (12) 求出牛顿方向dk.
步骤4 根据式 (13),更新sk:sk←sk+dk.
步骤5 对于j=1, 2, …, M(M为观测信号个数),执行1)、2):
1) αk=(xj-Ajsk)/‖Aj‖2,其中Aj为A的第j行;
2) 更新sk:sk←sk+αkAj.
步骤6 σk+1=δσk,sk+1=sk,更新k:k←k+1.
步骤7 输出sk.
3 算法的收敛性和复杂度分析根据文献[6],迭代产生的源信号序列{sk}所循的路径呈现出“锯齿现象”,影响收敛速度.当Hessen矩阵∇2F1(s) 条件数很大时,“锯齿现象”尤为严重.但是基于RBF网络的欠定盲分离源信号恢复 (SRRBF, source recovery in underdetermined blind source separation based on RBF network) 算法中所引入的牛顿法可以快速收敛,下面说明对Net1中F1(s) 的优化可以实现至少2级收敛.根据文献[6],有如下定理.
定理 设f(s) 为二次连续可微函数,
$ \left\| {{\nabla ^2}f{{\left( {\mathit{\boldsymbol{\bar s}}} \right)}^{ - 1}}} \right\| \le {k_1} $ | (15) |
$ \frac{{\left\| {\nabla f\left( {\mathit{\boldsymbol{\bar s}}} \right) - \nabla f\left( \mathit{\boldsymbol{s}} \right) - {\nabla ^2}f\left( \mathit{\boldsymbol{s}} \right)\left( {\mathit{\boldsymbol{\bar s}} - \mathit{\boldsymbol{s}}} \right)} \right\|}}{{\left\| {\mathit{\boldsymbol{\bar s}} - \mathit{\boldsymbol{s}}} \right\|}} \le {k_2} $ | (16) |
则牛顿法产生的序列收敛于
在Net1中F1(s) 达到最优解的极值条件为
$ \left\| {{\mathit{\boldsymbol{G}}^{ - 1}}} \right\| \le {{k'}_1} $ | (17) |
$ \frac{{\left\| {\nabla {F_1}\left( {\mathit{\boldsymbol{\bar s}}} \right) - \nabla f\left( \mathit{\boldsymbol{s}} \right) - \mathit{\boldsymbol{G}}\left( {\mathit{\boldsymbol{\bar s}} - \mathit{\boldsymbol{s}}} \right)} \right\|}}{{\left\| {\mathit{\boldsymbol{\bar s}} - \mathit{\boldsymbol{s}}} \right\|}} \le {{k'}_2} $ | (18) |
其中k′1, k′2>0,k′1k′2 < 1.当sk∈S,sk≠
$ \begin{array}{*{20}{c}} {{\mathit{\boldsymbol{s}}_{k + 1}} - \mathit{\boldsymbol{\bar s}} = {\mathit{\boldsymbol{s}}_k} - {\mathit{\boldsymbol{G}}^{ - 1}}\nabla {F_1}\left( {{\mathit{\boldsymbol{s}}_k}} \right) - \mathit{\boldsymbol{\bar s}} = }\\ {\left( {{\mathit{\boldsymbol{s}}_k} - \mathit{\boldsymbol{\bar s}}} \right) - {\mathit{\boldsymbol{G}}^{ - 1}}\left[ {\nabla {F_1}\left( {{\mathit{\boldsymbol{s}}_k}} \right) - \nabla {F_1}\left( {\mathit{\boldsymbol{\bar s}}} \right)} \right] = }\\ {{\mathit{\boldsymbol{G}}^{ - 1}}\left[ {\nabla {F_1}\left( {\mathit{\boldsymbol{\bar s}}} \right) - \nabla {F_1}\left( {{\mathit{\boldsymbol{s}}_k}} \right) - \mathit{\boldsymbol{G}}\left( {\mathit{\boldsymbol{\bar s}} - {\mathit{\boldsymbol{s}}_k}} \right)} \right]} \end{array} $ | (19) |
再考虑到式 (17) 和式 (18),有
$ \begin{array}{*{20}{c}} {\left\| {{\mathit{\boldsymbol{s}}_{k + 1}} - \mathit{\boldsymbol{\bar s}}} \right\| \le }\\ {\left\| {{\mathit{\boldsymbol{G}}^{ - 1}}} \right\|\left\| {\nabla {F_1}\left( {\mathit{\boldsymbol{\bar s}}} \right) - \nabla {F_1}\left( {{\mathit{\boldsymbol{s}}_k}} \right) - \mathit{\boldsymbol{G}}\left( {\mathit{\boldsymbol{\bar s}} - {\mathit{\boldsymbol{s}}_k}} \right)} \right\| \le }\\ {{{k'}_1}{{k'}_2}\left\| {{\mathit{\boldsymbol{s}}_k} - \mathit{\boldsymbol{\bar s}}} \right\| < \left\| {{\mathit{\boldsymbol{s}}_k} - \mathit{\boldsymbol{\bar s}}} \right\|} \end{array} $ | (20) |
因此,sk+1比sk更接近于
$ \left\| {{\mathit{\boldsymbol{s}}_{k + 1}} - \mathit{\boldsymbol{\bar s}}} \right\| \le c{\left\| {{\mathit{\boldsymbol{s}}_k} - \mathit{\boldsymbol{\bar s}}} \right\|^2} $ | (21) |
其中:
对于SRRBF算法而言,计算复杂度主要来源于式 (13)、式 (14) 以及步骤5,因此,若算法迭代次数为L1,加法和乘法的次数分别约为L1[2N+(3T)M]和L1[4N+(3T+1)M].对于RASR算法,计算复杂度主要来自于梯度的计算和迭代点的更新,若迭代次数为L2,则加法和乘法的次数分别约为L2[2T-1+(3T)M]和L2[T+1+(3T+1)M].一般而言,源信号数目N远小于采样点数目T,由于修正的牛顿法收敛速度更快,使得
为了比较提出的SRRBF算法与现有的基于
$ {\gamma _{{\rm{coef}}}}\left( {\mathit{\boldsymbol{\hat S}},\mathit{\boldsymbol{S}}} \right) = \frac{1}{N}\sum\limits_{n = 1}^N {\frac{{\left| {\sum\limits_{t = 1}^T {s\left( {n,t} \right)\hat s\left( {n,t} \right)} } \right|}}{{\sqrt {\sum\limits_{t = 1}^T {{s^2}\left( {n,t} \right)} \sum\limits_{t = 1}^N {{{\hat s}^2}\left( {n,t} \right)} } }}} $ | (22) |
其中:S为估计得到的源信号,
根据图 2可知,在稀疏度为0.8的情况下,在信噪比从10~30 dB变化范围内,SRRBF算法的相关系数均大于其他4种算法.比如,在10 dB的情况下,SRRBF算法的相关系数分别比SL0、RSL0、RASR、HOSL0算法高出了约2.13%、2.49%、1.20%、1.62%.
由图 3可得,在稀疏度为0.8的情况下,在信噪比从10~30 dB变化范围内,SRRBF算法的运算时间小于其他4种算法.比如,在10 dB的情况下,SRRBF算法运行时间分别比SL0、RSL0、RASR、HOSL0算法降低了约36.82%、48.83%、42.85%、62.92%.
图 4给出了信噪比为10 dB情况下5种算法相关系数随稀疏度变化的曲线.由图 4可以看出,当稀疏度小于0.55时,SRRBF算法的相关系数大于SL0、RSL0、HOSL0算法,略微小于RASR算法.例如,稀疏度为0.5的情况下,SRRBF算法的相关系数比RASR算法减小了约0.1%,而比SL0、RSL0、HOSL0算法分别提高了约0.4%、0.7%、4.3%.当稀疏度大于0.55时,SRRBF算法的相关系数均大于其他4种算法.
由图 5可以看出,SRRBF算法的运算复杂度显著小于其他4种算法.比如,在稀疏度为0.5的条件下,SRRBF算法比SL0、RSL0、RASR、HOSL0算法的运行时间分别降低了约40.75%、54.88%、46.82%、63.03%.
根据以上的仿真结果及分析可以得出:1) 在信号稀疏度较小的情况下,与RASR算法相比,SRRBF算法以牺牲极小的精度作为代价,节约了大量的运算时间,即同时兼顾了复杂度和精度;2) 在源信号稀疏度较大的情况下,SRRBF算法在复杂度和精度方面均优于SL0、RSL0、RASR、HOSL0算法.
5 结束语针对现有的基于优化近似
[1] | Mohimani H, Babaie-Zadeh M, Jutten C. A fast approach for overcomplete sparse decomposition based on smoothed l0 norm[J]. IEEE Transactions on Signal Processing, 2009, 57(1): 289–301. doi: 10.1109/TSP.2008.2007606 |
[2] | Eftekhari A, Bubaie M, Jutten C, et al. Robust-SL0 for stable sparse representation in noisy settings [C]//20th International Conference on Acoustics, Speech and Signal Processing (ICASSP, 2009). Taipei:IEEE press, 2009:3433-3436. |
[3] | Vidya L, Vivekanand V, Shyamkumar U, et al. RBF-network based sparse signal recovery algorithm for compressed sensing reconstruction[J]. Neural Networks, 2015, 63(3): 66–78. |
[4] |
安澄全, 彭军伟. 基于混合优化的平滑L0压缩感知重构算法[J]. 应用科技, 2013, 40(5): 23–28.
An Chengquan, Peng Junwei. Sparse recovery using smoothed L0 based on hybrid optimization algorithm[J]. Applied Science and Technology, 2013, 40(5): 23–28. |
[5] | Candès E J, Wakin M B. An introduction to compressive sampling[J]. IEEE Signal Processing Magazine, 2008, 25(2): 21–30. doi: 10.1109/MSP.2007.914731 |
[6] | 陈宝林. 最优化理论与算法[M]. 北京: 清华大学出版社, 2005: 286-291. |