概述
正交匹配追踪算法OMP(Orthogonal Matching Pursuit)
本文主要基于文献《Orthogonal Matching Pursuit for Sparse Signal Recovery With Noise》编写而成。主要讲述OMP算法基本步骤和思想,后续会介绍OMP算法在Bounded noise和Gaussian noise下的终止条件的选择。
Introduction
在信号处理过程中,经常会遇到这样一个模型:
其中,
- 向量 y∈Rn y ∈ R n 是观测向量(observation vector)。
- 矩阵 X∈Rn×p X ∈ R n × p ,这里的 X X ()也有些地方称作过完备字典矩阵,下边提到矩阵 X X ,都默认矩阵 的每一列均是正则化的,即 ||Xi||2=1 for i=1,2,⋯,p | | X i | | 2 = 1 f o r i = 1 , 2 , ⋯ , p 。
- ϵ∈Rn ϵ ∈ R n 是信号观测或者传输时的产生的噪声误差(the measurement errors), β∈Rp β ∈ R p 是真实信号。
该模型的目标就是通过观测值 y y 和矩阵 ,把未知向量 β β 求出来。
对于向量 ,定义 β β 的支集(support)为 supp(β)={i:βi≠0} s u p p ( β ) = { i : β i ≠ 0 } 。如果 |supp(β)|≤k | s u p p ( β ) | ≤ k ,可以说 β β 是 k k 稀疏()的。
另外,在Donoho and Huo(2001)中介绍了MIP(Mutual Incoherence Property)条件,并且 mutual incoherence 被定义为
其它用在压缩感知文献中的条件还有RIP(Restricted Isometry Property)和ERC(Exact Recovery Condition)。
The OMP Algorithm
下边给出OMP算法的具体步骤,在这之前再来重申一下一些相关概念的定义。
矩阵 X X 的每一列均是正则化的,即
对于集合 S ⊆ {i=1,2,⋯,p} S ⊆ { i = 1 , 2 , ⋯ , p } , X(S) X ( S ) 表示 X X 的一个子矩阵,由 的列 Xi X i 组成,其中 i∈S i ∈ S
The OMP algorithm can be stated as follows.
-
Step 1:
初始化,残差(residual) r0=y r 0 = y ,已选择的变量集合 X(c0)=∅ X ( c 0 ) = ∅ 。令迭代次数 i=1 i = 1 。
-
Step 2:
寻找变量 Xti X t i 使得 ti t i 为 maxti|X′tiri−1| max t i | X t i ′ r i − 1 | 的解。
然后将 Xti X t i 添加到已选变量集合中,并且更新 ci=ci−1⋃{ti} c i = c i − 1 ⋃ { t i } 。 -
Step 3:
令 Pi=X(ci)(X(ci)′X(ci))−1X(ci)′ P i = X ( c i ) ( X ( c i ) ′ X ( c i ) ) − 1 X ( c i ) ′ ,更新残差 ri=(I−Pi)y r i = ( I − P i ) y 。
-
Step 4:
如果终止条件满足,则算法结束;否则,令 i=i+1 i = i + 1 并且返回 Step 2 。
The OMP is a stepwise forward selection algorithm and is easy to implement.
在【step 4】中,要对程序终止条件进行判断,OMP的停止条件是依赖 noise structure 的。显然,在无噪的情况下,stop rule 就是残差 ri=0 r i = 0 。
The OMP Algorithm : Stopping Rules and Properties
在这之前,先给出一些定义。
令
T={i:βi≠0}
T
=
{
i
:
β
i
≠
0
}
为
β
β
的支集,
X(T)
X
(
T
)
为和支集
T
T
对应的矩阵 中列的集合。
在Tropp(2004)中介绍 Exact Recovery Condition (ERC) 指的是 M<1 M < 1 ,另外还讲述了 ERC 对于无噪情况下信号 β β 支集的复原是一个充分的条件。从上式可以看到,M的计算依赖于支集T,但是通常情况下T是事先不知道的,如果使用 mutual incoherence μ μ 就好办很多了。
-
Lemma 1.
- If μ<12k−1 μ < 1 2 k − 1 , then M≤kμ1−(k−1)μ<1 M ≤ k μ 1 − ( k − 1 ) μ < 1 . Lemma 2.
- Suppose μ<12k−1 μ < 1 2 k − 1 , then 1−(k−1)μ≤λmin≤λmax1+(k−1)μ 1 − ( k − 1 ) μ ≤ λ m i n ≤ λ m a x 1 + ( k − 1 ) μ , where k k denotes the cardinality of .
λmin λ m i n 和 λmax λ m a x 表示 X(T)′X(T) X ( T ) ′ X ( T ) 的最小和最大的特征值。引理1是Tropp(2004)中Theorem 3.5的一个特例。有关 λmin λ m i n 和 λmax λ m a x 的范围界定的相关结论,在 Needell and Tropp (2008) 中也有给出。
显然,为了更好的进行变量选择,矩阵X列的共线性和信噪比都需要被控制在一定范围内。更具体的来说,矩阵X的列向量 Xi X i 的线性相关性要尽可能的小,信噪比(signal-to-noise ratio)要尽可能的高。
接下来考虑两种噪声:有界噪声(Bounded Noise)和高斯噪声(Gaussian Noise)。其中,有界噪声考虑两种情况:一是 l2 l 2 bounded noise,即对于常数 b2>0 b 2 > 0 有 ∥ϵ∥2≤b2 ‖ ϵ ‖ 2 ≤ b 2 ;二是 l∞ l ∞ bounded noise,即对于常数 b∞>0 b ∞ > 0 有 ∥X′ϵ∥∞≤b∞ ‖ X ′ ϵ ‖ ∞ ≤ b ∞ 。高斯噪声即 ϵi ϵ i 独立同分布于 N(0,σ2) N ( 0 , σ 2 ) 。
l2 l 2 Bounded Noise
这种噪声结构下,算法停止条件设置为 ∥ri∥2≤b2 ‖ r i ‖ 2 ≤ b 2 。这个条件设置的很巧妙,由于 ∥ϵ∥2≤b2 ‖ ϵ ‖ 2 ≤ b 2 ,所以在此停止条件下,对于 β≡0 β ≡ 0 的情况,OMP算法不会选择任何变量,程序直接终止。
l∞ l ∞ Bounded Noise
这种噪声结构下,算法停止条件设置为 ∥X′ri∥∞≤b∞ ‖ X ′ r i ‖ ∞ ≤ b ∞ 。和前一种噪声结构 l2 l 2 bounded noise 的情况一样,这个停止条件保证了对于 β≡0 β ≡ 0 的情况,OMP算法不会选择任何变量,程序直接终止。
Gaussian Noise
事实上,Gaussian Noise是“essentially bounded”的。
该文待更新…
最后
以上就是冷酷手机为你收集整理的正交匹配追踪算法OMP(Orthogonal Matching Pursuit)的全部内容,希望文章能够帮你解决正交匹配追踪算法OMP(Orthogonal Matching Pursuit)所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复