压缩感知重构匹配类算法分析
摘  要： 压缩感知理论是一种利用信号的稀疏性或可压缩性而把采样与压缩融为一体的新理论体系，它成功地克服了传统理论中采样数据量大、资源浪费严重等问题。该理论的研究方向主要包括信号的稀疏表示、测量矩阵的设计和信号的重构算法。其中信号的重构算法是该理论中的关键部分，也是近年来研究的热点。本文主要对匹配追踪类重构算法作了详细介绍，并通过仿真实验结果对这些算法进行了对比和分析。
关键词： 压缩感知； 稀疏信号； 重构算法； 匹配追踪类压缩感知算法
abstract：the compressive sensing theory is a recent proposed theory, which can utilize the sparse and compressive characteristics of signals to combine the sampling and compression processes into only one procedure. it overcomes the shortcomings of large sampling data and significant waste of resource in traditional theories. the research areas in compressive sensing mainly include the sparse representation of signals, the design of measurement matrix, and signal reconstruction algorithms. the reconstruction algorithm is the key component of this new theory and is the focus of recent research. in this paper, the reconstru
ction algorithms, which use matching and tracking techniques, are described in details. simulations of these algorithm are also conducted to compare and analyze these algorithms.
key words： compressive sensing, sparse signal, reconstruction algorithm, compress sensing algorithms based on matching
1 cs（压缩感知）背景知识
压缩感知理论[1-4]是一种能够在采样的同时实现压缩目的的新理论，其基本思想是：只要信号本身或者信号在某个变换域上是稀疏的或可压缩的，那么就可以用一个与变换域不相关的测量矩阵将变换域的高维信号投影到一个低维空间上，然后通过求解一个优化问题就能够从少量的投影系数中以较高的概率成功或近似地重构出原信号。在该理论框架下，采样速率不依赖于信号带宽，而取决于信号本身的结构和内容。该理论的基本框架如图1所示。
图1  压缩感知理论框架
信号的可稀疏性是压缩感知理论的基础和前提。只有选择合适的基来表示信号，才能保证信
号的稀疏度，从而保证信号的精确重构。假设给定一组基（设为标准正交基ψ），如果一个长度为n的信号x可以用ψ中k个基向量线性表示，那么有：
（1.1）
则称x为k阶稀疏信号。其中系数，由此可以看出，x和s是对同一信号的两种等价描述形式，x为信号时域形式，s为信号在ψ域的变换形式。
当我们用一个已知的测量矩阵来采样未知的稀疏信号x时，则可得到m维的线性测量值y=rm。
（正则化正交匹配追踪1.2）
其中，是m×n维的矩阵，称作传感矩阵。对于测量值y，可以看成是s关于传感矩阵的测量值。当传感矩阵满足rip（约束等距条件）[5]时，可以通过求解问题(1.2)的逆问题先求出稀疏系数s，然后由式(1.1)解出x，从而将x从m维的观测向量y中正确地恢复出来。信号稀疏重构问题的最直接有效方法是通过一个类似l0范数的最优化问题来重构原始信号x，即：
s.t.  φx=y                （1.3）
其中是重构出的信号。
通过上述分析可知，压缩传感理论的研究主要包括三个方面：信号的稀疏表示、测量矩阵的设计和信号的重构算法。信号的重构算法是压缩传感理论当中相当关键的一部分，其算法主要有两类：一类是匹配追踪类重构算法，主要是求解l0范数的最小化问题，主要包括正交匹配追踪(omp)算法[6]、正则化正交匹配追踪（romp）算法[7]、子空间追踪（sp）算法[8]、压缩抽样匹配追踪（cosamp）算法[9]；另一类是凸松弛类算法，它是把l0范数最小化直接转化为l1范数最小化，并通过凸优化方法求解，主要包括基追踪算法[10]、梯度追踪算法[11]、迭代硬阈值算法[12]等。下面主要对匹配追踪类重构算法进行具体的介绍和比较分析。
2 cs匹配追踪类重构算法
匹配追踪类重构算法主要是运用贪婪算法思想来解决l1范数问题。其基本思想是在每一次的迭代过程中，从过完备原字库里（即测量矩阵φ）选择与信号最匹配的原子来进行稀疏逼近并求出余量，然后继续选出与信号余量最为匹配的原子，并把它们放在不断更新的原子支撑集φ∧中，依次类推，经过数次迭代，该信号便可以用这些原子进行线性表示。
在允许一定重构误差存在的情况下，l0范数最小化求解模型为式(2.1)。
s.t.                        (2.1)
其中：s为信号x的稀疏变换域形式，ε是一个较小的常数。
在匹配追踪类算法中，对于相关系数u的计算，是通过余量r与测量矩阵φ（）中各个原子之间内积的绝对值来求解的，如式(2.2)：
(2.2)
然后采用最小二乘法进行求解信号逼近值以及余量的更新值rnew：
(2.3)
(2.4)
2.1 正交匹配追踪（omp）算法
omp算法是对mp(匹配追踪)算法的一种改进。该算法仍然沿用了mp算法中的原子选择准则，即从原子集合φ中选择和观测信号或迭代余量最为匹配的原子。除此之外，omp算法需要将
已选择的原子运用gram-schmidt正交化方法进行处理，然后再将信号投影在这些正交原子构成的空间上，从而得到信号在各个已选原子上的分量和迭代余量。基于这种正交性处理，omp算法不会重复地选择原子，因此经过有限次（k次）迭代后就能够收敛到稀疏解，从而大大降低了迭代次数。正是由于这种原子正交化处理的加入，加大了omp算法的计算量，使得信号重构时间远远长于匹配追踪算法，所以对于一些大规模信号，omp算法可能无法使用。
另外，omp的重构算法是在迭代次数已知的条件下重构的，这种使迭代过程强制停止的方法使得omp算法需要大量的线性测量来保证其重构精度。omp算法以贪婪迭代的方法选择出列，使得在每次迭代中选择的列与当前的冗余向量最大程度地相关，然后从测量向量中减去相关部分并反复迭代，直至迭代次数达到稀疏度k后强制停止。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。