信号稀疏表示算法研究毕业论文

1、信号稀疏表示算法研究-毕业论文 学校代号 10524 学 号12009384分 类 号密 级 硕士学位论文信号稀 疏表示算 法研究学位申请人姓名 张政培 养 单 位 电子信 息工程学院导师姓名及职称 朱翠涛 教授 学 科 专 业 通信与 信息系统 研 究 方 向 信号稀 疏表示 论文提交日 期 2012 年 月 日 学校代号:10524 学 号:12009384 密 级: 中南民族大学硕士学位论文信号稀疏表示算法研究学位申请人姓名: 张政 导师姓名及职称: 朱翠涛 教授培养单 位: 电子信息工程学院 专业名 称: 通信与信息系统论文提交日 期 : 2012 年 月日论文答辩日 期 : 2012

2、 年 月 日答辩委员会主席: RESEARCH ON SIGNAL SPARSE REPRESENTATIONby Zhang ZhengB.E. South-Central University for Nationalities2009 A thesis submitted in partial satisfaction of theRequirements for the degree of Master of Engineering inCommunication and Information System in theGraduate School of South-Central

3、 University for NationalitiesSupervisorProfessor Zhu Cuitao May, 2012 中 南民族 大学 学 位论文 原创性 声明 本人郑重 声明: 所 呈交的论 文是本人 在导师的 指导下独 立进行研 究所取得的研究 成果。 除 了文中特 别加以标 注引用的 内容外 , 本论文不 包含任何 其他个人或 集体已经 发表或撰 写的成果 作品 。 对本 文的研究 做出重要 贡献的 个人和集体 , 均已 在 文中以明 确方式标 明。 本 人 完全意识 到本声明 的法律后 果由本人承 担。作者签名 :日期:年 月 日学 位论文 版权使 用授权 书 本

4、学位论 文作者完 全了解学 校有关保 留、 使用 学位论文 的规定, 同意学校保留并 向国家有 关部门或 机构送交 论文的复 印件和电 子版 , 允 许 论文被 查阅和借阅 。 本人授权 中南民族 大学可以 将本学位 论文的全 部或部分 内容编 入有关数据 库进行检 索, 可 以 采用影印 、 缩印 或 扫描等复 制手段保 存和汇编 本学位论文 。 本学位论 文属于 1 、保 密 ,在_ 年解 密后 适用本授 权书。 2 、不 保密 。 (请在以 上相应方 框内打“ ” )作者签名 : 日期:年 月 日 导师签名 : 日期:年 月 日 目 录 摘 要I ABSTRACT. II 第 1 章 绪

5、 论 1 1.1 研究背景 和意义. 1 1.2 国内外研 究现状 1 1.3 论文主要 工作. 6 1.4 论文组织 结构. 7 第2 章 基于快速互相关运算的信号稀疏表示算法8 2.1 问题描述8 2.2 算法描述. 13 2.3 仿真及分 析 16 2.4 本章小结. 23 第 3 章 基于稀疏框架的信号稀疏表示24 3.1 问题描述. 24 3.2 稀疏框架 的构造25 3.3 基于稀疏 框架的信号稀疏表示29 3.4 仿真及分 析 31 3.5 本章小结 33 第 4 章 总结与展望. 34 参考文献. 36 致 谢40 附录 攻读硕士学位期间所发表的学术论文 41 中南民族大学硕士

6、学位论文 摘 要 随着 信 息 技 术 的 不 断 发 展 , 人 们 对 信 息 量 的 需 求 就 变 得 越 来 越 大 , 传 统 信 号的 分 解 过 程 中 产 生 大 量 高 复 杂 度 的 计 算 问 题 就 显 得 尤 为 突 出 , 制 约 了 信 号 的 后 继处 理 和 传 输 。 所 以 人 们 一 直 在 寻 求 一 种 简 洁 、 高 效 的 信 号 表 示 方 法 , 信 号 的 稀 疏表 示 算 法 就 是 其 中 常 用 的 一 种 方 法 。 因 此 , 本 文 对 信 号 稀 疏 表 示 问 题 中 的 内 积 运算和分解向量两个问题展开了研究。 针对

7、信 号 稀 疏 分 解 过 程 中 存 在 的 大 量 的 内 积 计 算 问题, 本文 在 对 匹 配 追 踪 算法 基 础 上 进 行 改 进 得到 一种 基 于 快 速 互 相 关 运 算 的 信 号 稀 疏 表 示 算法 。 该 算 法 的主要 思想 是 : 在 迭 代 进 行 的 每 一 步 将 信 号 稀 疏 分 解 过 程 中 耗 费 大 量 计算 时 间 和 存储 空 间 的 内 积 计 算 看 作 一 次 互 相 关 运 算 , 然后 用一种 间 隔 取 点 跳 跃 计 算 的 快 速 算法 求 出 互 相 关 运 算 的 最 大 值 来 寻 求 每 一 步 的 最 佳 原

8、子 。 通 过 软 件 实 验 的 仿 真 , 改进后的算法能够较好地重构出原始信号。 将改进后的算法与 匹配追踪算法相比较,改进 后的 算法 的 运 算 量 有 着 显 著 的 降 低 , 计 算 速 度 有 了 较 大 的 提 高 , 并 具 有 良 好的收敛性 。 针 对 过 完 备 原 子 库 形 成 过 程 中 需 要 进 行 的 大 量 运 算 和 存 储 问 题 , 本 文 在 引 入框架理论的基础上将STF 算法应用到框架的形成中, 得到一种稀疏框架,并用稀 疏框 架 代 替 过 完 备 原 子 库 进 行 信 号 的 稀 疏 表 示 。 软 件 仿 真 结 果 表 明 , 信

9、 号 在 稀 疏 框架上 进行 稀 疏 分 解 后 重 构 出 的 信 号 能 够 在 一 定 程 度 上 较 好 地 表 示 原 始 信 号 的 主 要特点 。 将 信 号 在 稀 疏 框 架 上 进 行 信 号 的 稀 疏 表 示 与 信 号 在 过 完 备 原 子 库 上 进 行 信号 的 稀 疏 表示 相 比 较 , 构 成 稀 疏 框 架 的 原 子 数 目 要 远 小 于 形 成 过 完 备 原 子 库 的 原子 数 目 , 极 大 地 简 化 了 原 子 库 形 成 中 大 量 的 计 算 和 存 储 , 减 少 了 计 算 时 间 , 提 高了计算效率。 关键 词: 稀疏表 示

10、 ;快速互 相关运算 ; 内积运算; 稀疏框架I 信号稀疏表示算法研究 ABSTRACT With the continuou development of information technology recentlly, the demand on the information becomes much bigger.There is a problem that a large amount of high complexity calculating produced in the traditional signal decomposition process appears ve

11、ry prominent,and restricting signal processing and transmission. The resrarchers have been looking for a simple, efficient method of signal representation, signal sparse representation algorithm is one of the methods which is commonly used. Therefore, this thesis does some reach about problems of th

12、e inner product and vector decomposition in sparse signal representationAiming at the large number of inner product problem in sparse decomposition, a fast computation method for sparse decomposition based on the cross-correlation calculation is proposed in this thesis. The main idea of the algorith

13、m is as fellow:It uses a fast jump point computation method instead of a large number of inner product operation at each step of iterative operation to find out the best atomic. Simulation results show that the improved algorithm can be used to reconstruct the orginal signal well. Compared with the

14、matching pursuit algorithm, the computation of the improved algorithm is significantly reduced, the calculation speed is improved, and has a better convergenceConsidering the issue of a large number of computing and storge in the process of formating Over-complete dictionary,in this paper,STF algori

15、thm is applied to the formation of the framework based on the introduction of the theory of frame to obtain a sparse frame,and the sparerepresentation of signal is processed by sparse frame instead of over-complete dictionary.The results of simulation by software shows that the reconstructed signal

16、which is decomposition by sparse frame can represent the main features of original signal well to some extentpared with the sparerepresentation of signal by over-complete dictionary,the number of atoms of constituting a spare frame is much smaller,and this approach greatly simplifies computing and s

17、torage during the formation of the atom library, and reduces the computational time and improves computing efficiency Keywords: sparse representation; fast cross-correlation calculation; inner product; sparse frameII 中南民族大学硕士学位论文 第 1 章 绪 论 1.1 研 究背景 和意义 近年来 , 人 们 对 信 息 的 获 取 、 加工 、 传递 、 处 理 以 及 应 用

18、等 要 求 随 着 社 会 的发 展 和 信 息 技 术 的 更 新 而 变 得 越 来 越 高 , 很 多 领 域 也 就 日 益 面 临 着 对 各 种 诸 如 音频 数 据 , 视 频 数 据 , 天 文 数 据 等 大 量 数 据 的 处 理 和 存 储 等 问 题 。 然 而 用 什 么 方 法实现 对 这 些 数 据 的 表 达 更 加地 简 单和 灵 活 已 经 成 为 一 个 研 究 热 点 而 倍受 研 究 者 们的关注,其中 对信号进行稀疏表示就是一个很有效的方法 。 在 对 信 号 进 行 研 究 和 处 理 时 首 先 要 对 信 号 进 行 分 解 或 者 变 换 到

19、 相 应 的 域 , 传统 意 义 上 对 信号 进行 分解 或者 变换 一般 是 将 信 号 在 一 组 正 交 基 上 进行 分解 , 而 这个 正 交 基 必 须 是 完 备 的 。 目 前 一 些 比 较 成 熟 的 分 解 方 法 有 傅 立 叶 变 换 、 短 时 傅 里叶变换、 小波变换、Gabor 变换等。 但是, 这 些 分解方法的不足之处 是对信号的表示形式只能 是唯一的, 不可变的。 如果待分解信号的特征 与正交基不是完全相同,那么信号分解后 就不能稀疏地表示原信号。 假设 一个长为N 的待分解的信号 f , 若将这个信号在一组正交基上 进行正交分解, 那么构成这组基的

20、向量数目应为N,而由 于 基 的 正 交 性 , 所 构 成 的 信 号 表 示 不 是 稀 疏 的 。 而 信 号 的 稀 疏 表 示 则 是 将 信 号分 解 在 一 组 过 完 备 非 正 交 基 , 这 样 做 的 目 的 是 使 表 示 原 信 号 的 系 数 向 量 尽 量 含 有较 少 的 非 零 值 , 从而 让 信 号 的 表 示 形 式 最 为 简 洁 。 为 了 得 到 信 号 的 稀 疏 表 示 , 则必 须 使 用 非 正 交 基 , 从 而 可 从 实 质 上 降 低 信 号 处 理 的 复 杂 度 , 提 高 信 号 分 解 的 效率。因此 ,寻求新的信号稀疏表示

21、方法将会给信号的处理 带来深刻的变革和发展。 信 号 的 稀 疏 表 示 是 指 以 有 限 的 非 零 系 数 来 线 性 地 表达原 信号 的特点 , 这 些 非零 的 系 数 就 构 成 了 信 号 的 稀 疏 表 示 。 稀 疏 表 示 在 信 号 的 重 构 中 引 入 了 误 差 , 在 保证 非 零 系 数 的 个 数 比 原 始 信 号 的 采 样 点 少 的 情 况 下 来 最 小 化 地 逼 近 误 差 。 因 为 信号稀疏表示 表现出的优良特性, 文献1-5 指 出, 信号的稀疏表示已经被应用到信号 分 解 和 处理 等 多 个 领 域 , 比 如 信 号 去 噪 、 压

22、 缩 感 知 、 信 号 编 码 、 信 号 识 别 、 微弱信号提取 、时频分布等。 目 前 , 由 于 信 号 稀 疏 表 示 分 解 中 的 计 算 量 十 分 巨 大 , 难 以 在 实 际 中 得 到 应 用和 推 广 , 若 信 号 的 长 度 较 长 , 在 现 有 的 条 件 下 , 信 号 稀 疏 表 示 的 计 算 时 间 会 让 人难以忍受。参考文献6指出,当信号长度超过 1024 的 时候,信号稀疏表示的计算 量 将 相 当 巨 大 。 因 此 , 对 信 号 稀 疏 表 示 算 法 进 行 研 究 , 有 着 极 其 重 要 的 理 论 意义和非常广泛的应用价值。 1

23、.2 国内外研 究现状1 信号稀疏表示算法研究 7对信号稀疏表示算法 进行研究最早可以回溯到 1982 年,当时 Huber 在对统计 回 归 领 域 进 行 研 究 时 首先 提 出 了 一 种 投 影 追 踪 法 。 发 展 更 新 到 现 在 , 信 号 的 稀8疏表示已经形成了许多新的 不同的算法。其中最有代表性的是 Mallat 和 Zhang于 1993 年 在对小波理论进行分析的基础上,提出了一种新的信号 分解思想:即将信号分解在 过完备原子库上来代替信号在正交基上的分解, 这种分解 思想的提出,对信号的稀疏表示有着极其重要的意义 。国内外 对 信 号 稀 疏 表 示 的 研 究

24、 至 今 已经有 相 当 一 部 分 研 究 成 果 。 常 用 的 一 些9信 号 稀 疏 表 示 算 法 比如 基 追 踪 算 法 (basis pursuit,BP ) , 匹 配 追 踪 算 法10(matching pursuit ,MP)以及 MOF 算法method of frames 等等。如何实现算 法 的 快 速 计 算 , 降 低 算 法 的 复 杂 度 , 提 高 运 算 效 率 ; 如 何 选 择 原 子 或 者 向 量 集合 和 选择 怎 么 样 的 原 子 构 造 合 适 的 过完备 原 子 库 或者 级 联 字 典 ; 怎样 快速地 去 构造 分 解 向 量 和

25、 过 完 备 原 子 库 ; 或 者 确定 哪 一 类 信 号 适 合 用 于 哪 一 类 原 子 库 可以 获得 比 较 好 的 稀 疏 表 示 的 效 果 , 这 些 问 题 一 直 是 信号 稀疏 表示 领域 的 研 究 热 点 。 总的来讲, 对信号稀疏表示的研究主要从以下两个方面展开: (1)信号稀疏表示的分解算法的研究 11Chen 于 1995 年首先提出了基追踪算法(basis pursuit,BP ) ,该算法的基本思想是将最小化l 范数的问题转变为最小化l 范数的线性规划问题进行求解, 从0 1而 使 得 问 题 的 求 解 变 成 了 一 个 在 没 有 约 束 的 的

26、情 况 下 的 优 化 问 题 。 但 是 基 追 踪 算法 存 在 一 个 不 足 之 处 就 在 于 它 具 有 高 复 杂 度 的 计 算 , 尤 其 是 在 对 信 号 进 行 重 构 的时候。 于是, 在小波分析的基础上,Mallat 和 Zhang 利用平方可积空间中基本函数的 平 移 、 调 制 和 尺 度 等 参 数 的 变 换 构 造 出 具 有 时 频 特 性 的 过 完 备 原 子 库 , 并 且 提12-13出 了 匹 配 追 踪 方 法matching pursuit,MP 。 匹 配 追 踪 算 法 的 基 本 思 想 是 从一 个 给 定 的 过 完 备 原 子

27、库 中 选 择 最 匹配 原子, 然后 从 信 号 残 余 中 减 去 其 在 该 最 匹配 原 子 上 的 投 影 , 获 得 新 的 信 号 残 余, 这 个 过 程 不 断 地 迭 代 进 行, 直 到 残 余 信 号 的能量小于 设定的阈值或满足其他设定的停止条件为止。Mallat 和 Zhang 提出的算 法 一 般 被 称 作 基 本 的 匹 配 追 踪 方 法 。 而 这 种 基 本 的 匹 配 追 踪 算 法 也 存 在 一 个 不足之处,就是所选的最佳原子可能是己经被选择的原子。 14 15Pati 及 Davis 等人在对匹配追踪算法进行分析研究的基础上提出用 Gram16

28、-17?Schmidt 正 交 化 过 程 将 投 影 方 向 正 交 化 来 改 进 匹 配 追 踪 算 法 的 逼 近 效 果 。这 种 正 交 匹 配 追 踪 算 法 只 需 要 进 行 有 限 次 的 迭 代 就 可 以 形 成 收 敛 , 这 与 非 正 交 追踪 相 比 收 敛 速 度 有 了 一 定 的 提 高 。 在 进 行 迭 代 计 算 的 前 几 次 , 基 本 的 匹 配 追 踪 算法在寻求最佳原子时往往是挑选近似正交的向量, 因此 Gram-Schmidt 正交化几乎是不必要的, 因为这个 时候正交匹配追踪和非正交匹配追踪的迭代逼近差异不大。2 中南民族大学硕士学位论

29、文 但 随 着 迭 代 进 行 到 一 定 的 次 数 时 , 正 交 匹 配 追 踪 算 法 得 到 的 残 余 信 号 能 量 将 比 基本的匹配追踪算法下降得更快。 Natarajan 等 人 在 对 正 交 匹 配 追 踪 算 法 进 行 研 究 的 基 础 上 进 一 步 进 行 改 进 提18-20出了顺序递归匹配追踪算法 Order Recursive Matching Pursuit ,ORMP 。它相对于OMP 算法改进的地方是ORMP 算法是在每一步进行迭代找到内积的最大值前进行调整里选择最佳原子。 21为了进一步提高计算速度,Cotter 等人 通过对 匹配追踪算法、 正

30、交匹配追踪 算 法 、 顺 序 递 归 匹 配 追 踪 算 法 等 三 种 前 向 的 纳 入 型 算 法 的 计 算 复 杂 性 进 行 了 较22为详细的比较和分析,在此基础上提出了一种新的改进算法 ?反向删除算法 。反 向 删 除 算 法 与 匹 配 追 踪 算 法 的 不 同 之 处 是 最 初 始 入 选 原 子 从 整 个 过 完 备 原 子 库开始,选择需要删掉的原子是利用1 范数最小准则来确定的。 pJaggi 在 文 献23 中 在 对 匹 配 追 踪 的 一 步 优 化 这 一 准 则 进 行 分 析 的 基 础 上 结合局部相似性 , 一致性和匹配性的概念提出了HRP 算

31、法。HRP 算法的主要思想是要求 形 成 过 完 备 原 子 库 的 原 子 具 有 多 分 辨 的 特 性 , 并 且 在 每 一 步 的 迭 代 过 程 中 定 义当 前 残 余 信 号 与 当 前 尺 度 原 子 的 相 似 性 需 要 原 子 的 尺 度 更 加 精 细, 因 此 具 有 较 高的分辨率,并且获得的信号内部结构就会更加精准, 但这 种算法要求原子库具有特殊的结构 ,所以也就同时提高了计算的复杂性。 文献24中 Coifman 等人将余弦包和小波包等几类原子库 进行结合,提出了“ 最 优 正 交 基 ” 的 概 念 。 其 主要 思 想 是 从 原 子 库 中 的 原 子

32、 所 构 成 的 所 有 正 交 基 中选 择 嫡 最 小 的 正 交 基 来 进 行 信 号 表 示 , 但 是 在 一 些 特 定 的 情 况 下 , 由 于 其 合 成 观测信号的原子并不能组成正交基,因而这种算法也存在一定的局限性。 文献25介绍了一种FOCUSS 算法, 这种算法是Rao 和Borodnitshy 等人在对生 物 医 学成像 的 角 度 求解 时 利 用 最小l 范数 的求解 为 基 础提出 的 。FOCUSS 算法与2带限信号重构中的迭代滤波思想有非常多的相似之处。 26在内积快速运算方面,B.Jeon 和S.Oh 经过研究 分析得出在原子搜索过程中 , 并 不 要

33、 计 算 全 部 内 积 , 可 以 利 用 向 量 的 范 数 比 较 来 降 低 运 算 的 复 杂 度 , 实 验表 明 该 方 法 可 以 减 少 一 部 分 内 积 运 算 。 但 是 内 积 的 优 化 通 常 很 难 保 证 算 法 的 收 敛速 度 和 算 法 的 性 能 和 精 度 同 时 提 高 , 往 往 是 提 高 收 敛 速 度 就 会 影 响 算 法 的 重 构 精度,所以在实际情况中往往需要根据不同的应用从而选取不同的方法。 为了实现算法的收敛速度和性能精度两者之间的折中。E.Cottcr 和D.Rao 等2728提 出 树 状 搜 索 策 略 , 树 状 搜 索

34、 方 法 的 核 心 理 论 是 并 从 次 优 原 子 库 中 选 择 原 子来 代 替 从 一 个 最 优 原 子 库 中 选 择 原 子 , 通 过 这 一 方 式 来 平 衡 算 法 的 复 杂 度 和 重 构精度。 文献29介绍了一种在Schwarz 不等式的基础上,用简单的距离比较来搜索最3 信号稀疏表示算法研究 佳原子的方法,这种方法是由 S.Jun 和 B.Jeon 共同设计提出的,该算法执行的速度快慢取决于获得内积最大值的快慢。而该算法的主要优点是能 贾云得在文献30 中提出在 信息 编码 中 对能量优先的原子搜索策略进行 分 析的 基 础 上 , 提 出 了 一 种 改 进

35、 的 全 面 搜索 算法 和 加 权 能 量 优 先 搜 索 算法 , 这 种 方 法在一定的情况下也可以适当地提高搜寻最佳原子的速度。 最近几年,Starck 等人经过研究分析提出了另外一种新的用于信号稀疏表示的分离方法 ? 形态成分分析法Morpho-logical Component Analysis ,MCA3132。 这 种 方 法 的 基 本 思 想 表 述 如 下 : 假 设 对 于 存 在 于 混 合 信 号 中 任 意 的 一 个 单独 的 源 信 号 , 都 存 在 着 唯 一 的 能 够 对 这 个 单 一 的 信 号 源 稀 疏 表 示 的 原 子 库 , 并 且这 个

36、 原 子 库 对 于 混 合 信 号 中 的 其 他 源 信 号 却 不 能 进 行 稀 疏 表 示 , 然 后 再 利 用 追 踪算 法 来 搜 寻 最 佳 原 子 , 就 可 以 产 生 一 个 比 较 理 想 的 信 号 分 离 效 果 。 在 信 号 和 图 像的 稀 疏 表 示 领 域 中 , 形 态 成 分 分 析 法 是 一 种 比 较 新 的 稀 疏 表 示 方 法 , 由 于 他 对 混合 信 号 进 行 稀 疏 表 示 有 一 定 的 效 果 , 它 的 提 出 便 得 到 了 很 多 这 一 领 域 研 究 者 的 关注 , 它 的 应 用 范 围 也 在 不 断 的 扩

37、 展 , 它 的 不 足 之 处 是 由 于 它 的 理 论 面 貌 比 较 新 ,同 时 在 实 际 应 用 中 有 一 定 的 局 限 性 , 这 种 形 态 成 分 分 析 的 方 法 还 存 在 着 各 种 问 题值得研究者们进行进一步的分析研究。在形态成分分析算法的基础上,Boin 等人将其扩展到多通道数据的情况中,提 出 了 两 种 新 的 算 法 ?MMCA MultichannelMorpholgical Component 33-35Analysis 和GMCA Generalized MCA方法 。MMCA 方法实际上是对MCA 方法的 一 种 改 进 , 这 种 改 进

38、是 建 立 在 在 多 通 道 数 据 的 基 础 上 。 研 究 者 们 的 实 验 结 果 表明 , 较 多 的 数 据 能 够 更 好 地 提 高 信 号 的 分 离 能 力 , 并 且 对 算 法 的 性 能 有 一 定 的 改善。 上 面 的 方 法 都 是 在 给 定 的 待 分 解 信 号 是 确 定 信 号 的 情 况 下 , 而 在 实 际 的 应 用和 测 试 的 时 候 , 待 分 解 信 号 有 时 候 并 不 是 确 定 的 信 号 而 是 随 机 信 号 。 对 随 机 信 号进 行 稀 疏 表 示 采 用 的 基 本 算 法 与 上 面 介 绍 的 对 于 确 定

39、 信 号 的 稀 疏 表 示 算 法 基 本 是相 同 的 , 但 是 不 同 之 处 在 于 观 测 模 型 发 生 了 变 化 , 因 此 对 随 机 信 号 进 行 稀 疏 表 示也 就 有 些 不 同 之 处 。 上 面 所 提 到 的 匹 配 追 踪 算 法 等 一 些 吐 故 纳 新 类 型 的 算 法 , 一般采用的是信号的残余能量控制 准则。 (2)原子和过完备原子库的构造 信 号 稀 疏 表 示 算 法 的 另 一 个 热 点 领 域 就 是 原 子 和 过 完 备 原 子 库 的 构 造 。 研 究者们常用的原子库有: 由时移参数、频移参数确定的双参数原子库, 由时移参数、

40、频 移 和 参 数 尺 度 因 子 确 定 的 三 参 数 原 子 库, 以 及 由 时 移 参 数 、 频 移 参 数 、 尺 度 因子和调频率确定的四参数原子库。这些原子库的形成分别对应 Gabor 变换、傅里叶变换和 Chirplet 变换。 在原子库的设计和构造方面, 由于信号稀疏表示算法的性 能 是 由 原 子 库 中 的 原 子 与 待 分 解 信 号 的 相 关 程 度 来 决 定 的 , 因 此 , 如 果 设 计 出4 中南民族大学硕士学位论文 的 过 完 备 原 子 库 与 待 分 解 信 号 的 相 关 程 度 越 高 , 便 可 以 用 越 少 的 向 量 来 逼 近

41、原 信号 , 也 就 是 说 就 有 更 快 的 收 敛 速 度 , 这 样 一 来 就 能 够 得 到 较 高 的 表 示 精 度 或 是 付出 较 少 的 计 算 代 价 。 因 此 如 何 构 建 这 样 的 过 完 备 原 子 库 或 者 快 速 地 形 成 原 子 , 便成为信号稀疏表示算法研究的另一个重要问题 研究者们在进行信号稀疏表示的研究时最为常用的就是 Gabor 原子库。文献36介绍了 Gabor 函数最早是由 R.Neff 等在 1997 年提出将其作为信号分解的原子库, 并且在 2002 年对原子库进行了改进, 构造二维可分的 Gabor 函数作为原子库,明显地提高了计

42、算效率。在此基础上,Chen 和 Qian 通过研究信号的 Wigner分布,于 1994 年利用高斯函数的平移、 调制和尺度变换构造 出相应的时频词典原37子库 ,增加了原子库的过完备性。 Gabor 函数构成的过完备原子库存在一个不足之处是当信号重构时可能会 引起震荡, 于 是 Chou 等引入了量化学习法通过学习新的原子库来解决这种重构中的震荡问题。 在此基础上, 文献38介绍了B.Maeq 和C.Vleeschouwer 于1998 年提出了一种与 Gabor 原子库性能相当的原子库即子带字典,在一定情况下用这种原子库进行信号的稀疏表示有着更小的运算量。 文献39介绍了针对过完备原子库

43、原子数目过大的问题,Qiao W 等人提出在逼 近 误 差 给 出 的 情 况 下 , 可 以 将 稀 疏 分 解 过 程 中 的 比 特 数 进行 最 小 化 处理 从 而 简化原子库的大小。 40P.Vandergheynst 等人 对 Gabor 函数进行改进,加入它的导数得到新的 原41子库, 在对图像处理时有较好的效果。 而 L.Granai 等人 则在此基础上融入高斯函数得到新的原子库,在分解运算中有着更好的收敛效果。 近年来,随着信号的稀疏表示在信号处理等方面的研究和应用不断扩展,国际 信 号 处 理 方 面 的 研 究 学 者 们 对 这 个 领 域 也 十 分 关 注 , 比

44、 如 近 年 来 国 际 图 像 处 理年会等一些会议(IEEE ICIP)都对信号的稀疏表示方面的研究开展了专项讨论,一 些 著 名 的 通 信 类 期 刊 也 以 专 对 此 进 行 了 专 题 报 道 。 而在 国内 , 由 于 对 信 号 的 稀疏表示研究起步比较晚,研究进展 比较有限。2005 年国家自然科学基金对信号的稀 疏 表 示 这 一 研 究 热 点 进 行 了 两 项 专 项 资 助, 使 得 研 究 者 们 在 这 方 面 的 研 究 力 度开 始 增 加 。 在 自 然 图 像 的 稀 疏 编 码 以 及 雷 达 成 像 处 理 等 方 面 国 防 科 技 大 学 等

45、高 校取 得 了 一 定 的 成 果 ; 将 信 号 的 稀 疏 表 示 用 在 图 像 压 缩 和 图 像 的 去 噪 等 方 面 西 南 交通 大 学 等 高 校 也 取 得 了 一定 的 进 展 ; 在 盲 信 号 处 理 方 面 广 州 大 学 等 高 校 也 有 一 定的 进 步 等 等 。 比 较 有 代 表 性 的 应用 比 如 王 成 梅 等 人 提 出 的 改 进 的 雷 克 子 波 原 子 库在 对 地 震 信 号 进 行 稀 疏 分 解 的 时 候 有 着 非 常 好 的 效 果 , 但 其 应 用 范 围 有 一 定 的 局限性。 综 上 所 述 , 由 于 信 号 的

46、 稀 疏 表 示 具有 能 够 在 一 定 程 度 上 比 较 好 地 表 达 原 始 信号 的 基 本 特 征 , 从 而 对 信 号 的 稀 疏 表 示 的 研 究 和 应 用 也 就 日 益 广 泛 。 信 号 的 稀 疏5 信号稀疏表示算法研究 表 示 理 论 目前 仍 处 于 发 展 的 初期 , 对于 原子 过 完 备 原 子 库 的 快速 形 成 、 提高 分解算法的 效率 等 方 面 还 有 很 多 工 作 要 做 。 信 号 的 稀 疏 表 示 发 展 至 今 已 有 一 些 不 同 的算法, 综 合 考 虑 算 法 在 计 算 复 杂 度 和 逼 近 效 果 方 面 的 两

47、 个 重 要 因 素 , 以 贪 婪 算 法为 核 心 的 匹 配 追 踪 算法 相比 其 他 的 算法 有 着 明 显 的 优 越 性 , 也 是 目 前 研 究 者 最 常采用的算法。 采 用匹配追踪算法 来对 信号 进行 稀疏表示, 在一定程度上 能够得到比较好的应 用 。 但 这 种 方 法 也 存 在 一 些 缺 点: 最 主 要 的 问 题 是 计 算 量 过 于 庞 大 。 在 对 信 号的 每 一 步 分 解 寻 求 最 佳 原 子 的 过 程 中 , 都 需 要 进 行 大 量 的 内 积 运 算 , 从 而 决 定 应该 选 出 原 子 库 的 哪 一 个 向 量 来 做

48、分 解 , 分 解 的 每 一 步 都 要 计 算 残 余 信 号 在 过 完 备原 子 库 中 每 一 个 原 子 上 的 投 影 ; 在 过 完 备 原 子 库 的 形 成 过 程 中 , 由 于 过 完 备 原 子库 的 原 子 数 目 相 当 巨 大 , 这 就 造 成 了 其 分 解 过 程 中 的 计 算 量 十 分 巨 大 , 高 复 杂 度的计算 代价 成 为 了 信 号 的 稀 疏 表示 在 实 际 的 研 究 应 用 中 难 以 展 开 的 瓶 颈 。 因 此 ,本文 针 对 如 何 简 化 信 号 稀 疏 表 示 中 的 内 积 运 算 , 寻 求 更 佳 的 向 量 组

49、 合 来 代 替 过 完备原子库 这两个方面的问题进行研究。 1.3 论文主要 工作本 文 主 要 对 压 缩 感 知 理 论 中 的 信 号 稀 疏 表 示 算 法 进 行 了 探 讨 与 研 究 , 对目前信 号 稀 疏 表 示 算 法 及 常 用 的 过 完 备 原 子 库 进 行 了 系 统 的 分 析 、 归 纳 和 总 结 。 在 对信 号 匹 配 追 踪 算 法 进 行 深 入 研 究 的 基 础 上 , 针 对 现 有 匹 配 追 踪 算 法 中 存 在 的 高 复杂 度 计 算 的 问 题 , 提 出 了 一 种 基 于 快 速 互 相 关 运 算 的 信 号 稀 疏 表 示

50、 算 法 ; 针 对 原子 和 过 完 备 原 子 库 形 成 的 问 题 , 提 出 了 用 稀 疏 框 架 代 替 过 完 备 原 子 库 作 为 分 解 函数进行信 号的稀疏分解。主要的研究内容如下: (1 ) 对信号的匹配追踪算法进行了深入分析与研究, 仿真分析了信号稀疏表示与重构。 (2 ) 针对匹配追踪算法的计算量过于庞大问题, 提出了一种 基于快速互相关运 算 的 匹 配 追 踪 算 法 。 该 算 法 的 主 要 思 想 是 : 将 稀 疏 表 示 过 程 中 最 消 耗 时 间 的 N次 内 积 运 算 转 化 成 一 次 互 相 关 运 算 , 由 于 互 相 关 的 结

51、果 存 在 峰 值 特 性 , 对 互 相 关结果 进 行 多 个 点 的 跳 跃 计 算 , 首先 找 出 最 大 值 存 在 的 一 个 比 较 小 的 区 间 , 然 后 再比较 小 区 间 内 各 点 的 互 相 关 运 算 结 果 , 找 出 最 大 值 点 位 置 和 最 大 值 , 这 样 一 来 ,就极大地 减少了计算的点数,加快了计算的速度。 (3 ) 针对原子和过完备原子库形成这一问题, 并结合 不同的信号特点在不同的原子库上进行信号的稀疏分解并比较仿真结果,引入框架理论,通过 STF 方法形 成 一 种 稀 疏 框 架 , 并 用 其 代 替 过 完 备 原 子 库 进

52、行 信 号 的 稀 疏 分 解 , 由 于 框 架 的稀 疏 性 , 极 大 地 降 低 了 计 算 复 杂 度 。 实 验 证 明 , 在 一 定 情 况 下 选 取 稀 疏 框 架 代 替过完备原子库,能够在保证算法精度的情况下降低运算量提高计算速度。6 中南民族大学硕士学位论文 1.4 论文 组织 结构 本论文总共分为四章,组织结构如下: 第 1 章 介绍论文的研究背景、 国内外研究现状、 阐述课题的研究目的和意义。对信号稀疏表示算法进行了详细的研究现 状分析。 并介绍了本 论 文的主要工作及组织结构。第 2 章 描述信号稀疏表示算法,并在其基础上,针对信号稀疏分解过程中存在的大量的内积运算问题,提