浅谈压缩感知（二十）：OMP与压缩感知- AndyJee

一、OMP在稀疏分解与压缩感知中的异同

1 、稀疏分解要解决的问题是在冗余字典 ( 超完备字典 ) A 中选出 k 列，用这 k 列的线性组合近似表达待稀疏分解信号 y ，可以用表示为 y = Aθ ，求 θ 。

2 、压缩感知重构要解决的问题是事先存在一个 θ 和矩阵 A ，然后得到 y = Aθ （压缩观测），现在是在已知 y 和 A 的情况下要重构 θ 。

A 为 M×N 矩阵（ M<<N ，稀疏分解中为冗余字典，压缩感知中为传感矩阵 A = ΦΨ ，即测量矩阵 Φ 乘以稀疏矩阵 Ψ ），

y 为 M×1 的列向量（稀疏分解中为待稀疏分解信号，压缩感知中为观测向量），

θ 为 N×1 的列向量（稀疏分解中为待求分解系数，压缩感知中为信号 x 的在变换域 Ψ 的系数， x = Ψθ ）。

对已知 y 和 A 的情况下，求 y = Aθ 中的 θ 。

稀疏分解中 θ 是稀疏的，在压缩感知中信号也需要满足稀疏性的条件，这也是相同点之一。（ OMP 一开始在应用在稀疏表示上，后来压缩感知恰好信号也满足稀疏性条件，因此 OMP 也适用于压缩感知问题）

在稀疏分解中 θ 是事先不存在的，我们要去求一个 θ 用 Aθ 近似表示 y ，求出的 θ 并不能说对与错；在压缩感知中， θ 是事先存在的，只是现在不知道，我们要通过某种方法如 OMP 去把 θ 求出来，求出的 θ 应该等于原先的 θ 的，然后可求原信号 x = Ψθ 。

压缩感知中的 A 需要满足一定的条件来保证重建的可行性与唯一性。（如 RIP 、 spark 等）

通过OMP等重构算法求出的θ就是原来的x=Ψθ中的那个θ吗？为什么通过OMP迭代后一定会选出矩阵A的那几列呢？会不会选择A的另外几列，它们的线性组合也满足y=Aθ？

压缩感知的前提条件：若要恢复y=Aθ中k稀疏的θ，要求感知矩阵A（感知矩阵A=ΦΨ，即测量矩阵Φ乘以稀疏矩阵Ψ）至少任意2k列线性相关。这是压缩感知中A必须满足的一个条件。

假设通过OMP迭代后，存在两种不同的线性组合满足 y = Aθ

即 A _t θ _t = A _r θ _r _，这意味着 Aθ _k1 = Aθ _k2 _，即 A ( θ _k1 － θ _k2 )= 0 。此处的θ大小与y一致，但只有与选中对应列的位置处不为0.

两个k稀疏的N维信号（长度为N的列向量）θk1和θk2，它们的差向量(θk1－θk2)的稀疏度最大不超过2k，（当θk1和θk2中的非零项都没有对应在同一位置时）。

而A必须满足至少任意2K列线性相关，因此A的零空间维度必须至少为2K，而(θk1－θk2)的稀疏度最大不超过2k，因此A (θk1－θk2)=0并不成立，即原假设不成立。

所以在感知矩阵A满足至少任意2k列线性相关的前提下（即spark常数），通过OMP算法恢复出的θ是唯一的。