【Compressive Sensing】压缩感知初体验

压缩感知 由E. J. Candes、J. Romberg、T. Tao 和D. L. Donoho于2004年被提出，并且其雏形早在该年前期便已出现。此问题暂不做深入探讨。

陶哲轩曾撰写过一篇关于压缩感知的科普文章《压缩感知与单像素相机》。撰写科普文章是一项罕见的能力——最顶尖的科学奖项很少有人具备这种技能。然而这也是一种值得探讨的话题——毕竟这项工作涉及了大量复杂的数学知识。让我们共同探讨这篇文章——作为新手尚有许多疑问尚未解答，请多包涵与指导！

1、文章中有这句话：两百万个像素 用8位灰度值就是2MB，16位灰度就是4MB。

由于这里处理的是灰度图像而非非黑即白的二值图像，在不压缩的情况下一个像素占用的空间较大：使用8位编码则每个像素占用1字节（即256种状态），而采用16位编码则每个像素占用2字节（即65536种状态）。

**
**

2、不太高级的压缩技术引出的问题。

从任意一张图像出发，在其可见区域内选择色调相近的小区域进行分析，并记录其尺寸、位置及色调特征。接着，在剩余区域继续寻找满足条件的部分直至所有可识别区域都被处理完毕。通过逆过程恢复出一张重建图像虽然质量有所降低但占用的空间却大大减少

该图像处理算法不适合在颜色突变显著的情况下使用，在实际应用中表现并不理想。由于在颜色突变过大的情况下（即右侧半区的平均色彩强度超过左侧区域），无法通过均匀的色块来表示图像特征；相反，则应采用“非均匀色块”来描述这一现象：当右侧半区的平均色彩强度超过左侧区域时，则可运用二维Haar小波变换进行分析；另外一种更为平滑的小波基函数也被提出用于减少误差积累。其基本思想在于将原始图像分解为不同尺度和方向上的小波系数，并记录具有显著强度的小波分量；对于这些未被捕捉到的关键细节部分，则采用零填充的方式予以替代即可。

JPEG 2000采用了离散小波变换（DWT），相较于"小波系数阈值法"而言更加精细。

而一张1024×2048像素的图像将具有约2亿个自由度（即独立变量），因此必须使用超过2千万个小波基函数才能实现完美重构。从小波基的角度来看，在这些大量小波系数中仅有少量是重要的关键频带（通道），其余大部分仅提供极少有用的信息量，并且这些剩余的小波系数可以通过去除冗余的信息来显著减少存储量和计算复杂度。例如，在这种情况下仅有约10万个重要的小波系数能够完整地恢复图像的主要特征

然而，在这种情况下我们无法确定哪1/256的小波基是最具价值的因此必须对全部的2, 56万项小波系数逐一计算以便筛选出其中最重要的1/4 million项这就意味着总共需要进行约2.56 million次运算这是一个非常庞大的工作量如果我们随机选择了这些小波系数中的1/4 million但不幸的是这些被选中的小波基并未包含图像中最关键的信息这意味着我们实际上去除了图像中最有价值的部分信息这无疑是一种得不偿失的做法

解决策略：采用非Wavelet算法来进行30万次测量——即使之前已经提到过Wavelet算法是最佳图像观察与压缩手段之一。实际上最优的选择应当是（伪）随机测量——例如生成30万个"滤镜"图像，并对真实图像与每个滤镜之间的相关性进行度量。这样得到的测量结果（即"相关度"）很可能呈现出极小且随机的特点。然而——这是关键点所在——图像中的2百万种可能的小波基函数在经过这些随机滤镜测量后会呈现出独特的特征：每一个基函数都会与某些滤镜呈现正相关关系，并与另一些滤镜呈现负相关关系；但会与绝大多数滤镜保持不相关状态。值得注意的是，在很高的概率下这2百万个特征彼此之间互不相同；甚至更为重要的是，在任意选取10万个线性组合时仍然能够保持独特性（从线性代数的角度来看这是因为30万维线性子空间中任意两个10万维子空间之间几乎必然存在分离现象）。因此基本上可以从这30万次随机数据中恢复出原始图像（至少能够重构出其中10万个主要细节）。简而言之我们正在探讨的是一个基于哈希函数的线性代数框架

意思如下 ：能够通过随机算法生成大量滤镜组件（约达几百万），其中包含着原始图像（约达两千万个）的信息内容。由于采用了随机化技术处理这些组件参数设置之间的关系，在处理过程中各参数设置之间具有高度独立性（互不影响）。通过这种处理方式得到了一组新的样本信息集合（约达三百万项），这些样本信息既包含了原始图像的信息特征又实现了有效的维度压缩（降维效果显著）。这一过程本质上就是构建了一种特殊的测量矩阵形式的过程。具体来说，在构建这种测量矩阵时需要满足以下两个关键条件：一是选择合适的基函数集合；二是合理设计采样频率参数设置方案。在此基础上我们就可以基于收集到的样本信息集合来实现对原始图像的精确重构（即能重建出足够的细节内容）。在这种情况下我们就能确保至少能够恢复出原始图像中包含的重要细节内容（如形状、颜色等关键特征）的数量达到三分之一以上

假如能够识别出2,百万系数中的约1.54百万关键数值（C(2,百万,十万)），那么我们就可以通过传统的线性代数方法来恢复图像信息。然而我们无法预判哪些数据点最为关键 ，这又如何能准确重构原始图像呢？我们可以运用最小二乘法计算出所有这些数据点所对应的值（即求解其在空间中的分布），从而得到一个由这些像素构成的完整图像；然而这种方法生成的结果往往会带有大量细小的噪声干扰（即所谓的颗粒噪声），这对于高质量的应用显然是不合适的。对于每一个可能的关键组合集合而言（即每一个可能的关键组合集合而言），我们需要分别进行一次完整的线性代数运算；但是这样的计算量实在太大了（具体来说就是C(2百万,十万)=约1e+17种可能性），这样一来计算所需的时间将远远超过现有技术的能力范围。

陶哲轩给出了两种可行的恢复原图像的方法：

NO.1、匹配追踪法(MP): 识别出与其观测数据高度相关的信号特征；从观测数据中剔除该特征的所有痕迹；反复操作直至所有数据均可用该特征进行合理解释。

看起来并不好懂，那就分步骤解释 吧：

从字典矩阵D（过完备原子库）中挑选一个与原始信号y最匹配的原子（即D中的某一列），具体方法是：对信号y与字典矩阵D中的每一列（即每个原子）进行内积运算，并选出具有最大绝对值的那个原子；这个被挑选出的原子就是当前迭代过程中与y最为匹配的一个原子。

用专业术语说：令信号

，从字典矩阵中选择一个最为匹配的原子，满足

，r0 表示一个字典矩阵的列索引。这样，信号 y 就被分解为在最匹配原子

的垂直投影分量和残值两部分，即：

。

2) 对残值R1f按照上面的步骤进行同样的分解，那么第K步可以得到：

， 其中

满足

。

可见，经过K步分解后，信号 y 被分解为：

，其中

。

需要说明的是：MP算法是收敛的，因为

，

和

正交，由这两个可以得出

，得出每一个残值比上一次的小，故而收敛。

我发现某些公式存在错误，并且由于我不太了解如何在此平台正确插入数学公式（如），这可能会给读者带来困扰。但相信大多数读者仍能理解这些公式的含义，并且只要掌握了基本原理就可以继续进行下去。

NO.2、**基追踪（又名L1模最小化）： 在能够与观测数据相匹配的所有小波组合中,找到一个具有最低非零元素数量的,即其各个系数绝对值之和尽可能小。这种优化过程通常会显著地抑制大部分系数,从而实现信号的稀疏表示。该优化问题可通过诸如单纯形法等凸优化方法在合理时间内求解。

听起来似乎也不太容易理解呢。也就是将一个0范数的问题转化为一个1范数的问题吧。因为0范数实际上代表的是向量中非零分量的数量嘛！不过这可是属于NP难问题哦！无法找到精确解的话就可以考虑将其转化为一个带有凸性的优化问题——也就是所谓的1范数优化模型了。而1范数指的是各个元素绝对值之和嘛！由于数据的稀疏性，在这种情况下我们希望绝对值总和尽可能小对吧？以后我们会详细讨论这个算法哦！下面引用一下甄亮利老师的一篇博客内容作为参考材料吧！

这篇文章的权威性是毋庸置疑的，但前面说了理解起来并不简单，因此本人也有些疑惑的地方 。

传统相机会捕捉每一个像素的亮度信息（如上述案例所示即为两百万个数据点），输出的结果会形成较大的文件（例如采用8位灰度度量则为2MB；采用16位则达到4MB）。从数学角度而言，则可将其视为由超高位矢量构成的数据对象（在此例中约为两百万维度）。

困惑：

2、关键是尽管“所有图片”所构成的空间要占用2MB的“自由度”或者说“熵”。

疑惑： 为何将其视为‘degrees of freedom’和‘entropy’？虽然degrees of freedom尚能被我所把握，但entropy却难以让我完全理解其含义。若仅从定性的角度去考量，则entropy可被看作是衡量混乱程度的一个指标。

在图像上进行恰当的配置或叫滤光片设置后进行测量每个像素的色彩强度是一种有效的途径

疑惑： 对这个计量方法不太熟悉。听起来像是将亮度高的像素筛选出来。

参考文献：

1、匹配追踪算法基本概念介绍

http://blog.sina.com.cn/s/blog_5156997b0101qu5f.html

2、An introduction to Sparse Representation

http://blog.sciencenet.cn/home.php?mod=space&uid=621576&do=blog&id=551052