压缩感知从字面上看起来，好像是数据压缩的意思，而实则出于完全不同的考虑。经典的数据压缩技术，无论是音频压缩（例如 mp3），图像压缩（例如 jpeg），视频压缩（mpeg），还是一般的编码压缩（zip），都是从数据本身的特性出发，寻找并剔除数据中隐含的冗余度，从而达到压缩的目的。这样的压缩有两个特点：第一、它是发生在数据已经被完整采集到之后；第二、它本身需要复杂的算法来完成。相较而言，解码过程反而一般来说在计算上比较简单，以音频压缩为例，压制一个 mp3 文件的计算量远大于播放（即解压缩）一个 mp3 文件的计算量。
稍加思量就会发现，这种压缩和解压缩的不对称性正好同人们的需求是相反的。在大多数情况下，采集并处理数据的设备，往往是廉价、省电、计算能力较低的便携设备，例如傻瓜相机、或者录音笔、或者遥控监视器等等。而负责处理（即解压缩）信息的过程却反而往往在大型计算机上进行，它有更高的计算能力，也常常没有便携和省电的要求。也就是说，我们是在用廉价节能的设备来处理复杂的计算任务，而用大型高效的设备处理相对简单的计算任务。这一矛盾在某些情况下甚至会更为尖锐，例如在野外作业或者军事作业的场合，采集数据的设备往往曝露在自然环境之中，随时可能失去能源供给或者甚至部分丧失性能，在这种情况下，传统的数据采集-压缩-传输-解压缩的模式就基本上失效了。
压缩感知的概念就是为了解决这样的矛盾而产生的。既然采集数据之后反正要压缩掉其中的冗余度，而这个压缩过程又相对来说比较困难，那么我们为什么不直接「采集」压缩后的数据？这样采集的任务要轻得多，而且还省去了压缩的麻烦。这就是所谓的「压缩感知」，也就是说，直接感知压缩了的信息。
可是这看起来是不可能的事情。因为压缩后的数据并不是压缩前的数据的一个子集，并不是说，本来有照相机的感光器上有一千万个像素，扔掉其中八百万个，剩下的两百万个采集到的就是压缩后的图像，──这样只能采集到不完整的一小块图像，有些信息被永远的丢失了而且不可能被恢复。如果要想采集很少一部分数据并且指望从这些少量数据中「解压缩」出大量信息，就需要保证：第一：这些少量的采集到的数据包含了原信号的全局信息，第二：存在一种算法能够从这些少量的数据中还原出原先的信息来。
有趣的是，在某些特定的场合，上述第一件事情是自动得到满足的。最典型的例子就是医学图像成像，例如断层扫描（CT）技术和核磁共振（MRI）技术。对这两种技术稍有了解的人都知道，这两种成像技术中，仪器所采集到的都不是直接的图像像素，而是图像经历过全局傅立叶变换后的数据。也就是说，每一个单独的数据都在某种程度上包含了全图像的信息。在这种情况下，去掉一部分采集到的数据并不会导致一部分图像信息永久的丢失（它们仍旧被包含在其它数据里）。这正是我们想要的情况。
上述第二件事就要归功于陶哲轩和坎戴的工作了。他们的工作指出，如果假定信号（无论是图像还是声音还是其他别的种类的信号）满足某种特定的「稀疏性」，那么从这些少量的测量数据中，确实有可能还原出原始的较大的信号来，其中所需要的计算部分是一个复杂的迭代优化过程，即所谓的「L1-最小化」算法。
把上述两件事情放在一起，我们就能看到这种模式的优点所在。它意味着：我们可以在采集数据的时候只简单采集一部分数据（「压缩感知」），然后把复杂的部分交给数据还原的这一端来做，正好匹配了我们期望的格局。在医学图像领域里，这个方案特别有好处，因为采集数据的过程往往是对病人带来很大麻烦甚至身体伤害的过程。以 X 光断层扫描为例，众所周知 X 光辐射会对病人造成身体损害，而「压缩感知」就意味着我们可以用比经典方法少得多的辐射剂量来进行数据采集，这在医学上的意义是不言而喻的。
这一思路可以扩展到很多领域。在大量的实际问题中，我们倾向于尽量少地采集数据，或者由于客观条件所限不得不采集不完整的数据。如果这些数据和我们所希望重建的信息之间有某种全局性的变换关系，并且我们预先知道那些信息满足某种稀疏性条件，就总可以试着用类似的方式从比较少的数据中还原出比较多的信号来。到今天为止，这样的研究已经拓展地非常广泛了。
但是同样需要说明的是，这样的做法在不同的应用领域里并不总能满足上面所描述的两个条件。有的时候，第一个条件（也就是说测量到的数据包含信号的全局信息）无法得到满足，例如最传统的摄影问题，每个感光元件所感知到的都只是一小块图像而不是什么全局信息，这是由照相机的物理性质决定的。为了解决这个问题，美国 Rice 大学的一部分科学家正在试图开发一种新的摄影装置（被称为「单像素照相机」），争取用尽量少的感光元件实现尽量高分辨率的摄影。有的时候，第二个条件（也就是说有数学方法保证能够从不完整的数据中还原出信号）无法得到满足。这种时候，实践就走在了理论前面。人们已经可以在算法上事先很多数据重建的过程，但是相应的理论分析却成为了留在数学家面前的课题。
但是无论如何，压缩感知所代表的基本思路：从尽量少的数据中提取尽量多的信息，毫无疑问是一种有着极大理论和应用前景的想法。它是传统信息论的一个延伸，但是又超越了传统的压缩理论，成为了一门崭新的子分支。它从诞生之日起到现在不过五年时间，其影响却已经席卷了大半个应用科学。
译者：Armeny 原文 校对：拟南芥、剃刀、木遥
扩展阅读：数字图像的压缩与恢复/奥卡姆剃刀
2009年早春，斯坦福大学露西尔·帕卡德儿童医院的一组医生把一名两岁男孩送进磁共振成像[f1] 扫描仪。这个将被我称为布赖斯的男孩身处巨洞般的金属仪器中，看上去是那么弱小无助。他被施以全身麻醉，一根弯弯曲曲的管子从他的咽喉联接到扫描仪傍的呼吸机上。十个月前， 布赖斯接受了肝脏移植术，来自捐献者的部分肝脏取代了他自己的已坏死的肝脏。他的康复情况一度不错。但是，最近的实验室测试结果令人担忧，他的身体出现了问题——可能一条或者全部的两条胆管被堵住了。
帕卡德医院的儿童放射科医生施里亚斯（校对者注：这个first name有多种翻译方法，请编辑注意）·瓦萨纳瓦拉需要高精度的扫描结果来告诉他问题出在哪，但是这将意味着他的小病人在扫描过程中不得不保持绝对静止。哪怕布赖斯只是呼吸了一次，成像结果都会变得模糊。要避免上述情况，就需要进行足够深的麻醉让病人停止呼吸。进行一次标准的磁共振成像检测需要两分钟时间，但如果麻醉师真的让布赖斯在这么长时间里停止呼吸，那么带来的问题将远远超过他肝脏的小毛病。
不过，瓦萨纳瓦拉和他的电子工程师同事迈克尔·勒斯蒂格打算使用一种快得多的新扫描方法，名曰“压缩感知”。这种技术可能是当今应用数学界最热门的话题了。未来，它可能会改变我们寻找遥远星系的方式。而现在，这种技术使得瓦萨纳瓦拉和勒斯蒂格只需要40秒就可以采集到精确重建布赖斯肝脏图像所需的数据。
压缩感知的发现纯属偶然。2004年2月，伊曼纽尔·坎迪斯正在自己的电脑上看着Shepp-Logan图像（译注：这是医学图像处理领域用来进行仿真测试的标准模拟图像，由一些大大小小的椭圆模拟生物器官）打发时间。这幅通常被计算机科学家和工程师用于测试成像算法的标准图像，看起来就像《第三类接触》里那个搞笑地将眉毛扬起的外星人。坎迪斯，斯坦福大学教授，曾在加州理工学院工作过，打算用一个严重失真的模型图像作为磁共振成像仪不能精确扫描而产生的非清晰图像来进行实验。他想到一种名为L1（校对注：这里虽然原文用的是小写，但是在中文上下文中用小写则极易同11混淆，而数学上这里大小写都可以用）范数极小化的数学技术可能有助于清除小部分斑痕。他按下一个键，算法运行起来了。
坎迪斯希望屏幕上的模型图像变得稍微清晰一些。但是，他突然发现用残缺的数据渲染出来的图像是那么细腻完美，对每个细节而言都是如此，这简直就像变魔术一样。太不可思议了，他认为。“这就好像，你给了我十位银行账号的前三位，然后我能够猜出接下来的七位数字。”他说。他尝试在不同类型的模型图像上重新进行这个实验，结果都非常好。
在博士后贾斯廷·龙伯格的帮助下，坎迪斯提出了一个粗略的理论。之后，他在黑板上向加州大学洛杉矶分校的同事陶哲轩介绍了自己的理论。坎迪斯在结束讨论离开的时候觉得陶哲轩对此持怀疑态度，毕竟，图像清晰度的提高也太离谱了。然而，第二天晚上，陶哲轩给坎迪斯送去关于他们之前讨论的问题的一叠笔记。这叠笔记为他们共同发表的第一篇论文奠定了基础。在随后的两年中，他们写了更多文章。
上面介绍的是压缩感知技术的开端，这个数学界的全新领域改变了人们处理大规模数据集的方式。仅仅六年时光，它为上千篇论文提供了灵感，吸引了数百万美元的联邦基金。2006年，坎迪斯在这一领域内的工作为他赢得了奖金值50万美元的沃特曼奖，这是美国国家科学基金授予研究者的最高荣誉。其原因是显而易见的。想象一下，磁共振成像仪可以在几秒钟的时间里生成原本需要花费一个小时才能生成的图像；军用软件截获敌方通信的能力得到极大加强；传感器能够解析遥远星际的无线电波。突然之间，数据的采集、操作以及解析都变得容易了。
压缩感知的原理是这样的：你有一张图片，假设是总统的肾脏图片，这不是关键。图片由一百万个像素构成。对传统成像来说，你不得不进行一百万次量度。而采用压缩感知技术，你只需要量度一小部分，好比说从图像的不同部分随机抽取十万个像素。从这里开始，有大量的实际上是无穷多的方式填充那剩余的九十万个像素点。
寻找那个唯一正确的表示方式的关键在于一种叫稀疏度的概念。所谓稀疏度，是描述图像的复杂性或者其中所缺的一种数学方法。一幅由少数几个简单、可理解的元素（例如色块或者波浪线构成的图片）是稀疏的；满屏随机、散乱的点阵则不是稀疏的。原来在无限多的可能性中，最简单、最稀疏的那幅图像往往就是正解，至少很接近正解。
但是，怎样进行数字运算，才能快速获得最稀疏的图像呢？分析所有可能的情况太费时间。然而，坎迪斯和陶哲轩知道最稀疏的图像是用最少的成分构成的，并且，他们可以用L1范数极小化技术迅速找到它。
这样，在输入不完整的图像后，算法开始试着用大色块来填充空白区。如果有一团绿色的像素点聚集在一起，算法可能会用一个大的绿色矩形填充它们之间的空间;而如果是一团黄色的像素点，那么就用黄色的矩形来填充。在不同颜色交错散布的区域，算法会使用越来越小的矩形或其他形状填充各种颜色之间的空间。算法会重复这样的过程，最终，得到一幅由最少的可能的色块构成的图像，它的一百万像素都已被彩色填满。
并不能绝对保证这样的图像就是最稀疏的，或者正是你所试图重建的那个。但是坎迪斯和陶哲轩已经从数学上证明了，它的错误率是无穷小的。算法运行可能还是需要几个小时，但是，让电脑多跑一个小时，总好过让孩子在额外的一分钟里停止呼吸。
压缩感知已经产生了令人惊叹的科学影响。这是因为每一个有趣的信号都是稀疏的，只要你能够正确定义它的稀疏性。例如，钢琴和弦的乐音是一小组不超过五个纯音符的组合。在所演奏的音频中，只有少部分频率包含有效的音乐信息，而其余大部分频段是一片无声地带。因此，你可以用压缩感知技术从“欠采样”的老旧唱片中重建出当时的乐章，而不用担心失去了由特定频率构成的声波的信息。只需要你手头的材料，就可以用L1范数极小化法以稀疏方式填补空白，从而获得与原音一般无二的旋律。
带着建筑师式的眼睛，顶着略显蓬松的头发，坎迪斯散发着时尚极客的气息。这个39岁的法国人语气温和，但是面对他认为不达标的事情绝不妥协。“不，不，他说的没有道理。”当我提到压缩感知领域某个和他有些观点有着细小差别的专家的工作时，他如是说，“不，不，不，不。那没有道理，没道理，是错的。”
坎迪斯曾经预见，将来会有大量应用技术是以他的研究成果作为理论基础的。他举例说道，在未来，这项技术不会仅仅用在磁共振成像仪上。例如，数码相机收集了大量信息，然后压缩图像。但是，至少在压缩感知技术可用的情况下，压缩是一种极大的浪费。如果你的相机记录了大量的数据，却在压缩时丢弃了其中的90%，那么为什么不在一开始就只记录10%的数据从而节省电池电量和内存？对于您的孩子的数码快照，费电可能没什么大不了，你只要插上电源为相机充电就可以了。“但是，当废电池多到可以环绕木星，”坎迪斯说，“结果就不是那么简单了”。同样，如果你希望自己的相机能够拍摄万亿像素的照片而不是几百万像素，你就必须使用压缩感知技术。
从信息的小样本中收集有用数据的能力也引起了军方的重视：比如，敌方通信可能从一个频率跳到另一个频率。但是，还没有一种硬件设备能以足够快的速度扫描整个频域。但是无论在什么情况下，对手的信号都是稀疏的，是由频段内极少数的某种简单信号构成的，出现在一些相对较小却未知的频段。这意味着压缩感知可以用来从“噼啵”声中区分来自任意波段的敌人的交谈。所以不出意外的，美国国防部先进计划研究署正在支持压缩感知技术的研究。
压缩感知不仅可以用于解决现在的技术难题。将来，它还将帮助我们处理已存储的大量信息。每天，全世界都要产生数不清的数据，我们希望这些数据安全、有效、可恢复地保存起来。目前，我们大部分的视听信息都是用复杂的压缩格式存储起来的。如果有一天，这种格式被淘汰了，你不得不进行痛苦的格式转换。但是坎迪斯相信，在拥有压缩感知技术的未来，对于采用高成本红外技术拍摄的天文图像，只需要拍摄到20％的像素就可以了。因为我们一开始就只记录了极少部分的数据，所以不需要再进行压缩。那么我们只需要逐步改进数据的解析算法，而不是数据的压缩算法，就可以精确地恢复出原始图像了。
上面说的都是将来的事情。今天，压缩感知技术已经改写了我们获取医学信息的方式。在GE医疗集团的参与下，威斯康辛大学的一个研究小组正在把压缩感知技术与HYPR和VIPR技术结合，以提高特定种类磁共振扫描的速度，在某种情况下可以达到原来的几千倍。（我是这所大学的教员，但是没有参与这项研究。）GE医疗集团还在实验一种新的方法，有希望利用压缩感知技术大大改善对癌症病人代谢动力学的观测。同时，帕卡德医院应用了压缩感知技术，使磁共振成像仪的图像记录速度提升为传统扫描仪的三倍。
这对于两岁的布赖斯来说恰好够用。瓦萨纳瓦拉在控制室发出工作信号，麻醉师给男孩注射了一点镇静剂，然后关掉了呼吸机。男孩的呼吸立刻停止了。瓦萨纳瓦拉开始扫描，而麻醉师监视着布赖斯的心率和血氧水平。40秒钟之后，扫描结束，布赖斯没有出现明显的缺氧情况。当天晚些时候，压缩感知算法从粗略的扫描中生成了清晰的图像，能让瓦萨纳瓦拉看清双侧胆管的堵塞情况。一名介入放射科医生将一根弯曲的导线依次插入双侧胆管中，轻轻清除淤塞，并为男孩安装了让胆汁恰当流出的细小导管。正是数学与医学的结合，才使得布赖斯的检测结果又恢复了正常。
原文作者：
Jordan Ellenberg (ellenber@math.wisc.edu), 是威斯康辛大学的数学副教授。原文发表在《连线》杂志三月号上。
数学怎样得出那些颗粒：压缩感知技术是一种从低分辨率样本中重建高精度数据的数学工具。它可以用来重现古老的音乐录音、寻找敌人的无线电信号，并更加迅速地完成磁共振成像。这里展示的是它如何处理照片。
[f1]坚持用‘磁共振’的原因：1）MRI直译就是磁共振成像；2）现代人谈‘核’色变，而传统‘核磁共振’中的‘核’其实指的是原子核。因为‘核磁共振’这个名字让我们在招募fMRI实验被试时困难重重……赶明儿打算写个磁共振成像原理给大家做科普，希望以后招被试容易些……