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

1、第 23 卷 第 7 期 电 子 测 量与 仪 器学 报 Vol. 23 No. 7 2009 年 7 月 JOURNAL OF ELECTRONIC MEASUREMENT AND INSTRUMENT 1 本文于 2009 年 2 月收到。 更多电子资料请登录赛微电子网 基于改进 l1 范数最小化组合算法的欠定盲源分离 付 宁 彭喜元 (哈 尔滨 工 业 大学自 动 化 测试 与控制系 , 哈 尔滨 150080) 摘 要 : 基于稀疏假 设 , 欠定盲源分离 问题 一般可采用 线 性 规 划、最短路径法和 组 合算法等 l1范数最小化方法 进 行求解 , 但是 这 些 传统 方法 对 源

2、信号的稀疏性要求 较 高 , 从而限制了源信号的估 计 精度。 为 此 , 本文提出了一种改 进 的 l1范数最小化 组 合算法 . 该 算法根据一定 阈值 找到与最小 l1范数解最接近的若干次 优 解 , 将 这 些次 优 解和最小 l1范数解 进 行加 权 叠加 , 并替代 最 小 l1 范 数 解 , 作 为 源 信 号 的 估 计 。采 用 语 音 信 号 的 仿 真 实 验 表 明 , 对 于 观 测 信 号 个 数 不 太 小 的 高 维 混 合 情 况 , 该 算 法 的 源 信 号 估 计 精度能 够 比 传统 的 l1范数最小化 组 合算法提高 10%左右。 关键词 : 欠定

3、盲源分离；稀疏信号； 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:

4、 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 t

5、he 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 acco

6、rding 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

7、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)1()(),2NittstT

8、xAsa 式中 : s(t) = s1(t), s2(t), , sN(t)T表示 N 维 源信号向L 量 , x(t) = x1(t), x2(t), , xM(t)T表示 M 维观测 信号 向量 , A 表示 MN 维 的混合矩 阵 , ai 是 A 的列向量 , t 是离散 时 刻 , T 是 观测 信号点数。 BSS 的命 题 就是 , 对 任何 t, 根据已知的 x(t), 在 A 未知的条件下求未 知的 s(t)。当 MN 时 , 这 个 问题 就称 为 UBSS。 对 于欠定盲源分离 问题 , 一般将求解 过 程分解 为 估 计 混合矩 阵 A 和估 计 源信号 s(t)两步 2

9、。目前很 多文献集中研究如何估 计 混合矩 阵 A, 提出了很多 有效的方法 3-5。而 对 于如何估 计 源信号 s(t), 缺乏十 分有效的方法 , 研究的也相 对较 少。本文在假定 A 已 经 估 计 出来的前提下 , 集中研究如何估 计 源信号 s(t)。 2 电 子 测 量 与 仪 器 学 报 2009 年 针对 估 计 源信号 s(t)的 问题 , 一般是在源信号服 从稀疏分布的假 设 条件下 , 将 该问题转 化 为 l1范数 最小化 问题 。最 经 典的求解方法是 线 性 规 划法 4-6, 但 线 性 规 划法 计 算复 杂 度高 , 求解速度很慢。 为 此 , P. Bof

10、ill2等人提出了最短路径法 , 大大提高了求解 速度 , 该 方法的解与 线 性 规 划法的解等价 , 但它 仅 适用于 观测 信号个数等于 2 的情形。 S. Winte8、I. Takigawa9等采用一种 组 合算法 进 行求解 , 这 种算 法可 视为 最短路径法的 扩 展 , 适用于 观测 信号个数 大于 2 的情形。但是 这 些 传统 的 l1范数最小化方法 都 对 源信号的稀疏性要求 较 高 , 从而限制了源信号 的估 计 精度。另外 , S. Rickard10、E. Vincent11等人 利用信号在 时频 域中的稀疏性 , 将听 觉场 景分析中 的 时频 掩蔽方法 应 用

11、到欠定盲源分离 问题 中 , 取得 了一定效果 , 但 该 方法 对 信号在 时频 域中的稀疏性 要求更高。 为 降低算法 对 源信号稀疏性的要求 , 提出了一 种改 进 的 l1范数最小化 组 合算法。 该 算法首先根据 一定 阈值 找到与最小 l1范数解最接近的若干次 优 解 , 然后将 这 些次 优 解和最小 l1范数解 进 行加 权 叠加 , 并将 结 果作 为 源信号的估 计 。仿真 实验 表明 , 基于 该 算法的欠定盲源分离 , 能得到比 传统 的 l1范数最 小化方法更高的源信号估 计 精度。 2 传统的 l1 范数最小化 方法 根据文献 26, 信号的稀疏性是指信号在大多 数

12、 时 刻取 值为 零或接近零。一般情况下 , 信号在某 种 变换 域 (如傅里叶 变换 域或小波 变换 域 )中会具有 比 时 域更好的稀疏性。一个典型的稀疏分布就是拉 普拉斯分布。在源信号独立同分布并且服从 这 种典 型稀疏分布的假 设 条件下 , 当混合矩 阵 A 已知 时 , 由最大后 验 概率 , 源信号的估 计 可以 归结为 求解如 下 T 个 优 化 问题 : (2)()1min,.:(),1,NitstttTssx 式中 : (t)称作源信号 s(t)的估 计 。 式 (2)即称作 l1范数最小化 问题 , 该问题 的解称 作最小 l1范数解。 针对该问题 , 目前 经 典的求解

13、方 法包括 线 性 规 划法 4-6、最短路径法 2和 组 合算法 8-9 等。 F. Theis3和 I. Takigawa9等 证 明了 这 3 种方法 的解是等价的 , 而 线 性 规 划法 计 算复 杂 度高、求解 速度慢 , 最短路径法 仅 适用于 观测 信号个数等于 2 的情形 , 组 合算法又可以看作最短路径法在高 维 情 况的 扩 展 , 因此本文 仅对组 合算法作下介 绍 。 根据文献 9的 证 明 , 最小 l1范数解中至少有 NM 个零 , 即最多有 M 个非零 值 。因此 , 可得到 个可能解 , 通 过 比 较这 些可能解 , 便可得到最C 小 l1范数解。 组 合算

14、法的具体步 骤 如下 : 1) 求出 A 的 个 MM 维 子矩 阵 , 设为 Bk=NC , k=1, , , k1, ,kM 1, ,N。1,MkaLL 2) 对 某 一 时 刻 t, 根 据 下 式 求 出 l1范 数 最 小 化 问 题 的 可 能 解 , 记为 (k)(t)= , k= (),st ()Tkst 1, , 。LN (3)1 ()()T11,(),0MkkkMjststtNjjk 且Bx 3) 根据下式求出 (k)(t)对应 的 l1范数 Jk, k=1, , L 。NC (4)()1,NkMki NJstC 4) 根据下式确定最小 l1范数解 min(t), 并将其

15、作 为 s(t)的估 计 (t)。 (5)()mini,k NstJ 5) 根据第 (2)(4)步 , 求出所有 时 刻的 (t), 即得 到源信号的估 计 。 3 改进的 l1 范数最小化组合算法 3.1 算法原理 如前所述 , 传统 的 l1范数最小化方法是建立在 源信号稀疏特性基 础 之上的。根据文献 9, 源信号 越稀疏 , 其估 计结 果越精确。由信号稀疏性的含 义 可知 , 如果源信号足 够 稀疏 , 那么在大多数采 样时 刻将只有一个源信号取 值 占 优 。在 这 些 时 刻 , 最小 l1范数解能 够 非常好地逼近源信号。而在多个源信 号取 值 占 优 的 时 刻 , 其解与真

16、 实 的源信号将相差 较 大。由于当源信号并不是特 别 稀疏 时 , 多个源信号 取 值 占 优 的 时 刻将会 较 多 , 所以最小 l1范数解 对 源 信号的估 计 效果也将 较 差。因此 , l1范数最小化方法 对 源信号的稀疏性要求 较 高 , 在源信号并不充分稀 疏的情况下 , 其估 计 精度受到限制。 为 降低 传统 的 l1范数最小化方法 对 源信号稀疏 性的要求 , 本文提出了一种改 进 的 l1范数最小化方 法 , 其基本思想如下 : l1范数最小化 问题 存在 个MNC 可能解 , 其最 优 解就是取 这 些可能解中 l1范数最小 的解 , 它逼近源信号的概率最大。但是 ,

17、 考 虑 其他一 些可能解 , 如果其 l1范数也 较 小 , 那么它 们 逼近源 信号的概率也会 较 大。因此 , 考 虑 将 这 些 l1范数都 第 7 期 基于改 进 l1范数最小化 组 合算法的欠定盲源分离 3 比 较 小的可能解 进 行加 权 叠加 , 其 结 果有可能更加 逼近源信号 , 从而降低算法 对 源信号稀疏性的要求。 由于 这 些可能解逼近源信号的概率与它 们 的 l1范数 值 成反比 , 因此根据它 们 的 l1范数 值 来确定它 们 的 加 权 系数。 3.2 算法步骤 改 进 的 l1范数最小化 组 合算法步 骤 如下 : 1) 根据第 2 节 的方法 , 对 某一

18、 时 刻 t, 求出 l1 范数最小化 问题 的可能解 (k)(t)和相 应 的 l1范数 Jk, k=1, , , 以及最小 l1范数解 min(t)。min(t)的 l1LMNC 范数 记为 Jmin, 对应 的 k 值为 kmin。 2) 设 定 阈值 r, 用于判 别 可能解的 l1范数 Jk是 否足 够 小。 3) 对 于每个 (k)(t), k=1, , 且 k kmin, 若LMNC , 则 称 (k)(t)为 l1范数最小化 问题 的mini|kJrJ 次 优 解 , 将 这 些次 优 解 记为 (c)(t), c=1, ,C, C 为 次 优 解的个数。 这 些次 优 解 对

19、应 的 l1范数 记为 J(c)。 4) 根据下式确定最小 l1范数解 min(t)的加 权 系 数 , 记为 pmin。pmin与 Jmin成反比。 (6)minmin()i1CcJ 5) 根据下式确定次 优 解 (c)(t)的加 权 系数 , 分 别记为 p(c), c=1, ,C。p(c)与 J(c)成反比。L (7)()min1,cCJ 6) 根据下式将最小 l1范数解 min(t)和所有次 优 解 (c)(t)进 行加 权 叠加 , 其 结 果代替最小 l1范数解 , 作 为 s(t)的估 计 (t)。 (8)()mini1 Ccptptss 7) 根据第 (1)(6)步 , 求出所

20、有 时 刻的 (t), 即得 到源信号的估 计 。 当 阈值 r 取合适的 值时 , 在只有一个源信号取 值 占 优 的 时 刻 , 最小 l1范数解逼近源信号的概率最 大 , 在 这 些 时 刻次 优 解个数 为 0, 所以算法的 结 果与 传统 的 组 合算法一致 ; 而在多个源信号取 值 占 优 的 时 刻 , 次 优 解的个数不 为 0, 这 些次 优 解逼近源信号 的概率均 较 大 , 所以算法的 结 果 为这 些次 优 解和最 小 l1范数解的加 权 叠加 , 它将可能比最小 l1范数解 更加逼近源信号。 4 实验结果及分析 4.1 源信号估计精度评价准则 为 了 评 价欠定盲源分

21、离算法 对 源信号的估 计 精 度 , 将估 计 出的源信号 i 和已知的源信号 si进 行比 较 , 采用 “信噪比 ”(signal-to-noise ratio, SNR)进 行 评 价 , 其定 义 如下 4: (9)SNR20log,1,ii iNs 式中 : N 为 源信号的个数。 进 行 计 算之前 , i 和 si 需通 过 尺度 调 整使其具有相等的能量。 将各个源信号估 计 的 SNRi(i=1, ,N)进 行平均 , L 得到 “平均信噪比 ” , 作 为 算法 总 体估 计 精度的SR 评 价。 该值 越高表明算法估 计 精度越高。 (10)=1Nii 4.2 测试数据

22、集 实验 所用的源信号采用文献 4中的 语 音信号 s1、s2、s3、s4、s5, 每个信号是一段 10 s 的 诗 朗 诵语 音 , 采 样频 率 8 kHz。根据混合矩 阵 生成 观测 信号。 设 M 和 N 分 别 表示 观测 信号的个数和源信号的个数 , 那 么采用 “MmNs”表示一种混合情况。 针对 以下 4 个数 据集 进 行 实验 : 1) 2m3s: 源信号采用 s1、s2、s3, 其混合矩 阵为 ; 230.917.40.678598ms A 2) 3m4s: 源信号采用 s1、s2、s3、s4, 其混合矩 阵 为 ;34 060.70.516872489.19.35.2.

23、ms 3) 3m5s: 源信号采用 s1、s2、s3、s4、s5, 其混合矩 阵为 350.746.70.6.910.8621983274.ms A 。 4) 4m5s: 源信号采用 s1、s2、s3、s4、s5, 其混合矩 阵为 。45 0.37.680.70.1.904987.12.65.22 4ms A 4 电 子 测 量 与 仪 器 学 报 2009 年 4.3 实验方法及结果分析 为 使信号更加稀疏 , 对观测 信号 进 行短 时 傅里 叶 变换 (short time fourier transform, STFT), 在 变换 域 中 对 STFT 系数的 实 部和虚部分 别进

24、行求解 , 得到 源信号 STFT 系数的 实 部和虚部 , 将此 结 果反 变换 到 时 域即得到源信号的估 计 。这 种在 STFT 域中 进 行求解的方法和文献 24-5中的方法是一致的。窗 函数 选为 Hamming窗 , 与文献 4一致。 为 了 对 算法 进 行全面考核 , 对 不同窗 长 度的 变换结 果 进 行 测试 。 窗 长 度分 别设为 16 ms、32 ms、64 ms、128 ms、256 ms, 对应 的采 样 点数分 别为 128、256、512、1 024、2 048。相 邻 窗的重叠 长 度均 设为 窗 长 度的一半。 对应 每一种窗 长 度的 STFT 变换

25、 , 算法采用不同的 阈值 r 进 行运算 , 将 较优 的 结 果列入表 1表 4 中。表中也 列出了与 较优结 果相 对应 的 r 值 。 表 1 “2m3s”情况算法测试结果 Table 1 Experimental results on the data set “2m3s” 组 合算法 本文算法 STFT 窗 长 度 /对应 点数 /dBSNR/dBS对应 的 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 2

26、56 ms/2048 10.13 10.18 0.15 表 2 “3m4s”情况算法测试结果 Table 2 Experimental results on the data set “3m4s” 组 合算法 本文算法 STFT 窗 长 度 /对应 点数 /dBSNR/dBS对应 的 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”情况

27、算法测试结果 Table 3 Experimental results on the data set “3m5s” 组 合算法 本文算法 STFT 窗 长 度 /对应 点数 /dBSNR/dBS对应 的 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 s

28、et “4m5s” 组 合算法 本文算法STFT 窗 长 度 /对应 点数 /dBSNR/dBS对应 的 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 变换 , 参数 设 置和前面一 样 。算法 的运行 结

29、 果也列入表 1表 4 中。 由表中 结 果可看出 , 当 阈值 r 设 置 较 合适 时 , 本文算法 总 体上能 够 得到比 传统 的 组 合算法更高的 估 计 精度。但是 , 对 于 “2m3s”情况 , 本文算法的 优势 不太明 显 ; 而 对 于 “3m4s”、“3m5s”和 “4m5s”情况 , 本 文算法的 优势较 明 显 。这说 明在 观测 信号个数 较 小 的低 维 情况 , 相比于最小 l1范数解 , l1范数最小化 问 题 的其它可能解逼近源信号的概率 较 小 , 本文算法 采用次 优 解修正最小 l1范数解的策略不能 够 奏效 ; 而在 观测 信号个数 较 大的高 维

30、情况 , l1范数最小化 问 题 的可能解 较 多 , 其逼近源信号的概率 较 大 , 本文 算法的改 进 策略得以奏效。另外 , 由于本文算法增 加了 对 次 优 解的判断与运算 , 所以其运算复 杂 度相 比于 组 合算法将有所增加。 当 STFT 窗 长 度 不 同 时 , 算 法 对 源 信 号 的 估 计 精 度 将 不 同 。其 原 因 在 于 源 信 号 经 STFT 变 换 后 的 稀 疏 程 度 与 窗 长 度 有 关 。由 表 1表 4 可 看 出 , 本 文 算 法 与 组 合 算 法 的 估 计 精 度 随 窗 长 度 的 变 化 趋 势 一 致 。当 窗 长 度 为

31、64ms 时 , 两 种 算 法 的 估 计 精 度 都 达 到 最 高 。 这 说 明 此 时 源 信 号 在 STFT 域 的 稀 疏 性 最 好 , 这 与 文 献 10关 于 语 音 信 号 在 STFT 域 稀 疏 性 的 结 论 一 致 。 这 也 说 明 了 本 文 算 法 与 组 合 算 法 一 样 , 其基 础 仍 是 源 信 号 的 稀 疏 性 。当 稀 疏 性 越 好 时 , 算 法 结 果 也 越 好 。 为 考察本文算法在 阈值 r 取不同 值时 的性能 , 图 1 画出了 针对 “3m5s”数据集 , 算法运行 结 果的 随 r 变 化的曲 线 。其中 , STFT

32、 窗 长 度 设为 64 SNR ms, r 在 02 范 围 内取 值 。为进 行 对 比 , 图 中也画出 了采用 组 合算法所得 结 果的 值 。由 图 1 可看出 , SNR 阈值 r 需在一定合适的范 围 内取 值 , 本文算法的估 计 精度才会 优 于 组 合算法。 对 于 “3m5s”情况 , 其合 适的取 值 范 围约为 01。由算法步 骤 可知 , 阈值 r 控 制着次 优 解的个数。若 r 值 太大 , 则 所有可能解都会 成 为 次 优 解 , 源信号的稀疏性假 设 便失去意 义 , 算 法 结 果将 较 差 ; 若 r 值 太小 , 则 次 优 解将非常少 , 本 第

33、7 期 基于改 进 l1范数最小化 组 合算法的欠定盲源分离 5 文算法 对 最小 l1范数解的修正效果将很有限。在极 端情况 , 当 r=0 时 , 次 优 解个数 为 0, 所以算法的 结 果即 为 最小 l1范数解 , 从而失去改 进 效果。 图 1 “3m5s”情况 随 阈值 r 变 化曲 线SNR Fig. 1 Variation of with threshold value r for data set “3m5s” 5 结 论 基于稀疏表示的欠定盲源分离 问题 可 转 化 为 l1 范数最小化 问题 。本文在分析 传统 的 l1范数最小化 方法 优 缺点的基 础 上 , 提出了

34、一种改 进 的 l1范数最 小化 组 合算法。 该 算法充分利用了 l1范数最小化 问 题 的次 优 解 , 通 过对 最小 l1范数解的修正 , 有效降 低了 传统 方法 对 源信号的稀疏性要求 , 从而提高了 源信号的估 计 精度。由于增加了 对 次 优 解的判断与 运算 , 算法的运算复 杂 度有所增加。通 过对 几种 语 音信号的 实验 , 表明本文算法的源信号估 计 精度 优 于 传统 方法。 参考文献 : 1 LEE T W, LEWICKI M S, GIROLAMI M, SEJNOWSKI T J. Blind source separation of more source

35、s 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 algorith

36、m for overcomplete linear ICA J. Neurocomputing. 2004, 56(1-4): 381-398. 4 OGRADY 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 bli

37、nd 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.

38、 仪 器 仪 表学 报 , 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

39、-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

40、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

41、 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. 付 宁