The Introduction of Compressed Sensing (CS) Theory 西安工程大学理学院 李海洋 压缩感知理论简介 The Introduction of Compressed Sensing (CS) Theory 西安工程大学理学院 李海洋

1 背景介绍 1.1：传统采样理论简介 2 压缩感知理论主要研究内容 3 压缩感知应用-单像素CS相机 1.2：压缩感知理论的提出 2.1：信号的稀疏表示 2.2：观测矩阵的设计 2.3：信号重构 3 压缩感知应用-单像素CS相机

1.1 传统采样理论简介 Nyquist-Shannon 采样定律 JEPG等 信号 采样 压缩 传输 重构 传统的信号处理过程

传统的基于Nyquist-Shannon 采样定理指导下的信息采样理论的不足主要表现在以下两个方面：

2、另一方面，在实际应用中，为了降低信号的存储、处理和传输成本，人们又不得不经由压缩方式减少信号表示的比特数，以此抛弃认为不重要的数据，这种高速采样再抛弃的过程显然是对采样资源的巨大浪费。

1.2 压缩感知理论的提出 既然传统方法采样的多数数据会被抛弃，那么，为什么还要获取全部数据而不直接获取需要保留的数据呢？ 1.2 压缩感知理论的提出 既然传统方法采样的多数数据会被抛弃，那么，为什么还要获取全部数据而不直接获取需要保留的数据呢？ 采集很少一部分数据并且期望从这些少量数据中解压出大量信息，有无这种可能呢？D. Donoho, Candes，T. Tao 等人证明了如果信号具有稀疏性的特性，那么就可能存在一种算法能够从这些少量的数据中还原出原先的信息。

信号 采样 压缩 压缩 感知 信号 传输 重构

2 压缩感知理论主要研究内容 2.1：信号的稀疏表示 2.2：观测矩阵的设计 2.3：信号重构

2.1 信号的稀疏表示 稀疏性的定义： 一个实值有限长的N维离散信号 ，它可以用一个标准正交基 2.1 信号的稀疏表示 稀疏性的定义： 一个实值有限长的N维离散信号 ，它可以用一个标准正交基 的线性组合来表示，其中 表示矩阵 的转置，那么有 其中 ，若 在基 上仅有 个非零系数 时，称 为信号 的稀疏基， 是 稀疏(K-Sparsity)的。

如图是一个稀疏度为3的稀疏变换， , 向量 基本都是非零值， 但将其变换到 域 时，非零值就只有3 个了，数目远小于 原来的非零数目，实 现了信号的稀疏表 示。

如何寻找信号的最佳稀疏域呢？ 这是压缩感知理论的基础和前提，也是信号精确重构的保证。对稀疏表示研究主要有两个方面： （1）基函数字典下的稀疏表示： 寻找一个正交基使得信号表示的稀疏系数尽可能的少。比较常用的基有：高斯矩阵、小波基、正（余）弦基、Curvelet基等。Candes和Tao经研究发现光滑信号的Fourier 系数、小波系数、有界变差函数的全变差范数、振荡信号的Gabor 系数及具有不连续边缘的图像信号的Curvelet 系数等都具有足够的稀疏性,可以通过压缩感知理论恢复信号。

（2）超完备库下的稀疏表示： 用超完备的冗余函数库来取代基函数，称之为冗余字典，字典中的元素被称之为原子，目的是从冗余字典中找到具有最佳线性组合的K项原子来逼近表示一个信号，称作信号的稀疏逼近或高度非线性逼近。 一是如何构造这样一个适合某一类信号的冗余字典； 二是在已知冗余字典的前提下如何设计快速有效的分解方法来稀疏地表示某一个信号。

观测器的目的是采样得到 个观测值，并保证从中能够重构出原来长度为 的信号 或者稀疏基下的系数向量 。 2.2 观测矩阵的设计 观测器的目的是采样得到 个观测值，并保证从中能够重构出原来长度为 的信号 或者稀疏基下的系数向量 。 观测过程就是利用 观测矩阵的 个行向量对稀疏系数向量进行投影，得到 个观测值，即

如果我们假设信号已经是稀疏的，那么上面的方程就可以写作

观测矩阵要满足什么样的条件呢？ 从上式中求出 是一个线性方程组的求解问题，但由于方程的个数远远少于未知数的个数，即 ，因此，一般说来，该方程组有无穷多个解 。 但如果 具有稀疏性，则有可能求出确定解。Candes、Tao等人提出必须保证观测矩阵不会把两个不同的 稀疏信号映射到同一个采样几何中，即上述线性方程组的稀疏解具有唯一性。

目前，关于测量矩阵的研究主要基于以下两个方面： １　 RIP条件： ２　相干性：

　　　随机矩阵、结构随机矩阵与确定性矩阵. 虽然随机矩阵能产生尺寸接近最优的RIP 矩阵。 在工程实际中, 人们更希望构造一个确定性RIP矩阵。因为确定性矩阵更利于工程设计, 此外, 从构造解码算法角度来看, 确定性矩阵利于降低内存、设计快速的恢复算法等。然而, 现在仍然缺少令人满意的确定性RIP 矩阵构造方法。结构随机矩阵. 与确定性矩阵相比, 结构随机矩阵多了些随机性, 因而可以证明其具有较好的RIP 性质, 同时, 结构随机矩阵的随机性较弱, 一般仅具有行随机性。

2.3 信号重构 首先介绍范数的概念。向量的p-范数为： 当p=0时得到0-范数，它表示上式中非零项的个数。 2.3 信号重构 首先介绍范数的概念。向量的p-范数为： 当p=0时得到0-范数，它表示上式中非零项的个数。 由于观测数量 ，不能直接求解，在信号 能稀疏表示的前提下，求解方程组的问题转化为最小0-范数问题：

对于0-范数问题的求解是个NP问题，在实际应用中很难获得问题的可行解。因此，寻求对以上问题的松弛以获得理想的逼近解，已成为稀疏信号重构的重要手段。一种自然的想法是，用下面的模型来代替，我们称之为p-范数优化问题（0<p<=1）： 或者： 求解该最优化问题，得到稀疏域的系数，然后反变换即可以得到时域信号。

目前出现的重构算法主要有： 1）第一类贪婪算法：这类算法是通过每次迭代时选择一个局部最优解来逐步逼近原始信号，典型的贪婪算法--MP算法，贪婪算法是针对组合优化提出, 目前已发展了多种变形，例如，OMP, OOMP, CosMP等。该类重建算法速度快, 然而需要的测量数据多且精度低。 2）第二类凸优化算法：即1-范数优化问题，这类方法是将非凸问题转化为凸问题求解找到信号的逼近，如BP算法，梯度投影方法等。该类算法速度慢，然而需要的测量数据少且精度高。

　　　但是基于 1-范数优化问题的信号重构至少存在两个方面的不足：（1）数据之间还可能存在很大的冗余难以去除； （2）无法区分稀疏尺度的位置（尽管重构信号在欧式距离上逼近原始信号, 但会出现低尺度的能量转移到高尺度的现象, 因而易出现高频震荡现象）。 ３）p-范数优化问题。 　Xu 等人对1/2-范数优化问题的正则化问题进行了深入的研究，给出了问题的解析解，并从数值实验的角度说明了该问题的解具有较 1-范数重构更好的稀疏性，且p越小，稀疏性越好。

3 压缩感知应用--单像素CS相机 运用压缩感知原理，RICE大学成功研制了单像素CS相机。 传统百万像素的相机需要百万个探测传感器，而压缩传感数码相机只使用一个探测器来采光，然后跟捕获后的计算相结合来重构图像。这种样机的镜头由两部分组成：一个光电二极管和一个微镜阵列。 　该相机直接获取的是M次随机线性测量值而不是获取原始信号的N 个像素值，为低像素相机拍摄高质量图像提供了可能。

“数字微镜阵列”完成图像在伪随机二值模型上的线性投影的光学计算，其反射光由透镜聚焦到单个光敏二极管上，光敏二极管两端的电压值即为一个测量值y，将此投影操作重复M次，即得到测量向量Y， 然后用最小全变分算法构建的数字信号处理器重构原始图像x。 数字微镜器件由数字电压信号控制微镜片的机械运动以实现对入射光线的调整，相当于随机观测矩阵。

　现为美国　Stanford University 人文科学讲座教授及统计学教授。他是美国人文与科学学院院士、美国工业与应用数学学会(SIAM) 院士、法国科学院外籍院士及美国国家科学院院士。 统计学会会长奖 （1994） 邵逸夫数学科学奖 （2013）

Emmanuel Candes 是斯坦福大学的数学、统计学，电子工程荣誉教授，同时也是应用计算数学领域的教授。Emmanuel Candes教授曾获数项国际奖项，包括国家科学基金会最高个人奖项。 ICM2014被邀请做1小时报告。

谢谢大家！