稀疏表示的分段匹配寻踪方法

论文摘要

近年来,在信号处理领域中,随着各种变换域处理技术(如傅立叶变换、小波变换、奇异值分解等)的发展,信号的稀疏表示理论逐渐成为备受关注的课题,并被广泛应用于信号去噪、数据压缩、特征提取、模式分类和盲源分离等领域。特别是在高维信息处理方面,稀疏表示理论直接催生了压缩感知理论,而压缩感知理论是信息论中自香农采样定理以来最具革新意义的理论成果。因此,稀疏表示理论的研究工作对信号处理理论的进一步发展具有重要的基础性作用。本文重点研究信号在过完备系统中的稀疏表示方法。给定一个由一组基本信号(原子)组成的字典和一个可以在中稀疏表示的输入信号(即可用中很少的几个原子的线性组合来表示),寻求在中的最稀疏表示,即是求解优化问题:min ? . .。被证明是NP难的,但近年来的研究成果表明,当足够稀疏,而的相干参数较小时,一些寻踪方法,如基寻踪、正交匹配寻踪,可以逼近或精确求得( )的解,这一性质被称为精确重构。现有的大多数寻踪方法由于受字典相干性的影响,重构能力十分有限:或者对的稀疏性要求较高,或者计算复杂度太高。为了改进这一不足,本文基于于分段匹配寻踪方法进行了如下几方面的研究:(1)研究了精确重构条件。现有的许多寻踪方法的性能之所以受字典相干性的影响较大,主要原因在于其理论基础是? /?等价条件,即优化问题:min ? . .的解等价于( )解的充要条件,而该条件一般以字典的相干参数为研究对象。为摆脱字典相干性的限制,第二章基于框架理论,给出了? /?等价条件,即优化问题:min ? . .的解等价于( )解的充要条件。由于的最小?范数解只与字典中各原子的线性相关性有关,因此,基于? /?等价条件的寻踪方法不受字典相干性的影响。如果分段匹配寻踪方法历次迭代选取的原子集Γ满足? /?等价条件,则可精确求解( ),这样的Γ被称为依信号伪框架的。(2)研究了现有的各种贪婪寻踪方法的原子选取策略。由于依信号伪框架的字典Γ的构造主要依赖于原子选取策略,因此原子选取策略的优劣直接影响了寻踪方法的性能。第三章首先分析了现有的各种纯贪婪寻踪方法的原子选取策略及它们之间的内在联系,得到了一个新的结论:在一定条件下,基寻踪问题可通过一系列转换,最终用匹配寻踪方法来求解;其次分析了现有的各种分段匹配寻踪方法的原子选取策略,并指出了这些寻踪方法对字典相干性的依赖较弱,但其阈值参数难以控制。(3)为克服分段匹配寻踪方法的阈值参数难以确定的困难,第四章针对孤立奇异性信号和多尺度字典,提出了分段脊寻踪方法,其核心思想是:提取孤立奇异性信号在小波变换域的脊,然后选取那些落在脊上的原子组成Γ,最后求输入信号在Γ中的正交投影。可以证明Γ是依信号伪框架的,由? /?等价条件可知分段脊寻踪的结果必然是最小?的;又由于分段脊寻踪的原子选取是基于小波脊算法的,其速度优于现有的寻踪方法,数值实验的结果也表明了这一点。(4)为进一步解决分段匹配寻踪方法针对于一般的信号和字典的阈值参数难以确定的问题,第五章提出了基于局部竞争的分段正交匹配寻踪方法,其核心思想是:字典中与信号的内积较大的若干个原子,以及与它们在空域或频域上邻近的原子,可能是同等重要的,每次迭代选取两个或多个由这些原子组成的字典模式,并通过局部竞争来选取最优模式,从而避免那些与信号内积较小的原子总是不能入选的情形;同时,为避免引入冗余的原子,采取了原子淘汰算法。基于局部竞争的分段正交匹配寻踪方法虽然一次迭代的计算开销较大,但其总的迭代次数和计算开销比一般的寻踪方法少,数值实验表明其保稀疏性、抗相干性和收敛速度都优于现有的方法。(5)由于各种分段匹配寻踪方法都是基于正交匹配寻踪的,因此正交匹配寻踪的求解方法值得关注。第六章回顾了现有的求解正交匹配寻踪的快速迭代方法,拓展了共轭梯度寻踪方法,并比较了各种方法单次迭代所需的计算资源。然而,当Γ欠秩时,现有的各种求解正交匹配寻踪的迭代方法不能用于求解分段匹配寻踪的子问题,而经典的求解欠秩系统的迭代方法,如SYMMLQ、MINRES、LSQR等,一般不具保稀疏性。如何快速迭代求解分段匹配寻踪的子问题是尚待解决的问题。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 从正交基到过完备字典
• 1.2 稀疏表示的寻踪家族
• 1.2.1 寻踪方法的目标
• 1.2.2 贪婪方法
• 1.2.3 凸松弛方法
• 1.3 重大理论成果
• 1.3.1 精确重构条件
• 1.3.2 压缩感知
• 1.4 仍然存在的问题
• 1.5 关于本文
• 1.5.1 研究目标
• 1.5.2 主要工作
• 1.5.3 符号约定
• 1.5.4 可重现的数值实验
• 第二章 字典的框架分析
• 2.1 框架与框架方法
• 2.2 字典的框架描述
• 2.2.1 基于框架与秩的字典分类
• 2.2.2 字典的子框架
• 2.2.3 合成字典的框架
• 2.3 伪框架字典与（?） /（?） 等价条件
• 2范数解'>2.4 伪逆与最小l₂范数解
• 2.4.1 基于Penrose 方程的Λ-逆
• 2.4.2 满秩字典
• 2.4.3 紧框架字典
• 2.4.4 欠秩字典与病态字典
• 2.5 最大化子框架方法
• 2.5.1 子框架的选取
• 2.5.2 算法与实现
• 2.5.3 病态子框架
• 2.5.4 存在的问题
• 2.6 小结
• 第三章 贪婪方法的原子选取策略
• 3.1 纯贪婪寻踪方法
• 3.1.1 正交匹配寻踪
• 3.1.2 高分辨寻踪
• 3.1.3 多面体面寻踪
• 3.1.4 方向寻踪
• 3.1.5 后向贪婪算法
• 3.2 基寻踪及各种纯贪婪寻踪方法之间的联系
• 3.3 分段匹配寻踪方法
• 3.3.1 分段正交匹配寻踪
• 3.3.2 正则化正交匹配寻踪
• 3.3.3 分段弱梯度寻踪
• 3.4 小结
• 第四章 孤立奇异性信号的分段脊寻踪
• 4.1 预备定义与定理
• 4.1.1 奇异性检测与小波变换模极大
• 4.1.2 影响锥与孤立奇异性信号
• 4.2 分段脊寻踪
• 4.2.1 孤立奇异信号的多尺度分析
• 4.2.2 分段脊寻踪算法
• 4.3 实验与分析
• 4.3.1 TwinPeaks 信号
• 4.3.2 MultiPeaks 信号
• 4.4 小结
• 第五章 基于局部竞争的分段正交匹配寻踪
• 5.1 基于局部竞争的分段正交匹配寻踪算法
• 5.1.1 字典模式的建立与筛选
• 5.1.2 字典模式内部的竞争：原子的淘汰
• 5.1.3 稀疏性的度量与比较
• 5.1.4 算法描述
• 5.2 原子淘汰算法的改进
• 5.2.1 面向满秩字典的后向贪婪算法中的伪逆的迭代计算方法
• 5.2.2 面向奇异字典的后向贪婪算法
• 5.3 实验与分析
• 5.3.1 MP 和OMP 的反例
• 5.3.2 孤立奇异性信号
• 5.3.3 正弦信号
• 5.3.4 Carbon 信号
• 5.4 小结
• 第六章 正交匹配寻踪的迭代计算方法
• 6.1 符号约定
• 6.2 矩阵分析
• 6.2.1 原子正交化方法
• 6.2.2 Cholesky 因子化方法
• 6.2.3 QR 因子化方法
• 6.3 共轭梯度方法
• 6.3.1 共轭方向方法
• 6.3.2 标准的共轭梯度方法
• 6.3.3 Grochening 的共轭梯度方法
• 6.4 共轭梯度寻踪
• 6.4.1 基本原理
• 6.4.2 拓展与改进
• 6.5 OMP 的各种迭代计算方法的比较
• 6.6 分段匹配寻踪的迭代计算方法
• 6.6.1 求解欠秩系统的迭代方法
• 6.6.2 数值实验：各种迭代方法的保稀疏性比较
• 6.7 小结
• 第七章 结论与展望
• 7.1 结论
• 7.2 展望
• 参考文献
• 攻读博士学位期间取得的研究成果
• 致谢