最近有不少人问我究竟"压缩感知"是什么意思（特别是随着最近这个概念名声大噪），所谓“单像素相机”又是怎样工作的（又怎么能在某些场合比传统相机有优势呢）。这个课题已经有了大量文献，不过对于这么一个相对比较新的领域，还没有一篇优秀的非技术性介绍。所以笔者在此小做尝试，希望能够对非数学专业的读者有所帮助。
具体而言我将主要讨论摄像应用，尽管压缩传感作为测量技术应用于比成像广泛得多的领域（例如天文学，核磁共振，统计选取，等等），我将在帖子结尾简单谈谈这些领域。
相机的用途，自然是记录图像。为了简化论述，我们把图像假设成一个长方形阵列，比如说一个1024x2048像素的阵列（这样就总共是二百万像素）。为了省略彩色的问题（这个比较次要），我们就假设只需要黑白图像，那么每个像素就可以用一个整型的灰度值来计量其亮度（例如用八位整型数表示0到255，16位表示0到65535）。
接下来，按照最最简化的说法，传统相机会测量每一个像素的亮度（在上述例子中就是二百万个测量值），结果得到的图片文件就比较大（用8位灰度值就是2MB，16位灰度就是4MB）。数学上就认为这个文件是用超高维矢量值描绘的（在本例中就是约二百万维）。
在我开始讲“压缩感知”这个新故事之前，必须先快速回顾一下“老式压缩”的旧故事。（已经了解图像压缩算法的读者可以跳过这几段。）
怎么样压缩图像？方式多种多样，其中有些非常先进，不过我来试试用一种不太高科技的（而且也不太精确的）说法来描述一下这些先进技术。图像通常都含有大片无细节部分--比如在风景照里面，将近一半的画面都可能被单色的天空背景占据。我们假设提取一个大方块，比方说100x100像素，其中完全是同一颜色的——假设是全白的吧。无压缩时，这个方块要占10000字节存储空间（按照8位灰度算）；但是我们可以只记录这个方块的维度和坐标，还有填充整个方块的单一颜色；这样总共也只要记录四五个字节，省下了可观的空间。不过在现实中，压缩效果没有这么好，因为表面看来没有细节的地方其实是有着细微的色差的。所以，给定一个无细节方块，我们记录其平均色值，就把图片中这一块区域抽象成了单色色块，只留下微小的残余误差。接下来就可以继续选取更多色彩可见的方块，抽象成单色色块。最后剩下的是亮度（色彩强度）很小的，肉眼无法察觉的细节。于是就可以抛弃这些剩余的细节，只需要记录那些“可见”色块的大小，位置和亮度。日后则可以反向操作，重建出比原始图像质量稍低一些，占空间却小得多的复制图片。
其实上述的算法并不适合处理颜色剧烈变动的情况，所以在实际应用中不很有效。事实上，更好的办法不是用均匀色块，而是用“不均匀”的色块——比方说右半边色彩强度平均值大于左半边这样的色块。这种情况可以用（二维）Haar小波系统来描述。后来人们又发现一种"更平滑的"小波系统更能够避免误差，不过这都是技术细节，我们就不深入讨论了。然而所有这些系统的原理都是相同的：把原始图像表示为不同“小波（类似于上文中的色块）”的线性叠加，记录显著的（高强度的）小波的系数，放弃掉（或者用阈值排除掉）剩下的小波系数。这种“小波系数硬阈值”压缩算法没有实际应用的算法（比如JPEG2000标准中所定义的）那么精细，不过多少也能描述压缩的普遍原理。
总体来讲（也是非常简化的说法），原始的1024x2048图像可能含有两百万自由度，想要用小波来表示这个图像的人需要两百万个不同小波才能完美重建。但是典型的有意义的图像，从小波理论的角度看来是非常稀疏的，也就是可压缩的：可能只需要十万个小波就已经足够获取图像所有的可见细节了，其余一百九十万小波只贡献很少量的，大多数观测者基本看不见的“随机噪声”。（这也不是永远适用：含有大量纹理的图像--比如毛发、毛皮的图像——用小波算法特别难压缩，也是图像压缩算法的一大挑战。不过这是另一个故事了。）
接下来呢，如果我们（或者不如说是相机）事先知道两百万小波系数里面哪十万个是重要的，那就可以只计量这十万个系数，别的就不管了。（在图像上设置一种合适的“过滤器”或叫“滤镜”，然后计量过滤出来的每个像素的色彩强度，是一种可行的系数计量方法。）但是，相机是不会知道哪个系数是重要的，所以它只好计量全部两百万个像素，把整个图像转换成基本小波，找出需要留下的那十万个主导基本小波，再删掉其余的。（这当然只是真正的图像压缩算法的一个草图，不过为了便于讨论我们还是就这么用吧。）
这就是压缩传感的用武之地了。其理论依据是：如果只需要10万个分量就可以重建绝大部分的图像，那何必还要做所有的200万次测量，只做10万次不就够了吗？（在实际应用中，我们会留一个安全余量，比如说测量30万像素，以应付可能遭遇的所有问题，从干扰到量化噪声，以及恢复算法的故障。）这样基本上能使节能上一个数量级，这对消费摄影没什么意义，对传感器网络而言却有实实在在的好处。
不过，正像我前面说的，相机自己不会预先知道两百万小波系数中需要记录哪十万个。要是相机选取了另外10万（或者30万），反而把图片中所有有用的信息都扔掉了怎么办？
然而这种方式仍然存在两个技术问题。首先是噪声问题：10万个小波系数的叠加并不能完全代表整幅图像，另190万个系数也有少许贡献。这些小小贡献有可能会干扰那10万个小波的特征，这就是所谓的“失真”问题。第二个问题是如何运用得到的30万测量数据来重建图像。
需要注意到的是，这类图像恢复算法还是需要相当的运算能力的（不过也还不是太变态），不过在传感器网络这样的应用中这不成问题，因为图像恢复是在接收端（这端有办法连接到强大的计算机）而不是传感器端（这端就没办法了）进行的。
由于压缩传感还是一个相当新的领域（尤其是严密的数学结果刚刚出现），现在就期望这个技术应用到实用的传感器上还为时尚早。不过已经有概念验证模型出现了，其中最著名的是Rice大学研制的单像素相机。
最后必须提到的是，压缩传感技术是一种抽象的数学概念，而不是具体的操作方案，它可以应用到成像以外的许多领域。以下只是其中几个例子：
磁共振成像(MRI)。在医学上，磁共振的工作原理是做许多次（但次数仍是有限的）测量（基本上就是对人体图像进行离散拉东变换（也叫X光变换）），再对数据进行加工来生成图像（在这里就是人体内水的密度分布图像）。由于测量次数必须很多，整个过程对患者来说太过漫长。压缩传感技术可以显著减少测量次数，加快成像（甚至有可能做到实时成像，也就是核磁共振的视频而非静态图像）。此外我们还可以以测量次数换图像质量，用与原来一样的测量次数可以得到好得多的图像分辨率。
线性编码。压缩传感技术提供了一个简单的方法，让多个传送者可以将其信号带纠错地合并传送，这样即使输出信号的一大部分丢失或毁坏，仍然可以恢复出原始信号。例如，可以用任意一种线性编码把1000比特信息编码进一个3000比特的流；那么，即使其中300位被（恶意）毁坏，原始信息也能完全无损失地完美重建。这是因为压缩传感技术可以把破坏动作本身看作一个稀疏的信号（只集中在3000比特中的300位）。
许多这种应用都还只停留在理论阶段，可是这种算法能够影响测量和信号处理中如此之多的领域，其潜力实在是振奋人心。笔者自己最有成就感的就是能看到自己在纯数学领域的工作（例如估算傅立叶子式的行列式或单数值）最终具备造福现实世界的前景。
压缩感知从字面上看起来，好像是数据压缩的意思，而实则出于完全不同的考虑。经典的数据压缩技术，无论是音频压缩（例如mp3），图像压缩（例如jpeg），视频压缩（mpeg），还是一般的编码压缩（zip），都是从数据本身的特性出发，寻找并剔除数据中隐含的冗余度，从而达到压缩的目的。这样的压缩有两个特点：第一、它是发生在数据已经被完整采集到之后；第二、它本身需要复杂的算法来完成。相较而言，解码过程反而一般来说在计算上比较简单，以音频压缩为例，压制一个mp3文件的计算量远大于播放（即解压缩）一个mp3文件的计算量。
稍加思量就会发现，这种压缩和解压缩的不对称性正好同人们的需求是相反的。在大多数情况下，采集并处理数据的设备，往往是廉价、省电、计算能力较低的便携设备，例如傻瓜相机、或者录音笔、或者遥控监视器等等。而负责处理（即解压缩）信息的过程却反而往往在大型计算机上进行，它有更高的计算能力，也常常没有便携和省电的要求。也就是说，我们是在用廉价节能的设备来处理复杂的计算任务，而用大型高效的设备处理相对简单的计算任务。这一矛盾在某些情况下甚至会更为尖锐，例如在野外作业或者军事作业的场合，采集数据的设备往往曝露在自然环境之中，随时可能失去能源供给或者甚至部分丧失性能，在这种情况下，传统的数据采集-压缩-传输-解压缩的模式就基本上失效了。
压缩感知的概念就是为了解决这样的矛盾而产生的。既然采集数据之后反正要压缩掉其中的冗余度，而这个压缩过程又相对来说比较困难，那么我们为什么不直接「采集」压缩后的数据？这样采集的任务要轻得多，而且还省去了压缩的麻烦。这就是所谓的「压缩感知」，也就是说，直接感知压缩了的信息。
可是这看起来是不可能的事情。因为压缩后的数据并不是压缩前的数据的一个子集，并不是说，本来有照相机的感光器上有一千万个像素，扔掉其中八百万个，剩下的两百万个采集到的就是压缩后的图像，──这样只能采集到不完整的一小块图像，有些信息被永远的丢失了而且不可能被恢复。如果要想采集很少一部分数据并且指望从这些少量数据中「解压缩」出大量信息，就需要保证：第一：这些少量的采集到的数据包含了原信号的全局信息，第二：存在一种算法能够从这些少量的数据中还原出原先的信息来。
有趣的是，在某些特定的场合，上述第一件事情是自动得到满足的。最典型的例子就是医学图像成像，例如断层扫描（CT）技术和核磁共振（MRI）技术。对这两种技术稍有了解的人都知道，这两种成像技术中，仪器所采集到的都不是直接的图像像素，而是图像经历过全局傅立叶变换后的数据。也就是说，每一个单独的数据都在某种程度上包含了全图像的信息。在这种情况下，去掉一部分采集到的数据并不会导致一部分图像信息永久的丢失（它们仍旧被包含在其它数据里）。这正是我们想要的情况。
上述第二件事就要归功于陶哲轩和坎戴的工作了。他们的工作指出，如果假定信号（无论是图像还是声音还是其他别的种类的信号）满足某种特定的「稀疏性」，那么从这些少量的测量数据中，确实有可能还原出原始的较大的信号来，其中所需要的计算部分是一个复杂的迭代优化过程，即所谓的「L1-最小化」算法。
把上述两件事情放在一起，我们就能看到这种模式的优点所在。它意味着：我们可以在采集数据的时候只简单采集一部分数据（「压缩感知」），然后把复杂的部分交给数据还原的这一端来做，正好匹配了我们期望的格局。在医学图像领域里，这个方案特别有好处，因为采集数据的过程往往是对病人带来很大麻烦甚至身体伤害的过程。以X光断层扫描为例，众所周知X光辐射会对病人造成身体损害，而「压缩感知」就意味着我们可以用比经典方法少得多的辐射剂量来进行数据采集，这在医学上的意义是不言而喻的。
这一思路可以扩展到很多领域。在大量的实际问题中，我们倾向于尽量少地采集数据，或者由于客观条件所限不得不采集不完整的数据。如果这些数据和我们所希望重建的信息之间有某种全局性的变换关系，并且我们预先知道那些信息满足某种稀疏性条件，就总可以试着用类似的方式从比较少的数据中还原出比较多的信号来。到今天为止，这样的研究已经拓展地非常广泛了。但是同样需要说明的是，这样的做法在不同的应用领域里并不总能满足上面所描述的两个条件。有的时候，第一个条件（也就是说测量到的数据包含信号的全局信息）无法得到满足，例如最传统的摄影问题，每个感光元件所感知到的都只是一小块图像而不是什么全局信息，这是由照相机的物理性质决定的。为了解决这个问题，美国Rice大学的一部分科学家正在试图开发一种新的摄影装置（被称为「单像素照相机」），争取用尽量少的感光元件实现尽量高分辨率的摄影。有的时候，第二个条件（也就是说有数学方法保证能够从不完整的数据中还原出信号）无法得到满足。这种时候，实践就走在了理论前面。人们已经可以在算法上事先很多数据重建的过程，但是相应的理论分析却成为了留在数学家面前的课题。
坎迪斯希望屏幕上的模型图像变得稍微清晰一些。但是，他突然发现用残缺的数据渲染出来的图像是那么细腻完美，对每个细节而言都是如此，这简直就像变魔术一样。太不可思议了，他认为。“这就好像，你给了我十位银行账号的前三位，然后我能够猜出接下来的七位数字。”他说。他尝试在不同类型的模型图像上重新进行这个实验，结果都非常好。
压缩感知的原理是这样的：你有一张图片，假设是总统的肾脏图片，这不是关键。图片由一百万个像素构成。对传统成像来说，你不得不进行一百万次量度。而采用压缩感知技术，你只需要量度一小部分，好比说从图像的不同部分随机抽取十万个像素。从这里开始，有大量的实际上是无穷多的方式填充那剩余的九十万个像素点。
寻找那个唯一正确的表示方式的关键在于一种叫稀疏度的概念。所谓稀疏度，是描述图像的复杂性或者其中所缺的一种数学方法。一幅由少数几个简单、可理解的元素（例如色块或者波浪线构成的图片）是稀疏的；满屏随机、散乱的点阵则不是稀疏的。原来在无限多的可能性中，最简单、最稀疏的那幅图像往往就是正解，至少很接近正解。
这样，在输入不完整的图像后，算法开始试着用大色块来填充空白区。如果有一团绿色的像素点聚集在一起，算法可能会用一个大的绿色矩形填充它们之间的空间;而如果是一团黄色的像素点，那么就用黄色的矩形来填充。在不同颜色交错散布的区域，算法会使用越来越小的矩形或其他形状填充各种颜色之间的空间。算法会重复这样的过程，最终，得到一幅由最少的可能的色块构成的图像，它的一百万像素都已被彩色填满。
并不能绝对保证这样的图像就是最稀疏的，或者正是你所试图重建的那个。但是坎迪斯和陶哲轩已经从数学上证明了，它的错误率是无穷小的。算法运行可能还是需要几个小时，但是，让电脑多跑一个小时，总好过让孩子在额外的一分钟里停止呼吸。
压缩感知已经产生了令人惊叹的科学影响。这是因为每一个有趣的信号都是稀疏的，只要你能够正确定义它的稀疏性。例如，钢琴和弦的乐音是一小组不超过五个纯音符的组合。在所演奏的音频中，只有少部分频率包含有效的音乐信息，而其余大部分频段是一片无声地带。因此，你可以用压缩感知技术从“欠采样”的老旧唱片中重建出当时的乐章，而不用担心失去了由特定频率构成的声波的信息。只需要你手头的材料，就可以用L1范数极小化法以稀疏方式填补空白，从而获得与原音一般无二的旋律。
带着建筑师式的眼睛，顶着略显蓬松的头发，坎迪斯散发着时尚极客的气息。这个39岁的法国人语气温和，但是面对他认为不达标的事情绝不妥协。“不，不，他说的没有道理。”当我提到压缩感知领域某个和他有些观点有着细小差别的专家的工作时，他如是说，“不，不，不，不。那没有道理，没道理，是错的。”
坎迪斯曾经预见，将来会有大量应用技术是以他的研究成果作为理论基础的。他举例说道，在未来，这项技术不会仅仅用在磁共振成像仪上。例如，数码相机收集了大量信息，然后压缩图像。但是，至少在压缩感知技术可用的情况下，压缩是一种极大的浪费。如果你的相机记录了大量的数据，却在压缩时丢弃了其中的90%，那么为什么不在一开始就只记录10%的数据从而节省电池电量和内存？对于您的孩子的数码快照，费电可能没什么大不了，你只要插上电源为相机充电就可以了。“但是，当废电池多到可以环绕木星，”坎迪斯说，“结果就不是那么简单了”。同样，如果你希望自己的相机能够拍摄万亿像素的照片而不是几百万像素，你就必须使用压缩感知技术。
从信息的小样本中收集有用数据的能力也引起了军方的重视：比如，敌方通信可能从一个频率跳到另一个频率。但是，还没有一种硬件设备能以足够快的速度扫描整个频域。但是无论在什么情况下，对手的信号都是稀疏的，是由频段内极少数的某种简单信号构成的，出现在一些相对较小却未知的频段。这意味着压缩感知可以用来从“噼啵”声中区分来自任意波段的敌人的交谈。所以不出意外的，美国国防部先进计划研究署正在支持压缩感知技术的研究。
压缩感知不仅可以用于解决现在的技术难题。将来，它还将帮助我们处理已存储的大量信息。每天，全世界都要产生数不清的数据，我们希望这些数据安全、有效、可恢复地保存起来。目前，我们大部分的视听信息都是用复杂的压缩格式存储起来的。如果有一天，这种格式被淘汰了，你不得不进行痛苦的格式转换。但是坎迪斯相信，在拥有压缩感知技术的未来，对于采用高成本红外技术拍摄的天文图像，只需要拍摄到20％的像素就可以了。因为我们一开始就只记录了极少部分的数据，所以不需要再进行压缩。那么我们只需要逐步改进数据的解析算法，而不是数据的压缩算法，就可以精确地恢复出原始图像了。
上面说的都是将来的事情。今天，压缩感知技术已经改写了我们获取医学信息的方式。在GE医疗集团的参与下，威斯康辛大学的一个研究小组正在把压缩感知技术与HYPR和VIPR技术结合，以提高特定种类磁共振扫描的速度，在某种情况下可以达到原来的几千倍。（我是这所大学的教员，但是没有参与这项研究。）GE医疗集团还在实验一种新的方法，有希望利用压缩感知技术大大改善对癌症病人代谢动力学的观测。同时，帕卡德医院应用了压缩感知技术，使磁共振成像仪的图像记录速度提升为传统扫描仪的三倍。
这对于两岁的布赖斯来说恰好够用。瓦萨纳瓦拉在控制室发出工作信号，麻醉师给男孩注射了一点镇静剂，然后关掉了呼吸机。男孩的呼吸立刻停止了。瓦萨纳瓦拉开始扫描，而麻醉师监视着布赖斯的心率和血氧水平。40秒钟之后，扫描结束，布赖斯没有出现明显的缺氧情况。当天晚些时候，压缩感知算法从粗略的扫描中生成了清晰的图像，能让瓦萨纳瓦拉看清双侧胆管的堵塞情况。一名介入放射科医生将一根弯曲的导线依次插入双侧胆管中，轻轻清除淤塞，并为男孩安装了让胆汁恰当流出的细小导管。正是数学与医学的结合，才使得布赖斯的检测结果又恢复了正常。
原文作者：
JordanEllenberg(ellenber@math.wisc.edu),是威斯康辛大学的数学副教授。原文发表在《连线》杂志三月号上。数学怎样得出那些颗粒：压缩感知技术是一种从低分辨率样本中重建高精度数据的数学工具。它可以用来重现古老的音乐录音、寻找敌人的无线电信号，并更加迅速地完成磁共振成像。这里展示的是它如何处理照片。