（信号与信息处理专业论文）基于压缩感知的语音稀疏基和投影矩阵构造技术的研究.pdf

南京邮电大学学位论文原创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 本人学位论文及涉及相关资料若有不实，愿意承担一切相关的法律责任。 南京邮电大学学位论文使用授权声明 本人授权南京邮电大学可以保留并向国家有关部门或机构送交论文的复印件和电子文 档；允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索； 可以采用影印、缩印或扫描等复制手段保存、汇编本学位论文。本文电子文档的内容和纸质 论文的内容相一致。论文的公布（包括刊登）授权南京邮电大学研究生院（筹）办理。 涉密学位论文在解密后适用本授权书。 研究生签名：_ 日期：_ 研究生签名：_ 导师签名：_ 日期：_ 学科 、专业：工 学 、信号与信息处理 研 究 方 向：语音处理与现代语音通信 作 者：唐 力 指导教师：杨 震 教授 题 目：基于压缩感知的语音稀疏基和投影矩阵构造技术的研究 英文题目：research on speech sparse basis and projection matrix based on compressed sensing 主 题 词：压缩感知；语音信号；稀疏表示；k-svd；k-lms keywords: compressed sensing; speech signal; sparsity; k-svd; k-lms 项目资助：国家自然科学基金“基于 lp 优化的语音压缩和编码技术的研 究” ，项目编号 60971129 国家 973 计划“物联网混杂信息融合与决策研究” ，项目编号 2011cb302903 南 京 邮 电 大 学南 京 邮 电 大 学 硕士学位论文摘要硕士学位论文摘要 南 京 邮 电 大 学南 京 邮 电 大 学 硕士学位论文摘要硕士学位论文摘要 南京邮电大学硕士研究生学位论文 摘要 i 摘摘要要 语音通信已经成为人类生活中必不可少的一部分，语音是模拟信号，需要经过数字化处 理才能在数字通信系统中进行加工处理。在信号处理中数字化的第一步便是采样，一般遵循 奈奎斯特采样定理对语音信号采样。但是奈奎斯特采样的速率较高，采集的信号中具有较多 冗余的信息。所以为了降低采集后的数据量，2004 年 daonodo 与 candes 等人提出了压缩感 知理论，压缩感知在对稀疏信号进行采样的同时，也对信号进行了压缩。采用压缩感知技术 对语音信号进行处理，将大大降低传输过程中所需的信息量。 压缩感知的前提是信号具有稀疏性，但是语音信号在常规变换域中的稀疏度不够理想， 所以在对语音信号进行压缩感知投影观测之前，首先需要对语音信号在稀疏变换基上的稀疏 表示进行深入研究。因此，为了实现语音信号的压缩感知采样，本文主要研究了语音信号的 近似稀疏性和稀疏表示形式，在现有传统正交基的基础上寻找稀疏字典的训练算法，从而使 得原始信号在训练过的稀疏变换基上可以更加稀疏地表示。本文的主要工作和创新有：1)在 语音信号压缩感知技术中常常对投影观测矩阵进行自适应的选取，本文将信号的投影残差加 入到自适应投影观测矩阵的选取中，改进了针对信号能量进行的自适应投影观测算法；2)将 k-svd 训练算法和小波分解后的特性联合考虑，对小波分解后的低频系数采用 k-svd 算法， 从而降低了稀疏字典训练算法的复杂度；3)针对 k-lms 稀疏字典训练算法中 lms 分解过程 采用固定的步长因子，容易带来较大的稳态误差这个问题，本文提出将前两次稀疏表示过程 中的误差引入到步长因子的计算中， 对 k-lms 训练算法进行改进， 从而得到较好的重构性能。 在迭代过程的初始阶段，采用较大的步长因子，随着迭代次数的增加逐步减小步长因子的大 小，降低稀疏表示过程中的稳态误差，从而可以准确恢复出原始语音。 在文章的末尾，对全文进行了总结，并且提出了语音压缩感知有待解决和改进的几个方 向。 关键词：压缩感知；语音信号；稀疏表示；k-svd；k-lms 南京邮电大学硕士研究生学位论文 abstract ii abstract communication has played an important role in our daily life. the speech signal is an analog signal which has a continuous waveform in the time-domain. it must be digitalized before being processed by the computer. the first step of digitalization is sampling. nyquist sampling theory is usually adopted in the digitalization. but it would bring about a large number of data, and cost much resource in the transmitting and storage. in order to reduce the amount of data, daonodo and candes have proposed the compressed sensing. the theory proves that the sampling and compression are working simultaneously which can reduce the amount of data in the transmitting and storage. if a signal can be represented sparsely, it can adopt compressed sensing. however, the speech signal hasnt enough sparsity in the traditional basis. we should find a fit basis in which the signal can be represented sparsely, and then be projected into a projection matrix. there are three main points in the thesis. at first the residual of the signal can be considered into choosing an adaptive projection matrix according to the energy distribution of the signal. secondly, based on the characteristics of coefficients of speech signal at low frequency and high frequency after wavelet transformation, the trained overcomplete dictionary using k-svd is applied to the low frequency coefficients after wavelet transformation to decrease the computation of the sparse decomposition. lastly, the variable step has been adopted into the k-lms to decrease the error rate. at the beginning of the iterations, the step is large to speed up the rate of convergence. as the number of iterations increase, the step is reduced to get a low error rate. in the end of the thesis，we conclude the paper as well as the future direction of research and improvement of compressed sensing in speech signal. key words: compressed sensing; speech signal; sparsity; k-svd; k-lms 南京邮电大学硕士研究生学位论文 目录 iii 目录目录 摘要 . i abstract . ii 目录 . iii 缩略语 . v 第一章 绪论 . 1 1.1 课题研究背景 . 1 1.2 论文的主要内容和安排 . 3 第二章 压缩感知的基本理论 . 5 2.1 压缩感知的基本理论 . 5 2.1.1 信号的稀疏表示 . 5 2.1.2 信号的观测投影 . 7 2.1.3 信号的重构 . 10 2.2 仍然存在的问题 . 13 2.3 本章小结 . 13 第三章 语音信号的压缩感知 . 15 3.1 语音的产生模型 . 15 3.1.1 语音信号的产生原理 . 15 3.1.2 离散时域的语音生成模型 . 15 3.2 传统语音的采样及处理过程 . 16 3.3 语音的稀疏表示 . 17 3.4 语音信号的投影观测 . 23 3.5 重构语音信号的性能评价方法 . 25 3.6 本章小结 . 27 第四章 基于小波分解和 k-svd 的自适应压缩感知 . 28 4.1 矢量表示的 k-means 算法 . 28 4.2 k-svd 训练算法 . 29 4.3 语音信号的小波分解 . 31 南京邮电大学硕士研究生学位论文 目录 iv 4.3.1 连续小波及其变换 . 31 4.3.2 语音信号的离散小波变换 . 32 4.4 基于小波分解的语音稀疏分解及其压缩感知 . 33 4.5 性能分析 . 35 4.6 本章小结 . 40 第五章 基于 k-lms 的稀疏字典训练算法 . 41 5.1 最小均方(lms)算法原理 . 41 5.1.1 最小均方误差(mmse)准则 . 41 5.1.2 最速下降法 . 42 5.1.3 最小均方(lms)算法 . 43 5.2 一种基于 k-lms 的稀疏字典训练算法 . 44 5.3 基于变步长的 k-lms 稀疏字典训练算法 . 45 5.4 性能分析 . 47 5.5 本章小结 . 51 第六章 总结和展望 . 52 6.1 论文的主要工作 . 52 6.2 下一步工作展望 . 53 致谢 . 54 参考文献 . 55 攻读硕士学位期间发表的论文 . 61 南京邮电大学硕士研究生学位论文 缩略语 v 缩略语缩略语 bp basis pursuit 基追踪 cosamp compressed sampling matching pursuit 压缩采样匹配追踪 cs compressed sensing 压缩感知 dct discrete cosine transform 离散余弦变换 lms least mean square 最小均方算法 mmse minimum mean square error 最小均方误差 mof method of frame 框架方法 mp matching pursuit 匹配追踪 omp orthogonal matching pursuit 正交匹配追踪 rip restricted isometry property 约束等距性条件 romp regularized orthogonal matching pursuit 正则正交匹配追踪 samp sparsity adaptive matching pursuit 稀疏自适应匹配追踪 stomp stage-wise omp 分段正交匹配追踪 svd singular value decomposition 奇异值分解 南京邮电大学硕士研究生学位论文 第一章 绪论 1 第一章第一章 绪论绪论 在现代社会中，通信与信息处理技术随着人类的进步而快速发展，并且不断推动着人类 社会的发展和进步。可以说，通信是人类日常语言、文字、图像、数据、符号等信息的传输 与交换手段。即通信是将信息从一端准确传输到另一端的过程。在通信系统中可以把信源分 成两大类：模拟信号和数字信号。例如，由话筒输出的语音信号是模拟信号，而计算机可以 处理的数据属于数字信号。由于实际生活中语音的模拟化和信号处理工具的数字化，需要借 助于计算机处理信息，所以我们必须先对信号进行采样，从模拟信源中获取数字信息。即数 字化的首要步骤就是对信号进行采样。在日常信号处理中，我们大多遵循奈奎斯特采样定理 对原始模拟语音信号进行采样。 由于奈奎斯特采样是按照信号最高频率的 2 倍对信号进行采样，其采样速率较高，采集 的信息中冗余性较大，所以为了降低采集后得到的信息数据量，人们发明了许多数字压缩编 码技术来进一步压缩码率，这种将采样与压缩分离的传统处理方法浪费了许多通信资源。近 年来，daonodo 与 candes 等人提出了压缩感知(compressed sensing, cs)新理论1-3，压缩感 知提出在对信号进行采样的同时，也对信号进行了压缩。所以压缩感知的一个突出优点就是 实现了采样和压缩的结合，可以以远低于奈奎斯特的采样速率采集到原始信号较少的信息数 据量，并且理论证明，通过相应的重构算法可以以很高的概率还原出原始信号4-7。所以， 采用压缩感知技术代替传统的奈奎斯特定理，对语音信号进行传输与处理，可以大大降低在 传输过程中所需要的信息数据量。该理论现在已经成为现代语音处理技术领域的一个新的研 究方向。 1.1 课题研究背景课题研究背景 模拟信号是在时间轴上连续的信号，对模拟信号采样后得到的是一系列的离散采样点。 虽然这些离散点形状与原始模拟信号形状不一样，但是对一个带宽有限的连续模拟信号进行 采样时，如果采样速率足够大，那么这些采样值就可以完全代替传输的模拟信号本身。即只 要传输这些离散点便可以在接收端恢复出原始模拟信号，而描述这一采样速率条件的定理就 是采样定理。 1927 年，奈奎斯特证明了对某一带宽有限且时间连续的模拟信号进行采样，当采样率达 南京邮电大学硕士研究生学位论文 第一章 绪论 2 到一定数值时，根据这些采样序列可以在接收端准确地恢复出原始信号。当采样速率偏小时， 在频谱上发生频谱混叠，导致重构信号时会产生“半波损失” 。所以为了不使原波形产生“半 波损失” ，对模拟信号的采样速率应该至少为信号最高频率的两倍，这就是著名的奈奎斯特采 样定理。 奈氏采样定理指明：为了在采样后可以不失真地恢复出原始信号，采样频率必须要大于 或者等于整个信号最高频率的 2 倍。如果采样速率没有满足耐奎斯特采样定理的要求，在频 谱上会发生信号的重叠(混叠)， 因而不能正确分离出原始信号的频谱。 在日常生活中，语音频谱范围多在 0.3-3.4khz 内，根据耐奎斯特准则，语音信号处理中 采样频率一般为 8khz， 但是通常语音信号仅仅在很少时间范围内存在较高频率的分量， 所以 在任何时刻都使用 8khz 的采样速率，导致采集的数据冗余性很大，需要很大的网络开销。 所以科研人员提出一个构想：能否用一个正交稀疏变换基来表示原始信号，得到信号在另一 个域中的表现形式，并且建立新的理论框架对信号进行处理，使得在信息不丢失的情况下， 可以用远低于奈奎斯特采样的速率对信号进行采样， 并且可以在接收端准确恢复出原始信号。 近几年来，信号处理领域出现了一种新的理论-压缩感知(cs)，该理论吸引了相关研究人 员的关注，并带领信号处理进入到一个新的时代。压缩感知理论提出可以对信号同时进行采 样和压缩处理。相对于传统奈奎斯特采样定理，压缩感知先对信号进行采样，再对信号进行 压缩，采样的数据量较少，节省了时间和存储空间。由于采用压缩感知技术处理信号可以大 大降低所需的网络通信资源，使得该理论可以在现代信号处理领域中有着突出的优点和广阔 的应用前景。 文献1-3中指出，如果信号具有可压缩性或者在某个稀疏域上具有稀疏性，就可以通过 一个与稀疏变换域不相关的投影观测矩阵，将稀疏变换所得到的高维稀疏系数投影为一个低 维度的观测信号，最后通过一系列的重构优化问题，从低维度的观测信号中可以高概率地恢 复出原始信号。文献1-3中也证明了通过投影观测后的低维度观测信号包含了重构信号所需 的足够信息。基于这样的理论框架，信息在信号中的结构和内容决定了对数据进行采样的速 率，而采样的速率与信号的带宽没有关系。可以说，正是信号的稀疏性(或者可压缩性)导致 了我们对信号进行处理时，可以根据压缩感知技术，获得远低于奈奎斯特采样的数据量。 从理论上来说，任何信号都具有可压缩性或者稀疏性。只要找到与信号相对应的稀疏变 换域，使得信号在该稀疏变换域上可以稀疏地表示，那么就可以有效应用压缩感知理论对信 号进行处理。压缩感知现在已经涉及到应用科学和工程的多个领域中，并且具有重要的影响 和实践意义。例如，由于压缩感知具有稀疏性、随机性和凸优化性，可以在信道快速纠错码 南京邮电大学硕士研究生学位论文 第一章 绪论 3 中具有广阔的应用前景6。在宽带无线通信的信号分析处理中，可以用远小于奈奎斯特的采 样速率对数据进行采集6,7。在 x 射线和生物医学领域中，可以通过采集远远少于未知像素 点的观测数据来获取所需的图像信息8,9,10。在图像成像方面，美国莱斯大学已经基于压缩 感知技术，研究开发出了一款全新的“单像素相机” ，该相机在伪随机二值模型中使用数字微 镜阵列完成光学计算，利用比图像像素点数少得多的点恢复出原始图像6,7。现在大部分的 研究内容主要是针对图像的，语音压缩感知技术的研究还很少，处于刚起步的阶段，所以对 语音信号进行压缩感知处理是很有研究价值的。 文献11将压缩感知和语音编码相结合， 提出 了一种新的基于压缩感知的低速率语音编码方案。文献12将压缩感知应用到语音增强中， 对带噪语音进行压缩观测，提高了带噪语音的重构性能。 经典的压缩感知理论建立在非自适应的线性变换基础上，没有良好的灵活性，因此现在 有许多科研人员根据不同的信号类型采用不同的稀疏域和重构策略。对压缩感知理论进行自 适应研究，已经是目前压缩感知技术领域的一个热点研究方向。众所周知，在信号稀疏表示 的过程中用训练算法得到的稀疏变换基可以更加稀疏地表示该信号，但是增加了算法的存储 空间和计算成本，如何平衡算法性能和效率也是值得研究的问题，即寻找最优稀疏域和其相 应的投影观测矩阵是值得研究的。另外，压缩感知理论所用的重构算法大多是基于非线性的 迭代，具有复杂度高、计算量大的问题，难以达到实时性的要求，因此实时性强且重构性能 高的压缩感知理论也是重要的研究方向。 1.2 论文的主要内容和安排论文的主要内容和安排 第一章简要分析了传统数据采样所造成的数据采集量大的缺点，介绍了压缩感知理论相 对于传统数据采样的优点，以及压缩感知理论研究的现况。 第二章主要介绍了压缩感知系统的框架和基本原理，详细分析了压缩感知理论中的稀疏 表示、投影观测和重构算法，并提出了在现阶段一些有待解决的问题。 第三章主要介绍了语音压缩感知技术，首先分析了语音信号的产生原理及模型框图和传 统语音信号处理的步骤，然后证明了语音信号是近似稀疏的，可以使用压缩感知对其进行处 理，并详细介绍了本文所采用的自适应投影观测矩阵的产生模型。 第四章主要介绍了稀疏表示中所用的训练稀疏字典算法，并将其与小波分解后的语音特 性相结合，提出了一种基于小波分解的语音自适应压缩感知算法。 第五章主要介绍了变步长 k-lms 稀疏字典训练算法。在固定步长 k-lms 稀疏字典训练 南京邮电大学硕士研究生学位论文 第一章 绪论 4 算法的基础上，将稀疏表示误差考虑到变步长因子的计算中，从而降低了稀疏表示过程中的 稳态误差，提高了重构性能。 第六章对全文作了简要的总结，并且提出了下一步的工作和研究方向。 南京邮电大学硕士研究生学位论文 第二章 压缩感知的基本理论 5 第二章第二章 压缩感知压缩感知的的基本理论基本理论 2004 年 candes 从数学上证明了根据部分傅里叶变换系数，可以对信号进行精确地重构。 基于这样的理论成果， candes 和 donoho 在 2004 年正式提出了压缩感知理论的基本概念和理 论框架，其核心思想是利用信号的稀疏特性，对信号同时进行压缩与采样，首先采集信号的 投影观测值，然后根据相应的重构算法准确还原出原始信号1-3。该理论指出，信号的采样 速率与信号带宽大小无关，而与信息在信号中的结构和内容有关。同时该理论也给信息采集 和处理带来了一次新的重大变革和突破。 2.1 压缩感知的基本理论压缩感知的基本理论 压缩感知(cs)理论起源于 b.kashin4,5,6,7的泛函分析和逼近理论，并且和线性代数与解 析几何理论以及图论等有着很大的联系，其理论框架如图 2.1 所示。压缩感知理论主要由三 个主要部分组成，分别是信号的稀疏表示、投影观测和重构算法。信号稀疏表示的主要任务 是将信号映射到正交变换基上，使得其绝大部分变换系数的绝对值较小(接近于零，可以忽 略)，所得到的变换向量可以认为具有稀疏性或者近似稀疏，将这个稀疏变换向量可以看成是 原始信号在某一域上的另一种表达形式。信号可以在某个域上进行稀疏表示是应用压缩感知 的前提条件和基础，即信号必须在某种稀疏变换基上具有稀疏特性。投影观测矩阵必须满足 约束等距性(restricted isometry property, rip)条件，使得信号的投影观测向量与原始信号的结 构一样，投影观测向量由原始信号与投影观测矩阵的行向量作内积求得。最后通过相应的重 构优化算法，根据投影观测向量和 cs 矩阵精确恢复出原始信号。 图 2.1 压缩感知理论框架 2.1.1 信号的稀疏表示 设 n r为实数集空间， 在其空间内的任何一个信号都可以由若干个 n*1 维的基向量 1 n i i 可压缩 信号 稀疏表示 t x 投影观测 yx 重构 0 argminxx . styx 重构后 的信号 南京邮电大学硕士研究生学位论文 第二章 压缩感知的基本理论 6 的线性组合表示，并且假设这些基向量是正交的。n*n 维的稀疏变换基14-20可以看成是以 基向量 i 为列的矩阵。即 12 , n ,.，其中 1 jn jii ，j=1,2n。所以我们可以将 任何一个长度有限的一维离散时间信号 n xr表示为 1 n ii i x (2-1) 若的多数元素均为零，则称 n xr为稀疏的，其中向量是信号x在正交变换基上的稀疏 系数向量，n*1 维， 1 n i i 。稀疏系数满足 tx 或者, t iii xx (2-2) 其中 t 是的反变换。从上式我们可以看出，信号x是在时间域上的表现形式，稀疏系数 是信号x在稀疏变换基上的表现形式，所以x和是同一个信号在不同域上的两种等价表 现形式。 设信号 12 ,. n xx xx 1/ 1 p n p i p i xx (2-3) 为x的 p l范数。根据 p l范数定义，当满足以下公式： p k (2-4) 对于任意实数满足02p，0k 且 kn， 则我们认为向量在稀疏变换基下是稀疏的。 值得注意的是，稀疏系数向量的零范数，即0p 时，其数学意义是表示信号x在稀疏变换 域中非零值的个数，如果满足公式(2-4)我们认为信号x在稀疏变换基表示下的稀疏度或者 近似稀疏度为 k。信号稀疏分解的矩阵表示如图 2.2 所示。 = x 南京邮电大学硕士研究生学位论文 第二章 压缩感知的基本理论 7 图 2.2 信号稀疏分解的矩阵表示(假设白色部分为零元素) 由于自然界中常见的信号在传统时空域上并非都是绝对稀疏的，所以压缩感知技术并不 能对自然界信号直接应用处理。所以对于稀疏变换基方面的主要研究之一是寻找某种稀疏变 换基使得信号可以更加稀疏地表示16。即先通过某种稀疏变换求出信号在某稀疏变换基上 的稀疏表示结构，然后再按照压缩感知的后续步骤逐步处理。其中压缩感知的输入信号由原 始信号变成了其在稀疏变换基上的稀疏系数。 近年来，对稀疏表示的另一个主要研究方向是信号在过完备字典上的稀疏表示 17,18,19。用过完备的冗余函数集合25,26,27,28,29取代先前的基函数，过完备稀疏字典中 的元素(列向量)称为原子。该过完备字典的选择应该尽可能的接近输入信号结构，从这个字 典中选出 k 个最接近信号结构的原子，作为原始信号的近似表示。对信号在这种过完备字典 上的稀疏分解，往往可以获得远优于传统正交基变换的信号分解表示形式，即在过完备字典 上的稀疏系数向量具有较少的非零值。例如，文献17,18提出用局部 cosine 基来描述语音信 号的局部频域特性；利用 bandlet 基来描述图像中的几何边缘，还可以把其他的具有不同形状 的基函数集合到字典中，例如有 garbo 基可以用来描述纹理，curvelet 基可以用来描述轮廓 等23,24。在语音压缩感知技术中，文献30指出语音信号在 dct 域上具有良好的稀疏性， 在本文第三章中通过实验也证明了语音信号在 dct 域上的近似稀疏性。文献31证明了语音 信号在近似 klt 域上具有稀疏性，并提出了一种新的语音信号稀疏变换域。 压缩感知的应用前提和基础是尽可能地在稀疏变换域上稀疏分解信号。如果找到合适的 稀疏变换基，就能保证信号在该稀疏变换基上的稀疏度，从而保证信号的重构精度。在文献 35中 candes 和 tao 证明，利用压缩感知技术对满足幂次衰减速度的信号进行处理，可以重 构出原始信号，其重构误差为： 2 *() log r k exxc n (2-5) 其中 11 2 r p 。求解信号稀疏系数的本质是求解欠定线性方程组x，能否存在唯一解， 该唯一解是否稀疏，以及如何通过相关最优化方法求解该唯一解都是稀疏表示中所需解决的 问题。 2.1.2 信号的观测投影 通过稀疏分解 tx 得到稀疏系数后，我们需要选取投影观测矩阵。目的是在可以重 南京邮电大学硕士研究生学位论文 第二章 压缩感知的基本理论 8 构的条件下，尽可能地获得比原始信号维数少的观测序列1-7。所以在投影观测过程中，需 要保证信号x中的信息不被破坏，否则不能精确重构出原始信号。投影观测的目的是求出稀 疏系数向量在投影观测矩阵上的投影观测向量。 投影观测向量通过投影观测矩阵的 m 个 行向量 1 n ii 和稀疏系数向量做内积求得，则投影向量的维数为 m。 , ii y (2-6) 设投影观测向量 12 (,.) m yy yy，即 t yxx (2-7) 其中 t ，为 cs 矩阵。信号的投影观测过程如图 2.3 所示。 = y t x 图 2.3 投影观测的矩阵表示 根据公式(2-7)，已知投影观测向量 y 求出稀疏系数向量是一个线性规划的问题，但未 知数的个数远远多于方程式的个数，即 mn，所以根据公式(2-7)求出稀疏系数向量是一 个欠定问题。然而又因为稀疏度 km)。candes 等人1-7证明可以通过求解最小 0 l范数来解决压缩感知重构中的数学问题。 即通过求解最小 0 l范数来替代欠定方程 t yxx的求解： 0 min. . t styx (2-9) 但是只有列出信号x中所有非零值位置的 k n c种可能的组合，才能求解出最优解 42,43,44,45,46。所以求解式(2-9)是一个 np 难的问题，并且计算极不稳定，从而无法求解。 文献17,49,50,51表明，最小 1 l范数在一定条件下和最小 0 l范数具有等价性，即公式(2-9)转化 为： 1 min. . t styx (2-10) 公式(2-10)可以看成是一个线性规划问题的求解，是一个凸最优化问题，其计算复杂度为 o(n3)，这种方法被称为基追踪(basis pursuit, bp)方法。如果将重构误差考虑在内，公式(2-10) 可以转化成以下最小 1 l范数问题： 南京邮电大学硕士研究生学位论文 第二章 压缩感知的基本理论 11 12 min. .sty (2-11) 此外，内点法、梯度投影法以及同伦算法28,39,47也可以求解公式(2-10)。相比较而言，内 点法的重构性能较好，但是其速度较慢51；梯度法具有较快的运算速度；同伦算法适用于 重构低维度信号。 tropp 和 gilbert46,53,54提出了另外一种贪婪追踪算法，以匹配追踪(matching pursuit， mp)算法为代表。该类算法的优点是计算速度得到提高，并且易于实现。匹配追踪(mp)算法 53,54,56,57的基本思想是， 在每一次迭代过程中从过完备稀疏字典中选择出与信号相关性最 大的列向量作为稀疏逼近，并且求出信号的残差，然后选择出与信号残差相关性最大的列向 量，在满足重构误差要求或经过一定的重构次数后停止迭代，使信号可以由稀疏字典中的若 干个列向量线性表示。在该算法中每一次迭代的结果可能是次最优解，是因为信号在已选定 列向量集合上的投影可能非正交55，需要以较多迭代次数为代价来满足重构误差要求。 tropp 等56-59人提出正交匹配追踪(orthogonal matching pursuit, omp)算法用于压缩感 知中的信号重构，解决了以上可能存在的单次迭代中次最优解问题。该算法沿用了匹配追踪 (mp)算法从过完备字典中选取列向量的准则，在重构时每次迭代得到字典中的一个列向量， 利用递归对已选取的列向量进行 gram-schmidt 正交。正交匹配追踪(omp)算法可以保证每次 迭代结果的最优性，减少重构过程的迭代次数，是因为对选取的列向量进行正交化处理，不 会重复选择字典中的同一个列向量55。文献35表明对时域离散 n 维 k-稀疏的数字信号x， 以高斯随机