论文部分内容阅读
摘要：为降低块稀疏最小均方算法（BS-NLMS）在声学回波消除等系统辨识中的计算复杂度，本文充分研究了块稀疏系统特性，提出一种利用语音活动检测方法来降低原有算法计算复杂度的改进型新算法。新算法首先利用基于高阶统计量的语音活动检测法来区分一段语音中的有无语音段，然后采用最小欧式距离范数作为部分更新标准，从而克服了传统抽头系数在每次迭代时需要全部更新而引起的较高计算复杂度的问题。本文不仅给出了算法的计算复杂度分析，系统辨识的仿真结果也表明本方法较之前的块稀疏最小均方算法有更小的计算复杂度。
关键词：高阶统计量；块稀疏；部分更新；系统辨识
中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2018）13-0195-03
Improved Block-Sparse Least Mean Square Algorithm Based on Higher Order Statistics
WEI Dan-dan ， LIU Bin-cen
（College of Information Engineering， Zunyi Normal University， Zunyi 563006， China）
Abstract： In order to reduce computations of block sparse system identification，a selective partial-update normalization adaptive filtering algorithm based on the BS-NLMS algorithm is proposed of block sparse system identification in acoustic echo cancellation application. the Voice activity detection （VAD） algorithm is used to distinguish the active/inactive speech periods. the selective block updating schemes of smallest Euclidean distance is chosen to update filter coefficients at each iteration. Computational complexity is analyzed in detail. Additionally， simulations results show that the proposed algorithm performance in terms of convergence rate and steady-state mean square error as compared with the BS-NLMS algorithm.
Key words： adaptive filtering algorithm； block sparse； selective partial-update； system identification
1引言
無论在计算机领域的多媒体信号处理还是通信领域的系统辨识和声学回声消除等，自适应滤波算法都有着广阔的前景应用[1]。其中最为常用的是最小二乘 （Recursive Least Square， RLS） 法、最小均方（Least Mean Square， LMS）算法以及仿射投影算法（Affine Projection Algorithm， APA）等三种算法。其中，应用最为广泛的是具有计算量小和易于实现这两个优点的LMS算法。需要注意的是，仅仅是LMS算法不足以满足很多实际的工程应用，因为大部分未知系统下的权重系数是具有显著稀疏性的 ，以最为典型的声学回声信道模型为例，其冲激响应的权重系数成百上千而大部分都是零系数，该模型也称为单聚类稀疏系统或者是块稀疏信道。对于这种情况下的系统，单一的LMS算法显然不符合需求，我们需要将稀疏这个条件提前考虑，并将其作为先验知识加入算法的更新当中，通过插入[l（2.0）]范数的方法，去提高算法的收敛速度及稳态误差，这里引入了一个新的名词，即惩罚因子，其含义是把冲激响应分成相同的长度，然后取其混合2范数即可。最后就可以得到块稀疏归一化最小均方（Block Sparse-Normalization Least Mean Square ，BS-NLMS）算法了。该算法有一个明显不足之处，整个算法推到都只考虑了服从高斯分布的干扰噪声，而对于非高斯噪声这种情况，块稀疏最小均方滤波算法不具有抗冲击噪声的干扰性能。
BS-NLMS算法的快速收敛性能是以牺牲自身的计算复杂度为代价获得的，因此，如何在保证算法收敛速度的基础上同时降低算法复杂度便成了BS-NLMS算法的重要问题之一。 本论文拟通过采用部分更新技术来降低每次迭代过程中的计算复杂度。部分更新技术是自适应滤波算法用来降低计算复杂度的一种有效方法，且可移植性高。典型算法包括预先确定更新策略而不需要额外操作来确定系数的序列NLMS算法[4]，M-max NLMS算法[5]，以及采取固定更新方案来更新滤波器系数的set-membership PU-NLMS算法等[6]. 本论文选取最小均方欧式距离作为最优准则来选取部分更新块以降低计算复杂度。通常来说，选取准则大致可以分为两类，第一类是块系数矢量更新采用均方欧式范数，第二类是在参数设置时采用较大的梯度矢量成分。计算复杂度的降低是通过将抽头系数分为较小的块且每次只迭代一块而不是整个滤波器系数获得的。而在具体的块选择上则是得益于声学回波消除中很重要的一种VAD技术，而本文采用的是其中的高阶统计量方法。 2 进的 BS-NLMS自适应滤波算法
本文基于如图1所示系统辨识模型来对算法进行分析[9]，假设框图上半部分的自适应未知系统是[s（n）=[s0（n），s1（n），...，sL-1（n）]T]，而自适应滤波器的第[n]次迭代输入信号[u（n）=[u（n），u（n-1），...，u（n-L 1）]T]，抽头长度表示为L，滤波器的未知系统期望信号输出[d（n）]表示为[d（n）=uT（n）s（n） v（n）]，环境噪声[v（n）]服从零均值、方差为[σ2]的高斯分布。根据上述假设，则第[n]次的迭代估计误差可表示为[e（n）=d（n）-xT（n）w（n）]的形式，其中，式子中的[w（n）]表示抽头系数，含义是该自适应滤波器对未知的目标系统模型[s]的估计。
块稀疏自适应滤波算法的代价函数可用如下的方程式子来表示：[ξ（n）=e（n）2 λw（n）2，0]，其中，参数[λ]是一个正因子，另一参数可表示为：
[w2，0=Δ w12 w22… wN2T0]
式中，[w[i]=[w（i-1）P 1，w（i-1）P 1，...，wiP]T]表示第[i]组的滤波器系数，其中的[P]表示滤波器阶数分了多少组数，而[N]则表示滤波器阶数分组的长度是多少。最后利用最陡下降法，可以得到下式中的权重系数更新公式：
[w（n 1）=w（n） μe（n）u（n）u（n）u（n）T ε κgw（n）]
式中的[g（w）]可进一步写成如下方式
[g（w）=Δ[g1w，g2w，…，gLw]T]
而[μ]是一个用于调整误差和收敛速度的步长参数，小的正常数[ε]是为了避免发生除零操作而引入的，[κ=μλ/2]，[α]在此处必然是一个正常数。
[gj（w）=Δ2α2wj-2αwjwj/p， 0 利用语音信号的高阶统计量（Higher-order Statistics，HOS）作为主要语音检测指标的VAD算法是一种能够有效地将目标语音从服从高斯分布的语音噪声中区分出来的有效方案。其中，高阶统计量在此处的含义是指三阶以及三阶以上统计量的随机变量或者说是随机过程的统计量。对于一组随机信号[x1，x2，…，xn]，它们的[r]阶联合统计量可以定义为如下形式：
式中：[φ（ω1，ω2，…ωn）=Eexpj（ω1x1 ω2x2 … ωnxn）]表示信号[x1，x2，…，xn]的联合特征函数。而 对于[k]阶矩存在的平稳随机过程[x（k）]，其各阶统计量在不同延遲下的定义如下所示：
一阶统计量：[C1x=E[x（n）]]
二阶统计量为：[C2x（τ1）=E[x（n）x（n τ1）]]
对实信号[y（n）]而言，在均值为零，时间延迟[t1=t2=t3=0]的情况下，可分别得到如下二、三、四阶统计量的三个特殊切片：
方差（variance）：[γ2y=C2y（0）=E[y2（n）]=σ2]
斜度（skewness）：[γ3y=C3y（0，0）=E[y3（n）]]
峰度（kurtosis）：[γ4y=C4y（0，0，0）]
[=E[y4（n）]-3γ2y=E[y4（n）]-3σ2]
3 部分更新的SPU-BS-NLMS算法
SPU-BS-NLMS算法在每次迭代中基于块选择准则只更新一部分滤波器系数来降低BS-NLMS算法的计算复杂度。假设L能够被P和C整除，因为不同于文献[7][8][9]等其他传统算法，BS-NLMS算法已经假设滤波系数被分成了相同长度的组数。C表示滤波器系数块的数目，B表示块系数长度。系数矢量以及输入信号矢量如下所示：
[u（n）=[uT1（n）uT2（n）...uTC（n）]]
[w（n）=[wT1（n）wT2（n）...wTC（n）]]
[w1（n）=[w1（n）...wB-1（n）]] [u1（n）=[u1（n）...uB-1（n）]]
将某个更新块记作[i]， SPU-BS-NLMS算法能够通过最优准则获得，即误差矢量的最小l{2，0}范数。
[min||wi（k 1）-wi（k）||2，0]
[Subject to d（n）=wT（n 1）u（n）]
通过用拉格朗日乘法器，可得如下所示代价函数：
[xi（n 1）=E[e（n）]-βkwi（n 1） κgwi（n）]
其中，[β]是拉格朗日乘法系数。对代价函数求偏导使权重系数为零，可得权重系数更新方程。第[i]个块是预先设定的。然后，其值是不知道，方法是通过获取最小的欧式距离[kwi（n 1）-wi（n）]，得到输入样本的最大幅值。因此，修改部分更新块稀疏公式如下。[w（n 1）=w（n） S（n）e（n）u κgwi（n）]，其中[S（n）=diag（s1（n），s2（n），...，sc（n））]Si（n）等于0，其它为0。
就计算复杂度而言，M代表整个滤波器的长度，P在第二部分定义过，B代表更新块长度。每一次迭代就比较几种运算，加法运算，乘法运算，除法运算，平方根运算和比较运算。其中，NLMS算法需要2M 2次乘法，2M 2次加法，1次除法， 0次平方根和0次比较。BS-NLMS算法需2M 2次乘法， 4M 2次加法，1 M/P次除法 ， M/P次平方根和M/P次比较。SPU-BS-NLMS算法需要M/B M 2次乘法，3M/B M 2次加法，M/PB 1次除法，M/P次平方根和M/PB次比较。本文提出的新算法减少了O（2L 6M） 次的计算量。就当前发展而言，能够以不降低算法的跟踪性能为代价而降低算法的计算复杂度是十分重要的。 4 結论
本文提出的部分更新块稀疏自适应滤波算法能够降低算法的计算复杂度，该算法首先利用基于高阶统计量的语音活动检测法区分有无语音段，然后采用最小欧式距离范数作为更新标准，从而克服了传统抽头系数在每次迭代时需要全部更新而导致的计算复杂度的问题。文中给出了算法的计算复杂度分析。进一步的研究方向将会从块稀疏的分块来研究，考虑如何进行分块的自适应，而不是固定的分配。
参考文献：
[1] HAYKIN S. Adaptive filter theory[M]. India：Pearson Education India， 2008： 120-180.
[2] Zhang Jian；Chen Xiaowei.Non-subsampled cont- JIANG S， GU Y T. Block-sparsity-induced adaptive filter for multi- clustering system identification [J].IEEE Transactions on Signal Processing. 2015，62（20）， 5318-5330.
[3] LIU J， GRANT S L. Proportionate adaptive filtering for block-sparse system[J]. IEEE/ACM Transactions on Audio， Speech， and Languange Processing， 2016， 24（4）， 623-630.
[4]S. C. Douglas， Adaptive filters employing partial updates， IEEE Transactions on Circuits and Systems II： Analog and Digital Signal Processing，44（3）：209-216，1997.
[5] T. Aboulnasr， K. Mayyas， Complexity reduction of the NLMS algorithm via selective coefficient update， IEEE Transactions on Signal Processing，47（5）：1421-1424，1999.
[6] S. Werner， MLR. De. Campos， and PSR. Diniz， Partial-update NLMS algorithms with data-selective updating， IEEE Transactions on Signal Processing， 52（4）： 938-949， 2004.
[7] P. Loganathan， EAP. Habets， and P. A. Naylor， A proportionate adaptive algorithm with variable partitioned block length for acoustic echo cancellation， 2011 IEEE International Conference on， pp.73-76，IEEE（2011）.
[8] M. Godavarti， A. O. Hero， Partial update LMS algorithms， IEEE Transactions on Signal Processing， 53（7）： 2382-2399， 2005.
[9] T. Schertler. Selective block update of NLMS type algorithms， 1998 IEEE International Conference on， pp： 1717-1720， IEEE（1998）.
关键词：高阶统计量；块稀疏；部分更新；系统辨识
中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2018）13-0195-03
Improved Block-Sparse Least Mean Square Algorithm Based on Higher Order Statistics
WEI Dan-dan ， LIU Bin-cen
（College of Information Engineering， Zunyi Normal University， Zunyi 563006， China）
Abstract： In order to reduce computations of block sparse system identification，a selective partial-update normalization adaptive filtering algorithm based on the BS-NLMS algorithm is proposed of block sparse system identification in acoustic echo cancellation application. the Voice activity detection （VAD） algorithm is used to distinguish the active/inactive speech periods. the selective block updating schemes of smallest Euclidean distance is chosen to update filter coefficients at each iteration. Computational complexity is analyzed in detail. Additionally， simulations results show that the proposed algorithm performance in terms of convergence rate and steady-state mean square error as compared with the BS-NLMS algorithm.
Key words： adaptive filtering algorithm； block sparse； selective partial-update； system identification
1引言
無论在计算机领域的多媒体信号处理还是通信领域的系统辨识和声学回声消除等，自适应滤波算法都有着广阔的前景应用[1]。其中最为常用的是最小二乘 （Recursive Least Square， RLS） 法、最小均方（Least Mean Square， LMS）算法以及仿射投影算法（Affine Projection Algorithm， APA）等三种算法。其中，应用最为广泛的是具有计算量小和易于实现这两个优点的LMS算法。需要注意的是，仅仅是LMS算法不足以满足很多实际的工程应用，因为大部分未知系统下的权重系数是具有显著稀疏性的 ，以最为典型的声学回声信道模型为例，其冲激响应的权重系数成百上千而大部分都是零系数，该模型也称为单聚类稀疏系统或者是块稀疏信道。对于这种情况下的系统，单一的LMS算法显然不符合需求，我们需要将稀疏这个条件提前考虑，并将其作为先验知识加入算法的更新当中，通过插入[l（2.0）]范数的方法，去提高算法的收敛速度及稳态误差，这里引入了一个新的名词，即惩罚因子，其含义是把冲激响应分成相同的长度，然后取其混合2范数即可。最后就可以得到块稀疏归一化最小均方（Block Sparse-Normalization Least Mean Square ，BS-NLMS）算法了。该算法有一个明显不足之处，整个算法推到都只考虑了服从高斯分布的干扰噪声，而对于非高斯噪声这种情况，块稀疏最小均方滤波算法不具有抗冲击噪声的干扰性能。
BS-NLMS算法的快速收敛性能是以牺牲自身的计算复杂度为代价获得的，因此，如何在保证算法收敛速度的基础上同时降低算法复杂度便成了BS-NLMS算法的重要问题之一。 本论文拟通过采用部分更新技术来降低每次迭代过程中的计算复杂度。部分更新技术是自适应滤波算法用来降低计算复杂度的一种有效方法，且可移植性高。典型算法包括预先确定更新策略而不需要额外操作来确定系数的序列NLMS算法[4]，M-max NLMS算法[5]，以及采取固定更新方案来更新滤波器系数的set-membership PU-NLMS算法等[6]. 本论文选取最小均方欧式距离作为最优准则来选取部分更新块以降低计算复杂度。通常来说，选取准则大致可以分为两类，第一类是块系数矢量更新采用均方欧式范数，第二类是在参数设置时采用较大的梯度矢量成分。计算复杂度的降低是通过将抽头系数分为较小的块且每次只迭代一块而不是整个滤波器系数获得的。而在具体的块选择上则是得益于声学回波消除中很重要的一种VAD技术，而本文采用的是其中的高阶统计量方法。 2 进的 BS-NLMS自适应滤波算法
本文基于如图1所示系统辨识模型来对算法进行分析[9]，假设框图上半部分的自适应未知系统是[s（n）=[s0（n），s1（n），...，sL-1（n）]T]，而自适应滤波器的第[n]次迭代输入信号[u（n）=[u（n），u（n-1），...，u（n-L 1）]T]，抽头长度表示为L，滤波器的未知系统期望信号输出[d（n）]表示为[d（n）=uT（n）s（n） v（n）]，环境噪声[v（n）]服从零均值、方差为[σ2]的高斯分布。根据上述假设，则第[n]次的迭代估计误差可表示为[e（n）=d（n）-xT（n）w（n）]的形式，其中，式子中的[w（n）]表示抽头系数，含义是该自适应滤波器对未知的目标系统模型[s]的估计。
块稀疏自适应滤波算法的代价函数可用如下的方程式子来表示：[ξ（n）=e（n）2 λw（n）2，0]，其中，参数[λ]是一个正因子，另一参数可表示为：
[w2，0=Δ w12 w22… wN2T0]
式中，[w[i]=[w（i-1）P 1，w（i-1）P 1，...，wiP]T]表示第[i]组的滤波器系数，其中的[P]表示滤波器阶数分了多少组数，而[N]则表示滤波器阶数分组的长度是多少。最后利用最陡下降法，可以得到下式中的权重系数更新公式：
[w（n 1）=w（n） μe（n）u（n）u（n）u（n）T ε κgw（n）]
式中的[g（w）]可进一步写成如下方式
[g（w）=Δ[g1w，g2w，…，gLw]T]
而[μ]是一个用于调整误差和收敛速度的步长参数，小的正常数[ε]是为了避免发生除零操作而引入的，[κ=μλ/2]，[α]在此处必然是一个正常数。
[gj（w）=Δ2α2wj-2αwjwj/p， 0
式中：[φ（ω1，ω2，…ωn）=Eexpj（ω1x1 ω2x2 … ωnxn）]表示信号[x1，x2，…，xn]的联合特征函数。而 对于[k]阶矩存在的平稳随机过程[x（k）]，其各阶统计量在不同延遲下的定义如下所示：
一阶统计量：[C1x=E[x（n）]]
二阶统计量为：[C2x（τ1）=E[x（n）x（n τ1）]]
对实信号[y（n）]而言，在均值为零，时间延迟[t1=t2=t3=0]的情况下，可分别得到如下二、三、四阶统计量的三个特殊切片：
方差（variance）：[γ2y=C2y（0）=E[y2（n）]=σ2]
斜度（skewness）：[γ3y=C3y（0，0）=E[y3（n）]]
峰度（kurtosis）：[γ4y=C4y（0，0，0）]
[=E[y4（n）]-3γ2y=E[y4（n）]-3σ2]
3 部分更新的SPU-BS-NLMS算法
SPU-BS-NLMS算法在每次迭代中基于块选择准则只更新一部分滤波器系数来降低BS-NLMS算法的计算复杂度。假设L能够被P和C整除，因为不同于文献[7][8][9]等其他传统算法，BS-NLMS算法已经假设滤波系数被分成了相同长度的组数。C表示滤波器系数块的数目，B表示块系数长度。系数矢量以及输入信号矢量如下所示：
[u（n）=[uT1（n）uT2（n）...uTC（n）]]
[w（n）=[wT1（n）wT2（n）...wTC（n）]]
[w1（n）=[w1（n）...wB-1（n）]] [u1（n）=[u1（n）...uB-1（n）]]
将某个更新块记作[i]， SPU-BS-NLMS算法能够通过最优准则获得，即误差矢量的最小l{2，0}范数。
[min||wi（k 1）-wi（k）||2，0]
[Subject to d（n）=wT（n 1）u（n）]
通过用拉格朗日乘法器，可得如下所示代价函数：
[xi（n 1）=E[e（n）]-βkwi（n 1） κgwi（n）]
其中，[β]是拉格朗日乘法系数。对代价函数求偏导使权重系数为零，可得权重系数更新方程。第[i]个块是预先设定的。然后，其值是不知道，方法是通过获取最小的欧式距离[kwi（n 1）-wi（n）]，得到输入样本的最大幅值。因此，修改部分更新块稀疏公式如下。[w（n 1）=w（n） S（n）e（n）u κgwi（n）]，其中[S（n）=diag（s1（n），s2（n），...，sc（n））]Si（n）等于0，其它为0。
就计算复杂度而言，M代表整个滤波器的长度，P在第二部分定义过，B代表更新块长度。每一次迭代就比较几种运算，加法运算，乘法运算，除法运算，平方根运算和比较运算。其中，NLMS算法需要2M 2次乘法，2M 2次加法，1次除法， 0次平方根和0次比较。BS-NLMS算法需2M 2次乘法， 4M 2次加法，1 M/P次除法 ， M/P次平方根和M/P次比较。SPU-BS-NLMS算法需要M/B M 2次乘法，3M/B M 2次加法，M/PB 1次除法，M/P次平方根和M/PB次比较。本文提出的新算法减少了O（2L 6M） 次的计算量。就当前发展而言，能够以不降低算法的跟踪性能为代价而降低算法的计算复杂度是十分重要的。 4 結论
本文提出的部分更新块稀疏自适应滤波算法能够降低算法的计算复杂度，该算法首先利用基于高阶统计量的语音活动检测法区分有无语音段，然后采用最小欧式距离范数作为更新标准，从而克服了传统抽头系数在每次迭代时需要全部更新而导致的计算复杂度的问题。文中给出了算法的计算复杂度分析。进一步的研究方向将会从块稀疏的分块来研究，考虑如何进行分块的自适应，而不是固定的分配。
参考文献：
[1] HAYKIN S. Adaptive filter theory[M]. India：Pearson Education India， 2008： 120-180.
[2] Zhang Jian；Chen Xiaowei.Non-subsampled cont- JIANG S， GU Y T. Block-sparsity-induced adaptive filter for multi- clustering system identification [J].IEEE Transactions on Signal Processing. 2015，62（20）， 5318-5330.
[3] LIU J， GRANT S L. Proportionate adaptive filtering for block-sparse system[J]. IEEE/ACM Transactions on Audio， Speech， and Languange Processing， 2016， 24（4）， 623-630.
[4]S. C. Douglas， Adaptive filters employing partial updates， IEEE Transactions on Circuits and Systems II： Analog and Digital Signal Processing，44（3）：209-216，1997.
[5] T. Aboulnasr， K. Mayyas， Complexity reduction of the NLMS algorithm via selective coefficient update， IEEE Transactions on Signal Processing，47（5）：1421-1424，1999.
[6] S. Werner， MLR. De. Campos， and PSR. Diniz， Partial-update NLMS algorithms with data-selective updating， IEEE Transactions on Signal Processing， 52（4）： 938-949， 2004.
[7] P. Loganathan， EAP. Habets， and P. A. Naylor， A proportionate adaptive algorithm with variable partitioned block length for acoustic echo cancellation， 2011 IEEE International Conference on， pp.73-76，IEEE（2011）.
[8] M. Godavarti， A. O. Hero， Partial update LMS algorithms， IEEE Transactions on Signal Processing， 53（7）： 2382-2399， 2005.
[9] T. Schertler. Selective block update of NLMS type algorithms， 1998 IEEE International Conference on， pp： 1717-1720， IEEE（1998）.