基于改进l1范数最小化组合算法的欠定盲源分离.doc

第7期 基于改进l1范数最小化组合算法的欠定盲源分离 · 5 ·
更多电子资料请登录赛微电子网
基于改进l1范数最小化组合算法的欠定盲源分离
付 宁 彭喜元
(哈尔滨工业大学自动化测试与控制系, 哈尔滨 150080)
摘 要: 基于稀疏假设, 欠定盲源分离问题一般可采用线性规划、最短路径法和组合算法等l1范数最小化方法进行求解, 但是这些传统方法对源信号的稀疏性要求较高, 从而限制了源信号的估计精度。为此, 本文提出了一种改进的l1范数最小化组合算法. 该算法根据一定阈值找到与最小l1范数解最接近的若干次优解, 将这些次优解和最小l1范数解进行加权叠加, 并替代最小l1范数解 作为源信号的估计。采用语音信号的仿真实验表明, 对于观测信号个数不太小的高维混合情况, 该算法的源信号估计精度能够比传统的l1范数最小化组合算法提高10%左右。
关键词: 欠定盲源分离；稀疏信号； l1范数最小化；线性规划
中图分类号: TN911　　　文献标识码: A　　　国家标准学科分类代码: 510.40
Underdetermined blind source separation based on improved combinatorial algorithm for l1-norm minimization
Fu Ning Peng Xiyuan
(Dept. of Automatic Test and Control, Harbin Institute of Technology, Harbin 150080, China)
Abstract: Under the sparse assumption, the problem of underdetermined blind source separation can be solved by l1-norm minimization algorithms such as the linear programming, the shortest-path algorithm, the combinatorial algorithm and so on. But these conventional algorithms rely on the high sparseness of the sources, so the recovery accuracy of the sources is not high enough. To overcome this disadvantage, an improved combinatorial algorithm for l1-norm minimization is proposed in this paper. First, the algorithm searches the second best solutions which are close to the minimum l1-norm solution according to a threshold, and then the weighted sum of these second best solutions and the minimum l1-norm solution is taken as the estimation of the sources. The experiments of sound sources show that the recovery accuracy of the sources can be increased by about 10% when the number of mixtures is not too small.
Keywords: underdetermined blind source separation; sparse signals; l1-norm minimization; linear programming

1 引 言
近年来, 观测信号个数少于源信号个数的欠定盲源分离(underdetermined blind source separation, UBSS) 已成为盲源分离(blind source separation, BSS)领域的研究热点[1-7]。
考虑BSS的基本瞬时线性混合模型,
(1)
式中: s(t) = [s1(t), s2(t),, sN(t)]T表示N维源信号向量, x(t) = [x1(t), x2(t),, xM(t)]T表示M维观测信号向量, A表示M×N维的混合矩阵, ai是A的列向量, t是离散时刻, T是观测信号点数。BSS的命题就是, 对任何t, 根据已知的x(t), 在A未知的条件下求未知的s(t)。当M矩阵A和估计源信号s(t)两步[2]。目前很多文献集中研究如何估计混合矩阵A, 提出了很多有效的方法[3-5]。而对于如何估计源信号s(t), 缺乏十分有效的方法, 研究的也相对较少。本文在假定A已经估计出来的前提下, 集中研究如何估计源信号s(t)。
针对估计源信号s(t)的问题, 一般是在源信号服从稀疏分布的假设条件下, 将该问题转化为l1范数最小化问题。最经典的求解方法是线性规划法[4-6], 但线性规划法计算复杂度高, 求解速度很慢。为此, P. Bofill[2]等人提出了最短路径法, 大大提高了求解速度, 该方法的解与线性规划法的解等价, 但它仅适用于观测信号个数等于2的情形。S Winte[8]、I. Takigawa[9]等采用一种组合算法进行求解, 这种算法可视为最短路径法的扩展, 适用于观测信号个数大于2的情形。但是这些传统的l1范数最小化方法都对源信号的稀疏性要求较高, 从而限制了源信号的估计精度。另外, S. Rickard[10]、E. Vincent[11]等人利用信号在时频域中的稀疏性, 将听觉场景分析中的时频掩蔽方法应用到欠定盲源分离问题中, 取得了一定效果, 但该方法对信号在时频域中的稀疏性要求更高。
为降低算法对源信号稀疏性的要求, 提出了一种改进的l1范数最小化组合算法。该算法首先根据一定阈值找到与最小l1范数解最接近的若干次优解, 然后将这些次优解和最小l1范数解进行加权叠加, 并将结果作为源信号的估计。仿真实验表明, 基于该算法的欠定盲源分离, 能得到比传统的l1范数最小化方法更高的源信号估计精度。
2 传统的l1范数最小化方法
根据文献[2-6], 信号的稀疏性是指信号在大多数时刻取值为零或接近零。一般情况下, 信号在某种变换域(如傅里叶变换域或小波变换域)中会具有比时域更好的稀疏性。一个典型的稀疏分布就是拉普拉斯分布。在源信号独立同分布并且服从这种典型稀疏分布的假设条件下, 当混合矩阵A已知时, 由最大后验概率, 源信号的估计可以归结为求解如下T个优化问题:
(2)
式中: ŝ(t)称作源信号s(t)的估计。
式(2)即称作l1范数最小化问题, 该问题的解称作最小l1范数解。针对该问题, 目前经典的求解方法包括线性规划法[4-6]、最短路径法[2]和组合算法[8-9]等。F. Theis[3]和I. Takigawa[9]等证明了这3种方法的解是等价的, 而线性规划法计算复杂度高、求解速度慢, 最短路径法仅适用于观测信号个数等于2的情形, 组合算法又可以看作最短路径法在高维情况的扩展, 因此本文仅对组合算法作下介绍。
根据文献[9]的证明, 最小l1范数解中至少有N-M个零, 即最多有M个非零值。因此, 可得到个可能解, 通过比较这些可能解, 便可得到最小l1范数解。组合算法的具体步骤如下:
1) 求出A的个M×M维子矩阵, 设为Bk=, k=1,,, k1,,kM{1,,N}。
2) 对某一时刻t, 根据下式求出l1范数最小化问题的可能解, 记为ŝ(k)(t)=[, k= 1,,。
(3)
3) 根据下式求出ŝ(k)(t)对应的l1范数Jk, k=1,, 。
(4)
4) 根据下式确定最小l1范数解ŝmin(t), 并将其作为s(t)的估计ŝ(t)。
(5)
5) 根据第(2)~(4)步, 求出所有时刻的ŝ(t), 即得到源信号的估计。
3 改进的l1范数最小化组合算法
3.1 算法原理
如前所述, 传统的l1范数最小化方法是建立在源信号稀疏特性基础之上的。根据文献[9], 源信号越稀疏, 其估计结果越精确。由信号稀疏性的含义可知, 如果源信号足够稀疏, 那么在大多数采样时刻将只有一个源信号取值占优。在这些时刻, 最小l1范数解能够非常好地逼近源信号。而在多个源信号取值占优的时刻, 其解与真实的源信号将相差较大。由于当源信号并不是特别稀疏时, 多个源信号取值占优的时刻将会较多, 所以最小l1范数解对源信号的估计效果也将较差。因此, l1范数最小化方法对源信号的稀疏性要求较高, 在源信号并不充分稀疏的情况下, 其估计精度受到限制。
为降低传统的l1范数最小化方法对源信号稀疏性的要求, 本文提出了一种改进的l1范数最小化方法 其基本思想如下: l1范数最小化问题存在个可能解, 其最优解就是取这些可能解中l1范数最小的解, 它逼近源信号的概率最大。但是, 考虑其他一些可能解, 如果其l1范数也较小, 那么它们逼近源信号的概率也会较大。因此, 考虑将这些l1范数都比较小的可能解进行加权叠加, 其结果有可能更加逼近源信号, 从而降低算法对源信号稀疏性的要求。由于这些可能解逼近源信号的概率与它们的l1范数值成反比, 因此根据它们的l1范数值来确定它们的加权系数。
3.2 算法步骤
改进的l1范数最小化组合算法步骤如下:
1) 根据第2节的方法, 对某一时刻t, 求出l1范数最小化问题的可能解ŝ(k)(t)和相应的l1范数Jk, k=1,,, 以及最小l1范数解ŝmin(t)。ŝmin(t)的l1范数记为Jmin, 对应的k值为kmin。
2) 设定阈值r, 用于判别可能解的l1范数Jk是否足够小。
3) 对于每个ŝ(k)(t), k=1,,且k ≠ kmin, 若, 则称ŝ(k)(t)为l1范数最小化问题的次优解, 将这些次优解记为ŝ(c)(t), c=1,,C, C为次优解的个数。这些次优解对应的l1范数记为J(c)。
4) 根据下式确定最小l1范数解ŝmin(t)的加权系数, 记为pmin。pmin与Jmin成反比。
(6)
5) 根据下式确定次优解ŝ(c)(t)的加权系数, 分别记为p(c), c=1,,C。p(c)与J(c)成反比。
(7)
6) 根据下式将最小l1范数解ŝmin(t)和所有次优解ŝ(c)(t)进行加权叠加, 其结果代替最小l1范数解, 作为s(t)的估计ŝ(t)。
(8)
7) 根据第(1)~(6)步, 求出所有时刻的ŝ(t), 即得到源信号的估计。
当阈值r取合适的值时, 在只有一个源信号取值占优的时刻, 最小l1范数解逼近源信号的概率最大, 在这些时刻次优解个数为0, 所以算法的结果与传统的组合算法一致; 而在多个源信号取值占优的时刻, 次优解的个数不为0, 这些次优解逼近源信号的概率均较大, 所以算法的结果为这些次优解和最小l1范数解的加权叠加, 它将可能比最小l1范数解更加逼近源信号。
4 实验结果及分析
4.1 源信号估计精度评价准则
为了评价欠定盲源分离算法对源信号的估计精度, 将估计出的源信号ŝi和已知的源信号si进行比较, 采用“信噪比”(signal-to-noise ratio, SNR)进行评价, 其定义如下[4]:
(9)
式中: N为源信号的个数。进行计算之前, ŝi和si需通过尺度调整使其具有相等的能量。
将各个源信号估计的SNRi(i=1,,N)进行平均, 得到“平均信噪比”, 作为算法总体估计精度的评价。该值越高表明算法估计精度越高。
(10)
4.2 测试数据集
实验所用的源信号采用文献[4]中的语音信号s1、s2、s3、s4、s5, 每个信号是一段10 s的诗朗诵语音, 采样频率8 kHz。根据混合矩阵生成观测信号。设M和N分别表示观测信号的个数和源信号的个数, 那么采用“MmNs”表示一种混合情况。针对以下4个数据集进行实验:
1) 2m3s: 源信号采用s1、s2、s3, 其混合矩阵为
;
2) 3m4s: 源信号采用s1、s2、s3、s4, 其混合矩阵为
;
3) 3m5s: 源信号采用s1、s2、s3、s4、s5, 其混合矩阵为
。
4) 4m5s: 源信号采用s1、s2、s3、s4、s5, 其混合矩阵为
。
4.3 实验方法及结果分析
为使信号更加稀疏, 对观测信号进行短时傅里叶变换(short time fourier transform, STFT), 在变换域中对STFT系数的实部和虚部分别进行求解, 得到源信号STFT系数的实部和虚部, 将此结果反变换到时域即得到源信号的估计。这种在STFT域中进行求解的方法和文献[2][4-5]中的方法是一致的。窗函数选为Hamming窗, 与文献[4]一致。为了对算法进行全面考核, 对不同窗长度的变换结果进行测试。窗长度分别设为16 ms、32 ms、64 ms、128 ms、256 ms, 对应的采样点数分别为128、256、512、1 024、2 048。相邻窗的重叠长度均设为窗长度的一半。对应每一种窗长度的STFT变换, 算法采用不同的阈值r进行运算, 将较优的结果列入表1~表4中。表中也列出了与较优结果相对应的r值。

表1 “2m3s”情况算法测试结果
Table 1 Experimental results on the data set “2m3s”
STFT窗长度/对应点数

组合算法
本文算法
/dB
/dB
对应的r值
16 ms/128
8.28
8.28
0.05
32 ms/256
10.00
10.02
0.15
64 ms/512
11.38
11.45
0.20
128 ms/1024
11.07
11.11
0.10
256 ms/2048
10.13
10.18
0.15

表2 “3m4s”情况算法测试结果
Table 2 Experimental results on the data set “3m4s”
STFT窗长度/对应点数

组合算法
本文算法
/dB
/dB
对应的r值
16 ms/128
11.49
12.05
0.65
32 ms/256
12.94
13.76
0.60
64 ms/512
13.94
14.97
0.15
128 ms/1 024
13.74
14.64
0.15
256 ms/2 048
12.71
13.59
0.15
表3 “3m5s”情况算法测试结果
Table 3 Experimental results on the data set “3m5s”
STFT窗长度/对应点数

组合算法
本文算法
/dB
/dB
对应的r值
16 ms/128
7.23
8.04
0.60
32 ms/256
8.98
10.10
0.55
64 ms/512
10.14
11.34
0.55
128 ms/1024
9.88
11.01
0.50
256 ms/2048
9.06
9.87
0.45

表4 “4m5s”情况算法测试结果
Table 4 Experimental results on the data set “4m5s”
STFT窗长度/对应点数

组合算法
本文算法
/dB
/dB
对应的r值
16 ms/128
14.57
15.65
0.10
32 ms/256
16.75
18.44
0.15
64 ms/512
17.64
19.72
0.15
128 ms/1024
17.19
19.13
0.15
256 ms/2048
15.42
16.93
0.15

为了使算法的测试结果更具有对比性, 对传统的组合算法[8-9]也进行了测试。算法运行前, 都对观测信号进行STFT变换, 参数设置和前面一样。算法的运行结果也列入表1~表4中。
由表中结果可看出, 当阈值r设置较合适时, 本文算法总体上能够得到比传统的组合算法更高的估计精度。但是, 对于“2m3s”情况, 本文算法的优势不太明显; 而对于“3m4s”、“3m5s”和“4m5s”情况, 本文算法的优势较明显。这说明在观测信号个数较小的低维情况, 相比于最小l1范数解, l1范数最小化问题的其它可能解逼近源信号的概率较小, 本文算法采用次优解修正最小l1范数解的策略不能够奏效; 而在观测信号个数较大的高维情况, l1范数最小化问题的可能解较多, 其逼近源信号的概率较大, 本文算法的改进策略得以奏效。另外, 由于本文算法增加了对次优解的判断与运算, 所以其运算复杂度相比于组合算法将有所增加。
当STFT窗长度不同时, 算法对源信号的估计精度将不同。其原因在于源信号经STFT变换后的稀疏程度与窗长度有关。由表1~表4可看出, 本文算法与组合算法的估计精度随窗长度的变化趋势一致。当窗长度为64ms时, 两种算法的估计精度都达到最高。这说明此时源信号在STFT域的稀疏性最好, 这与文献[10]关于语音信号在STFT域稀疏性的结论一致。这也说明了本文算法与组合算法一样, 其基础仍是源信号的稀疏性。当稀疏性越好时, 算法结果也越好。
为考察本文算法在阈值r取不同值时的性能, 图1画出了针对“3m5s”数据集, 算法运行结果的随r变化的曲线。其中, STFT窗长度设为64 ms, r在0~2范围内取值。为进行对比, 图中也画出了采用组合算法所得结果的值。由图1可看出, 阈值r需在一定合适的范围内取值, 本文算法的估计精度才会优于组合算法。对于“3m5s”情况, 其合适的取值范围约为0~1。由算法步骤可知, 阈值r控制着次优解的个数。若r值太大, 则所有可能解都会成为次优解, 源信号的稀疏性假设便失去意义, 算法结果将较差; 若r值太小, 则次优解将非常少, 本文算法对最小l1范数解的修正效果将很有限。在极端情况, 当r=0时, 次优解个数为0, 所以算法的结果即为最小l1范数解, 从而失去改进效果。

图1 “3m5s”情况随阈值r变化曲线
Fig. 1 Variation of with threshold value r for data set “3m5s”
5 结 论

付 宁
基于稀疏表示的欠定盲源分离问题可转化为l1范数最小化问题。本文在分析传统的l1范数最小化方法优缺点的基础上, 提出了一种改进的l1范数最小化组合算法。该算法充分利用了l1范数最小化问题的次优解, 通过对最小l1范数解的修正, 有效降低了传统方法对源信号的稀疏性要求, 从而提高了源信号的估计精度。由于增加了对次优解的判断与运算, 算法的运算复杂度有所增加。通过对几种语音信号的实验, 表明本文算法的源信号估计精度优于传统方法。
参考文献:
[1] LEE T W, LEWICKI M S, GIROLAMI M, SEJNOWSKI T J. Blind source separation of more sources than mixtures using overcomplete representations [J]. IEEE Signal Process Letter, 1999, 6(4): 87-90.
[2] BOFILL P, ZIBULEVSKY M. Underdetermined blind source separation using sparse representations [J]. Signal Processing, 2001, 81(11): 2353-2362.
[3] THEIS F J, LANG E W, PUNTONET C G. A geometric algorithm for overcomplete linear ICA [J]. Neurocomputing. 2004, 56(1-4): 381-398.
[4] O’GRADY P D, PEARLMUTTER B A. Hard-LOST: Modified k-means for oriented lines [C]. Proceedings of the Irish Signals and Systems Conference, Belfast, Ireland, 2004: 247-252.
[5] HE Z S, XIE S L, FU Y L. Sparse representation and blind source separation of ill-posed mixtures [J]. Science in China (Series F: Information Sciences), 2006, 49(5): 639-652.
[6] LI Y Q, CICHOCKI A, AMARI S. Analysis of sparse representation and blind source separation [J]. Neural Computation, 2004, 16(6): 1193-1234.
[7] 高莉, 黄力宇. 基于自适应梯度盲源分离算法的胎儿心电提取[J]. 仪器仪表学报, 2008, 29(8): 1756-1760.
GAO L, HUANG L Y. Separating maternal and fetal electrocardiograms based on adaptive gradient algorithm for blind source separation [J]. Chinese Journal of Scientific Instrument, 2008, 29(8): 1756-1760.
[8] WINTER S, SAWADA H, MAKINO S. On real and complex valued l1-norm minimization for overcomplete blind source separation [C]. IEEE Workshop on Applications of Signal Processing to Audio and Acoustics [C], NY, United States, 2005: 86-89.
[9] TAKIGAWA I, KUDO M, TOYAMA J. Performance analysis of minimum l1-norm solutions for underdetermined source separation [J]. IEEE Transactions on Signal Processing, 2004, 52(3): 582-591.
[10] YILMAZ Ö RICKARD S. Blind separation of speech mixtures via time-frequency masking [J]. IEEE Transactions on Signal Processing, 2004, 52(7): 1830-1847.
[11] VINCENT E, GRIBONVAL R, PLUMBLEY M D. Oracle estimators for the benchmarking of source separation algorithms [J]. Signal Processing, 2007, 87(8): 1933-1950.
作者简介:
付 宁: 男, 1979年出生, 现为哈尔滨工业大学自动化测试与控制系博士研究生。主要研究方向为盲信号处理、自动测试技术等。
E-mail: farnold1224@
Fu Ning: male, born in 1979. He is currently a PhD candidate in Harbin Institute of Technology, China. His research interest is in blind source separation and automatic test technology.

第3期 汤清虎 等: 非晶态Mn-Ce-O催化芒香醇选择氧化 7