压缩感知原理整理

ignotusm

## 压缩感知-keys
- concept：是针对信号采样的技术，通过一些手段实现压缩采样，即**在采样过程中完成了数据压缩的过程**
- 压缩感知概括性的*数学描述*：如果一个信号**在某个变换域是稀疏的**，那么就可以用一个**与变换基不相关的**观测矩阵将变换所得高维信号投影到一个低维空间上，然后通过求**解一个优化问题**就可以从这些少量的投影中以高概率重构出原信号。
-
- **奈奎斯特采样定律**callback：时域以τ为间隔进行采样，频域会以1/τ为周期发生周期延拓。那么如果采样频率低于两倍的信号最高频率，信号在频域频谱搬移后就会发生混叠。
- 压缩感知**颠覆**奈奎斯特采样定律：如果信号是稀疏的，那么可以以远低于采样定理要求的采样点重建恢复，就是压缩感知的概念。
   **颠覆的关键**：采样方式；奈奎斯特是等间距采样，若是随机采样之类的不等间距采样
- **随机亚采样**：频域不再以固定周期延拓—>会产生大量不相关的干扰值——>最大峰值依然存在，但是一定程度上被干扰值覆盖——>干扰值得特点：像随机噪声，实际是由三个信号的能量泄露导致的<font color=#00ffff >？？？数学证明是什么</font>
- 压缩感知的两个前提条件：稀疏性、不相关性
        * *稀疏性*：信号在某个域中的非零点数远小于信号总点数，则信号在该域是稀疏的 （在稀疏域重建复原原信号容易）
           近似稀疏、不稀疏——>做DWT、DCT找到稀疏变换
        * *不相关性*：
             用随机亚采样才能恢复出信号——>观测矩阵表示亚采样的过程——>
             * 观测矩阵应该满足<font  color="blue">约束等距性条件（restricted isometry property，RIP）</font>
             ![[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个测量值准确重构（得到一个最优解）**。

### <font  color=green>压缩感知的本质数学问题：求解K稀疏向量S，i.e.，欠定稀疏方程组y=ΘS</font>
- 压缩感知的核心问题转化为 **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}$越不相关