摘要：提出了一种新的基追踪求解算法。依据信号特性自适应地选取字典；通过l1范数的近似表示，将有约束的极值问题转化为无约束问题，并利用一种新的迭代算法进行快速求解；几类典型信号实验结果验证了本方法具有良好的去噪效果。

        关键词：基追踪 字典 去噪

        基追踪方法是信号稀疏表示领域的一种新方法。它寻求从完备的（过完备）函数（基）集合中得到信号的最稀疏的表示，即用尽可能少的基精确地表示原信号，从而获得信号的内在本质特性。基追踪方法采用表示系统的范数作为信号稀疏性的度量，通过最小化l1范数将信号稀疏表示问题定义为一类有约束的极值问题，进而转化为线性规划问题进行求解。

        目前，基追踪方法在一维信号处理领域有很好的应用。以David L.Donoho为代表的斯需求量福大学统计系工作组利用基追踪方法在一维实信号去噪和超分辨方面取得取了很多很好的应用结果。尽管使用了一种新的线性规划算法——内点算法，基追踪方法由于要在所有的字典向量中极小化一个全局目标函数，其计算量仍然是很大的。正因为求解大尺度线性规划问题的困难，目前的基追踪方法局限于一维的信号去噪和超分辨处理。本文提出一种新的思路来求解上述有约束的极值问题。首先依据信号特性自适应地选取字典；通过l1范数的近似表示，将有约束的极值问题转化为无约束问题，并利用一种迭代算法进行快速求解；最后通过几类典型信号去噪实验来验证本方法的应用效果。实验结果表明，改进的基追踪方法能够快速稳定实现，。同时具有良好的去噪效果。

1 字典的构造

        对于观测到的离散信号s∈H,H为Hilbert空间，给定H中的字典φ={φγ，γ∈Γ}，其中Γ为指标集，φγ为H中的基函数，也称为原子。基追踪方法将信号稀疏表示问题定义为以下有结束的极值问题，即

其中，αγ（γ∈Γ）为表示系数。如果将字典中的向量表示成矩阵φ的例，系数表示成一个列向量，则（1）式可表示成

min||α||1 subject to s=φα (2)

在含噪观测的情况下，考虑如下模型：

y=s+σz

其中s为真实信号，y为观测信号，z为标准高斯白噪声，σ为噪声根方差。基追踪方法去噪归结为求解以下优化问题：

        以上最优化问题致力于最小化信号重建误差，同时使得信号的表示最稀疏。正则化参数λ控制着允许误差与稀疏性之间的平衡。

        由（3）式可见，基追踪方法去噪的核心问题涉及到原子的选取、字典的构造、求解算法设计等三个方面。其中，字典的构造是基追踪方法的重要环节。为了尽可能精确地表示信号，字典与信号应用是自适应的，或者说字节是从信号的学习中得到的。通常，基追踪方法所使用的字典有完备的、过完备的、欠完备的等。可以根据信号的先验信息及实际需要设计字典。一般设计的字典是完备或过完备的。对于简单信号去噪，一般只需要构造完备的字典。对于复合信号对噪问题，通常需要构造过完备的字典。对于完备字典，同样存在信号的稀疏表示问题，因为噪声总是处处奇异的。本文所采用的字典主要有：

（1）Heaviside字典

此字典中原子不是正交的，但是对于任意长度为n的一维离散信号s=(s1s2…sn)都有以下表示：

        Heaviside字典具有上三角形式，结构简单，善于捕捉分片常数信号中的突变特征。

（2）时间-尺度字典（小波字典）

以Haar小波字典为例：

你小波基：ψ=l[0,1],母小波基：ψ=1[1/2,1],1-1[0,1/2]

Haar小波字典中包含小波基的