通信人家园

标题: 压缩感知原理整理 [查看完整版帖子] [打印本页]

时间: 2023-4-2 15:22

作者: ignotusm 标题: 压缩感知原理整理

## 压缩感知-keys
- concept：是针对信号采样的技术，通过一些手段实现压缩采样，即**在采样过程中完成了数据压缩的过程**
- 压缩感知概括性的*数学描述*：如果一个信号**在某个变换域是稀疏的**，那么就可以用一个**与变换基不相关的**观测矩阵将变换所得高维信号投影到一个低维空间上，然后通过求**解一个优化问题**就可以从这些少量的投影中以高概率重构出原信号。
-
- **奈奎斯特采样定律**callback：时域以τ为间隔进行采样，频域会以1/τ为周期发生周期延拓。那么如果采样频率低于两倍的信号最高频率，信号在频域频谱搬移后就会发生混叠。
- 压缩感知**颠覆**奈奎斯特采样定律：如果信号是稀疏的，那么可以以远低于采样定理要求的采样点重建恢复，就是压缩感知的概念。
**颠覆的关键**：采样方式；奈奎斯特是等间距采样，若是随机采样之类的不等间距采样
- **随机亚采样**：频域不再以固定周期延拓—>会产生大量不相关的干扰值——>最大峰值依然存在，但是一定程度上被干扰值覆盖——>干扰值得特点：像随机噪声，实际是由三个信号的能量泄露导致的？？？数学证明是什么
- 压缩感知的两个前提条件：稀疏性、不相关性
 * *稀疏性*：信号在某个域中的非零点数远小于信号总点数，则信号在该域是稀疏的（在稀疏域重建复原原信号容易）
 近似稀疏、不稀疏——>做DWT、DCT找到稀疏变换
 * *不相关性*：
 用随机亚采样才能恢复出信号——>观测矩阵表示亚采样的过程——>
 * 观测矩阵应该满足约束等距性条件（restricted isometry property，RIP）
 ![[Pasted image 20230331115018.png]]* RIP的等价条件：观测矩阵和稀疏表示基不相关
 ![[Pasted image 20230331114938.png]]* 如何找到普适的观测矩阵Φ——>和任意稀疏基表示Ψ都具有不相关性——>高斯随机测量矩阵（其实就是如何进行亚采样，才能满足不相关性）
 *
 ![[Pasted image 20230331115708.png]]
- 压缩感知和图像压缩的区别：
![[Pasted image 20230331113232.png]]
* 图像压缩：先进行了全采样，然后在变换域丢弃小系数，完成压缩
* 压缩感知：直接进行亚采样，然后用算法消除亚采样导致的伪影（直接在采样时就完成了压缩）
- 压缩感知的数学表达：
![[Pasted image 20230331113502.png]]
 * x是为长度N的一维信号，也就是原信号，稀疏度为k。此刻它是未知的。
 * *Φ为观测矩阵*，对应着亚采样这一过程。它将高维信号x投影到低维空间，是已知的。
 * *y=Φx*为长度M的一维测量值，也就是亚采样后的结果。显然它也是已知的。
 * 因此，**压缩感知问题就是在已知测量值y和测量矩阵Φ的基础上，求解欠定方程组y=Φx得到原信号x。**
 * 然而，一般的自然信号x本身并不是稀疏的，需要在某种稀疏基上进行稀疏表示。令x=Ψs，Ψ为稀疏基矩阵，s为稀疏系数。
 * 于是最终方程就变成了：**y=ΦΨs。已知y、Φ、Ψ，求解s。** 即，由低维的向量y精确重构出Nyquist速率采样的高维数据向量x。

 - 感知矩阵 **y=ΘS**：ΦΨ合并成一个矩阵，称之为传感矩阵。即令Θ=ΦΨ
 ![[Pasted image 20230331114318.png]] * **问题即为，已知y和Θ，求解S。**

求解出S后，由x=Ψs即可得到恢复出的原信号x。

然而在正常情况下，*方程的个数远小于未知数的个数，方程是没有确定解的，无法重构信号*。但是，由于信号是K稀疏，如果上式中的***Φ满足有限等距性质(RIP)，则K个系数就能够从M个测量值准确重构（得到一个最优解）**。

### 压缩感知的本质数学问题：求解K稀疏向量S，i.e.，欠定稀疏方程组y=ΘS
- 压缩感知的核心问题转化为 **L0范数最小化问题**：
 * L0范数是指向量中非0的元素的个数
 * 研究难点：直接求解该问题需要筛选出稀疏向量x=Ψs中所有可能的非零元素——>此方法是不可跟踪或NP-hard的，因为搜索空间过大
 * *问题转化的关键*：当RIP条件满足时，非凸的L0范数最小化问题和L1范数最小化问题等价

### 压缩感知过程
**1. 稀疏表示**
 找到一个基或者过完备的字典Ψ，使得X在Ψ域是稀疏的
 $X=ΨY$
 因为是规范正交基所以实现变换系数也就是压缩信号： $\boldsymbol{Y} = \boldsymbol{\Psi}^T \boldsymbol{X}$，其中 $\boldsymbol{Y}$ 是 $\boldsymbol{X}$ 的等价或逼近的稀疏表示
**2. 投影测量（测量过程）**
 观测矩阵 $\boldsymbol{\Phi} \in \mathbb{R}^{M\times N}$ ，观测矩阵也叫测量矩阵，感知矩阵，实现的功能是对信号进行降维和压缩
 $\boldsymbol{A} = \boldsymbol{\Phi}\boldsymbol{X}$
 同时也是对在$\boldsymbol{\Psi}$域上的稀疏投影$\boldsymbol{Y}$进行投影测量
 $\boldsymbol{A} = \boldsymbol{\Phi}\boldsymbol{\Psi} \boldsymbol{Y}$
矩阵 $\boldsymbol{\Phi}$需要满足的性质（需要保证稀疏向量 $\boldsymbol{Y}$从N 维降到 K 维时重要信息不被破坏。）——*RIP有限等距性*

- ***RIP有限等距性***
 由于信号在稀疏域$\boldsymbol{\Psi}$上是K稀疏，如果上式中的观测矩阵$\boldsymbol{\Phi}$满足有限等距性质，则稀疏域上较少的非零系数就能够从M个测量值准确重构（得到一个最优解）。
$$\min \left\|| \boldsymbol{\Psi}^{T} \boldsymbol{X}\right\||_{0} s.t. \boldsymbol{\Theta} \boldsymbol{X}=\boldsymbol{\Phi}\boldsymbol{\Psi}\boldsymbol{X}= \boldsymbol{A}$$
**1） RIP条件的数学表达**
 定义$\boldsymbol{Y}$为K 稀疏，若存在满足下面不等式的$\delta_{k}$
$$\left(1-\delta_{k}\right)\|\boldsymbol{Y}\|_{2}^{2} \leq\|\boldsymbol{\Phi} \boldsymbol{Y}\|_{2}^{2} \leq\left(1+\delta_{k}\right)\|\boldsymbol{Y}\|_{2}^{2}$$
 $\delta_{k}<1$，则测量矩阵$\boldsymbol{\Phi}$满足K阶RIP条件
 **2) RIP的等价条件**
 要确认一个矩阵是否满足RIP非常复杂。于是Baraniuk证明：RIP的等价条件是观测矩阵$\boldsymbol{\Phi}$和稀疏表示基$\boldsymbol{\Psi}$不相关（incoherent）。
 *-矩阵不相关的数学表示*
 $A=ΦX=ΦΨY$
 要求$\boldsymbol{\Phi} \stackrel{\text { 不相关 }}{\longleftrightarrow} \boldsymbol{\Psi}$
 相关性的定义： $\mu(\boldsymbol{\Phi}, \boldsymbol{\Psi})=\sqrt{n} \cdot \max _{1 \leq k, j \leq n}\left|\left\langle \boldsymbol{\phi}_{k}, \boldsymbol{\psi}_{j}\right\rangle\right|$
 $mu$的范围 : $\mu(\boldsymbol{\Phi}, \boldsymbol{\Psi}) \in[1, \sqrt{n}]$
 $\mu$越小，$\boldsymbol{\Phi}$和$\boldsymbol{\Psi}$越不相关

通信人家园 (https://www.txrjy.com/)