1.2.3  压缩感知非线性重建

压缩感知重建是指利用已知的测量矩阵 和测量值向量 ，通过合适的算法重建原始信号 的过程。相对于线性的测量过程（2），压缩感知重建是非线性的。Candes等证明在一定的条件下稀疏信号的压缩感知重建问题可转化为求解如下最小化 范数 问题：

                        （5）

式（5）表明在一定条件下原始信号 实为满足测量方程（2）的最稀疏解。

由于 问题（5）是组合优化问题，求解该式需要列举出 中非零系数中 种排列可能，问题本身是一个NP难问题，求解过程复杂且结果不稳定。后来，一些学者提出了用 范数代替 范数的方法，两种方法所得结果等价：

                        （6）

(6)式的过程使得问题变成了一个凸优化问题，而此类问题可以转化成线性规划问题求解。求解算法有多种，常用的如共轭梯度投影法，迭代阈值法，内点法，基追踪算法等。

事实上，在多数实际应用中，噪声是存在的。为了消除噪声影响，通常通过改变问题（6）的约束限制条件来解决：

                  （7） 

近年来，关于（7）式的解法已经有许多都被研究出，但是这些重建方法的核心都是重建计算复杂度与重建质量之间的一个取舍的问题。无论选来择何种取舍，这些方法都面临着大规模压缩感知重建的问题，比如一般的图像或者更高维的视频图像的重建问题，这些问题，似乎都是一些需要大量耗时的问题。

2   二维图像压缩感知测量与重建

我们知道，一维信号可以表示为向量的形式，二维图像信号则可以表示为矩阵的形式。通过数学方法，我们可以将二维的矩阵信号列向量化，从而得到该信号的一维的表示形式。这也就意着，我们可以将传统的一维信号压缩感知测量与重建的方法直接运用到经过列向量化变换的二维图像的压缩感知测量与重建的过程中。然而，随着问题维数的增高，这种传统方法面临着计算复杂和存储困难的问题。因此，人们将目光转移到基于块的压缩感知问题的研究上。本章将对传统的以及基于块的信号的压缩感知测量与重建方法进行详尽的介绍。

2. 1  传统的二维图像压缩感知测量与重建方法论文网

2.1.1  传统的二维图像压缩感知测量过程

压缩感知理论指出，如果在某一稀疏变换基 的作用下，信号 是稀疏的或可压缩的，则可以通过一个 的随机测量矩阵 ，对 维信号 进行采样，得到 维的测量值 ， 。由 得到 的过程就是压缩感知的测量过程，又称为采样，可表示为:

通常称 为采样率。

图像信号是二维信号，图像 通常可以表示为一个 的矩阵。我们可以将 列向量化为一个 的一维向量信号 。从而，可以沿用一维信号的压缩感知测量过程，选取 的测量矩阵 ，对 维信号 进行采样，得到 维的测量值 。

2.1.2  传统的二维图像压缩感知重建过程

与一维信号重建过程类似，我们可以直接运用一维信号的压缩感知重建算法比如BP算法，GPSR算法，PL算法[12]等来进行二维信号的直接重建。最后，只需将重建得到的一维信号 还原为二维信号 。

事实上，上述重建方法忽略了图像的二维几何结构，重建结果还有待提高。并且，这种将二维图像看作一维信号的直接重建过程面临着许多难题，比如：计算复杂度，大量数据的存储困难等。因此，学者们经过研究，得到了基于块的二维图像压缩感知重建方法。我们将在下一节对此方法进行较深入的介绍。