压缩感知成像

一、背景介绍

压缩感知允许我们从远少于传统采样定理（如Nyquist-Shannon采样定理）所需的样本中恢复信号。这种技术基于一个观察：许多信号在某种变换（如傅里叶变换、小波变换等）下是稀疏的，即信号在这种变换下只有少数几个非零系数，我们就能以较低的频率（远低于奈奎斯特采样频率）采样该信号，并可能以高概率精确的重建该信号。

二、压缩感知基础及重构条件

2.1 压缩感知理论基础

设信号 x为长度为 N 的列向量，在稀疏表示中可以用 N×N 的变换基 Ψ=[ψ1,ψ2,⋯,ψN] 线性表示：
$$x=\psi h$$
h 为信号 z 在不同域上的等价表示。在压缩感知理论中，为了实现压缩采样，使用一个与信号 z 或者变换矩阵不相关的测量矩阵将信号 z 投影到低维的空间上，即：
$$y=\Phi x$$
其中， Φ∈CM×N 是测量矩阵， y=[y1,y2,⋯,yM] 是长度为 M 的观测向量，其中 M<N ，则：
$$y=\Phi x+n=\Phi \psi h+n=Ah+n$$
其中， n 为量测噪声， A=ΦΨ 是 M×N 维的感知矩阵（传感矩阵），如下图所示。

如图，x是为长度N的一维信号，也就是原信号，稀疏度为k。此刻它是未知的。Φ为观测矩阵，对应着亚采样这一过程。它将高维信号x投影到低维空间，是已知的。y=Φx为长度M的一维测量值，也就是亚采样后的结果。显然它也是已知的。因此，压缩感知问题就是在已知测量值y和测量矩阵Φ的基础上，求解欠定方程组y=Φx得到原信号x。然而，一般的自然信号x本身并不是稀疏的，需要在某种稀疏基上进行稀疏表示。令x=Ψs，Ψ为稀疏基矩阵，s为稀疏系数。于是最终方程就变成了：**y=ΦΨs。已知y、Φ、Ψ，求解s。**求解出S后，由x=Ψs即可得到恢复出的原信号x。

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

2.2 压缩感知前提条件

2.2.1 稀疏性

​ 稀疏性：信号可以用少数个特征向量的线性组合来表示，具体来说，指的是一个 n 维实信号可以在一组基下可以展开成一个 k−sparse 的向量，就是该向量的非零元素为 k 个， k<<n 。

​ 图像的稀疏性：数字图像的存储形式就是2维矩阵（灰度图像是1个二维矩阵，彩色图像是3个二维矩阵）。自然图像可以分解为许多独立的成分，在给定冗余字典（*一种超完备的函数库，与传统的正交基不同，冗余字典中的元素，称为原子，数量通常多于信号的维度，这使得字典能够提供更灵活和丰富的表示方式。冗余字典的主要目的是通过少量的原子线性组合来重构信号，从而实现信号的稀疏表示）*的情况下，自然图像可以稀疏表示，即每个信号只需由字典里很少几个基的线性组合进行构造。

​ 利用线性代数、矩阵论中的范数理论来解释，零范数（序列或矩阵中的非零元素个数计算算子）是最好的稀疏性表征，也即对于序列信号 s(t) 或图像矩阵 Gm×n ，只要：
$$\begin{gathered} ||s(t)|{|}_0\ll size(s(t)) \\ ||{\mathrm{G}}_{m\times n}|{|}_0\ll size({\mathrm{G}}_{m\times n}) \end{gathered}$$
则视为该信号或图像是稀疏的，且零范数的值对应其稀疏度，零范数越小稀疏度越大。用形象化的解释来说，这个信号或图看起来像“散点状“。对于一幅图像而言，其像素间的相关性表现在图像在某个变换域的系数是稀疏分布的；如何合理和充分利用高维数据间存在的稀疏性和冗余性，对于高效地采集、表示、重构这些数据是十分重要的。

​低秩性：低秩性可以看做是稀疏性在矩阵上的拓展。稀疏性是指向量或矩阵中大部分元素为 0 ，而矩阵的低秩性是指矩阵的秩相对于矩阵的行数或列数而言很小。如果对矩阵进行奇异值分解，并把其所有奇异值排列为一个向量，那么这个向量的稀疏性便对应于该矩阵的低秩性。**矩阵秩最小化主要是指利用原始数据矩阵的低秩性进行矩阵的重建，这涉及到最小化矩阵的秩函数。低秩矩阵恢复则是指同时利用原始数据矩阵的低秩性和误差矩阵的稀疏性来恢复数据矩阵。如果利用线性代数、矩阵论中的范数理论来解释：对于信号或图像矩阵 Gm×n ，只要：
$$\mathrm{rank}({\mathrm{G}}_{m\times n})\ll \min (m,n)$$
则视为该信号或图像是低秩的。用形象化的解释来说，这个信号或图看起来像“几条线”。从应用上，笼统地讲，稀疏、低秩均表征着一种冗余程度。稀疏度越高、秩越低表示数据冗余性越大，用很少几个基就可以表达完整数据了。

2.2.2 观测矩阵Φ应满足约束等距性（RIP）

RIP是压缩还原算法中常常可以看见的名词，主要可以被用来分析还原算法的表现好坏。其定义如下：对于任意具有稀疏度 K 的信号 z ，感知矩阵 A 满足：
$$\left(1-{\delta }_K\right)\Vert z{\Vert }_2^2\le \Vert Az{\Vert }_2^2\le \left(1+{\delta }_K\right)\Vert z{\Vert }_2^2$$
其中， δK∈(0,1) 称为 K 阶等距约束常数。若感知矩阵 A 满足一定阶数和常数的RIP， L−0 范数和 L−1 范数的最优解将完全一致。因此RIP也是凸松弛类解法是否能够达到最优的先决条件之一。RIP的本质是感知矩阵 A 中所有列子集都正交。陶大神和Candès大神证明了RIP才是观测矩阵要满足的准确要求。尽管一些矩阵被证明符合 RIP，但是实际中无法检测大多数矩阵的 RIP。于是Baraniuk证明：RIP的等价条件是观测矩阵和稀疏表示基不相关。

所以在实际中一般应用互相关系数来评估测量矩阵的重构性能。感知矩阵 A 的互相关系数定义为：
$$\chi (A)=\underset{i\ne j}{\max }\frac{\left|⟨{\rho }_i\cdot {\rho }_j⟩\right|}{{\Vert {\rho }_i\Vert }_2{\Vert {\rho }_j\Vert }_2}$$
其中， ρi 表示感知矩阵 A 的第 i 列， ⟨ρi⋅ρj⟩ 为向量的内积。为能够精确重构信号，对信号稀疏度 K 与互相关系数 χ 的要求如下：
$$\begin{gathered} K<\frac{1}{2}\left(\frac{1}{\chi }+1\right),\text{信号不包含噪声} \\ K<\frac{1}{4}\left(\frac{1}{\chi }+1\right),\text{信号包含噪声} \end{gathered}$$
当稀疏矩阵 Ψ 被确定后，感知矩阵 A 是否满足RIP性质由测量矩阵 Φ 决定，许多实际情况表明，若取 Φ 为随机矩阵，则其以较大概率满足RIP，因而随机观测矩阵通常更有利于稀疏重建。

三、压缩感知重构算法

**压缩感知理论必须解决两个问题：测量矩阵的设计和高效稀疏恢复算法的开发。**这些算法通常分为四类：凸松弛、非凸松弛、贪婪算法、统计类算法。

1. 凸松弛法：这类方法通过将非凸问题转化为凸问题求解，找到信号的逼近。常见的算法包括基追踪（Basis Pursuit, BP）、梯度投影法（Gradient Projection for Sparse Reconstruction, GPSR）、迭代阈值法（Iterative Thresholding, IT）、迭代硬阈值法（Iterative Hard Thresholding, IHT）以及Bregman迭代法（Bregman Iterative, BI）等。
2. 贪婪算法：这类方法通过每次迭代时选择一个局部最优解来逐步逼近原始信号。常见的算法包括匹配追踪（Matching Pursuit, MP）、正交匹配追踪（Orthogonal Matching Pursuit, OMP）、分段匹配追踪（Stagewise Orthogonal Matching Pursuit, StOMP）、正则化正交匹配追踪（Regularized Orthogonal Matching Pursuit, ROMP）、压缩采样匹配追踪（Compressive Sampling Matching Pursuit, CoSaMP）、子空间追踪（Subspace Pursuit, SP）以及改进的后退型OMP（Improved Backward Optimized OMP, IBOOMP）等。
3. 组合算法：这类方法要求信号的采样支持通过分组测试快速重建，如傅立叶采样、链式追踪（Chaining Pursuit, CP）和HHS（Heavy Hitters on Steroids Pursuit, HHSP）追踪等。
4. 统计类算法：这类方法包括贝叶斯统计框架下的稀疏重建算法和基于训练集合学习的统计优化方法。这些方法利用典型信号的训练集通过学习的方法找出最优的线性投影集合。

其中重点关注的：

1. ADMM算法：
   • 分类：ADMM算法通常属于凸松弛法。它通过将复杂的优化问题分解为更简单的子问题来求解，特别适用于大规模优化问题。ADMM算法在处理具有可分离的凸优化问题时表现出色，广泛应用于统计学习、机器学习等领域。
   • 特点：ADMM算法的主要优点是处理速度快，收敛性能好。它通过引入拉格朗日乘子和惩罚参数，将原问题转化为增广拉格朗日函数，然后交替更新变量，逐步逼近最优解。
2. ISTA算法：
   • 分类：ISTA算法通常属于凸松弛法。它是一种迭代算法，用于求解带有L1范数正则项的优化问题，特别适用于稀疏信号重建和稀疏回归问题。
   • 特点：ISTA算法的基本思想是通过逐步优化的方式，每一步根据梯度信息更新当前的解，同时对解进行收缩处理，以实现L1正则化的效果。ISTA算法的关键在于如何有效地对解进行“收缩”（即设置阈值，使小于阈值的解变为零）从而达到稀疏的效果。尽管ISTA算法简单，但收敛速度较慢，尤其是在大规模数据上。

参考原链接：
https://zhuanlan.zhihu.com/p/22445302
https://zhuanlan.zhihu.com/p/599365659