压缩感知小结 #

最近在写学校要求的总结，顺便整理了一下之前看过的压缩感知的内容。

压缩感知是2006年由陶哲轩等人于文章中共同提出的，文中首先提出了有限等距性质（RIP）。之后RIP作为理论基础被广泛引用于各类压缩感知文献，是信号处理领域一个重大的发现。压缩感知中的采样模型为$y=\Theta x$。其中$s$是$k$稀疏的信号（即向量$s$中有$k$个非零分量），$y$是观测到的结果，$\Theta$是重建矩阵。但是一般来说，我们能够拿到的数据x都不是稀疏的结果，所以往往就需要使用某些变换域下的稀疏基，作为基底，将原始的数据x转换为稀疏基底上的稀疏系数s。那么常用的稀疏基底就是傅里叶基、小波基，分别对应傅里叶变换和小波变换。近年来也有一些稀疏基方面的研究，比如curvelet、shearlet等，这些基底基于小波变换，稀疏性质要优于小波变换。假设我们选定了变换域之后对数据x进行了变换，由于这些变换都是线性的，那么可以写作$x=\Psi s$。而之前的采样模型可以描述为由采样矩阵构建$\Phi$的$y=\Phi x=\Phi \Psi s$，于是有重建矩阵$\Theta =\Phi \Psi$。

根据信号处理中著名的“香农-奈奎斯特采样定理”，在将一个模拟信号转换为数字信号时，需要至少以模拟信号中最高频率的两倍的采样频率进行采样，才能保证采样后的数字信号保存了模拟信号中的信息。但是根据“有限等距性质”，对于一个$k$稀疏的向量$s$，只要在采样时，重建矩阵$\Theta$满足下式（$k$阶RIP）：

$1-\delta \le \frac{|\Theta u{|}_2}{|u{|}_2}\le 1+\delta$，

即可从采样结果$\Theta s$中重建出信号$s$，其中$u$是任意的$2k$稀疏向量，$\delta$是一个大于$0$的常数，$\delta$要尽可能得小。该性质是充分的，但是它很难被验证，因为u需要是任意的k稀疏信号且$\delta$的值难以评估。有另外一种描述方式是使用矩阵的spark常数来评估重建矩阵$\Theta$的性质，只要矩阵$\Theta$的spark常数大于$2k$，那么$k$稀疏的信号$s$可以由采样结果$\Theta s$恢复出来。这里的spark常数与矩阵的秩类似。众所周知，矩阵的秩是指矩阵中最大的不线性相关的行（列）数，spark常数则是矩阵的最小线性相关行（列）数，对于重建矩阵$Theta$，我们考虑的是列方向上的相关性。例如矩阵

$\begin{array}{ccc}1& 0& 2\\ 0& 3& 0\\ 0& 0& 0\end{array}$

的spark常数就是2，而矩阵

$\begin{array}{ccc}1& 0& 2\\ 0& 3& 1\\ 0& 0& 0\end{array}$

的spark常数则是3。

对于RIP，不加证明得直观来看，是要求在采样后仍然能保持原有数据的距离信息，试想对于一个稀疏的信号，如果在采样时没有采样到关键的分量（绝对值大的分量），那么自然是无法满足RIP性质的，因此RIP其实是保证了设计出的重建矩阵要捕捉到关键信息。RIP和spark常数其实是十分接近的。可能我们都会注意到，在用spark常数的评估重建矩阵的性质时，针对的对象是$k$稀疏的信号，但是spark却要求是$2k$的。这是因为对于任意两个$k$稀疏的信号，他们作差后得到的信号自然最差是一个$2k$稀疏的信号。而在观测信号时，增加一个与之前的观测线性相关的新观测是没有意义的，因为这个新的观测结果本身就可以从之前的观测中线性组合出来，根本无法得到额外的信息。恰好$\Theta$的spark常数大于$2k$，意味着经过采样后，两个$k$稀疏的信号的差距（距离）被保持了，也就是说是k稀疏的信号经过采样后仍然是可以区分的。

虽然有了RIP和spark常数这两个性质来评估重建矩阵，采样矩阵$\Phi$仍然很难设计，所幸大量实践证明，随机的采样矩阵的性质已经足够优秀[3]。事实上在采样设备的物理实现中，常常使用的设计也是由伯努利分布生成的0/1矩阵。这样的0/1矩阵中，$0$代表未观测到的信息，$1$表示进行了观测。整个问题的数学模型和理论基础至此介绍完毕。

其实这类问题有一些通用的解法，在这里做简要总结。首先是基于凸优化的方法，构建一个损失函数作为优化的目标。损失函数中包含一个重建误差的损失项和先验条件的损失项。先验条件可以是在变换域上的稀疏性假设，也可以是由图像性质衍生出的限制如图像各个局部的相关性等。通过先验条件来限定解空间的范围，在受限的解空间内求得最优解。还有一类方法是构建子空间的贪心算法，如正交匹配追踪（OMP）算法，每次选取重建矩阵中一个与残差内积最大的列，OMP认为该列的观测与剩余的列的观测相比，包含了最多的信息，之后使用最小二乘法和选取出的列组成的新重建矩阵来更新对稀疏系数和残差的估计，算法在残差降低到一定阈值后停止。但是这类贪心法的误差往往较大，精确恢复所需的观察数量很大。也有的算法假设图像各块生成于高斯混合模型，通过拟合生成式的高斯混合模型生成出图像。值得关注的是，最近深度学习的技术也被广泛应用到了压缩感知中：ISTA-Net通过将更新过程展开至一个深度神经网络，获得了非常好的重建效果（基于稀疏表示的假设，在每个phase中用卷积找到稀疏表示，由于主要使用卷积，模型也很小）；Tensor ADMM-Net则将Tensor的低秩（使用tensor的核范数）和ADMM框架整合到深度神经网络中，同样效果显著。这两者都属于探索可解释的网络的例子，将数值更新算法展开成了网络。$\lambda$-Net只做了超光谱的实验，是基于U-Net端到端的实现。

有一篇很好的文章，写Plug and Play ADMM的框架下重建算法的收敛性证明。事实上，Plug and Play ADMM框架恰好就是上面第一类优化方法的框架。这些方法都可以视作是一个损失函数梯度方向上的有限的更新加上一个受限的降噪过程（文中定义了bounded gradient和bounded denoiser两个概念）。更进一步，我们甚至不需要写出一个具体的损失函数，也不需要一个具体的数学推导过程，也不需要将先验条件形式化。只要选用一个更新方法，可以是ADMM框架，可以是ISTA/FISTA算法，可以是Alternating Projection的方式，更新后再选用一个或一些降噪处理的方法，组合起来进行迭代就可以重建出图像了。对于类似的问题，该方案也是通用的。

综述文章：M. Rani, S. B. Dhok, and R. B. Deshmukh, “A systematic review of compressive sensing: Concepts, implementations and applications,” IEEE Access, vol. 6, pp. 4875–4894, 01 2018.

优化角度比较通用的Plug-and-Play ADMM框架及其收敛性证明：S. H. Chan，X. Wang and O. A. Elgendy, “Plug-and-Play ADMM for Image Restoration: Fixed Point Convergence and Applications”, arXiv, 2016.