压缩感知 许志强 中国科学院数学与系统科学研究院, 计算数学与科学工程计算研究所, 科学与工程计算国家重点实验室, 100190, 北京 2012 年 1 月 12 日 摘要 压缩感知是近来国际上热门的研究方向. 其在信号处理中具有很好的应用前景. 此外, 它与逼近论、最优化、随机矩阵及离散几何等领域密切相关, 由此产生了一些漂 亮的数学结果. 本文综述压缩感知一些基本结果并介绍最新进展. 主要包括 RIP 矩阵 编码与 1解码的性能, RIP 矩阵的构造, Gelfand 宽度, 个例最优性及 OMP 解码等. 1引言 现实世界中, 人们经常需要对信号进行观测, 例如医学图像成像、CT 断层扫描等, 以 期通过观测信息对原始的信号进行重建. 由于计算机的离散化存储, 我们可将需重建的信 号 x 抽象为一 N 维向量, 可将对信号 x 的观测抽象为用一 n N 的矩阵 与信号 x 进行 乘积. 例如在 CT 扫描中, 矩阵 通常选择为离散 Fourier 矩阵. 那么, 我们所观测的信息 为 y = x.(1) 人们自然而问: 为重建信号 x, 至少需要多少次观测? 由线性代数知识可知, 为使方程组 (1) 的解存在且唯一, 我们须选择 n N. 也就是说, 我们需要至少进行 n = N 次观测. 然 而, 现实世界中的自然信号通常具有一定规律性. 对这种规律性, 一种常用的刻画方式是自 然信号在一组基底表示下是稀疏的. 这里的“稀疏”是指它们用一组基底展开后, 大多数 系数为 0, 或者绝对值较小. 例如, 自然图像用小波基底展开后, 一般而言, 其展开系数大多 国家自然科学基金 (11171336) 及创新群体 (11021101) 资助. Email: xuzq 1 2稀疏信号的恢复2 数绝对值较小. 这也就是图像能够进行压缩的原理. 然而, 这同时为人们减少观测次数 n 从理论上提供了可能性. 因而, 压缩感知的主要任务为: 对尽量小的 n, 设计 n N 观测矩 阵 , 以及通过 x 快速恢复 x 的算法. 所以, 压缩感知的研究主要分为两方面：矩阵 的设计; 与反求信号 x 的算法. 本文主要介绍压缩感知的一些基本结果. 在每节里, 我们采用注记的方式介绍当前的 一些研究进展及研究问题, 同时提供与之相关的参考文献, 以使感兴趣的读者可进一步探 索. 本文组织结构如下: 第 2 节中我们介绍了稀疏信号精确恢复的编码、解码方法. 特别 是, 我们将介绍矩阵的零空间性质, 及 RIP 矩阵编码与 1解码的性能. 我们在第 3 节中介 绍 RIP 矩阵的构造方法, 包括随机矩阵、结构随机矩阵及确定性矩阵. 在第 4 节中, 为理 解最优编码、解码对的性能, 我们介绍了 Gelfand 宽度与编码、解码对性能的关联. 我们 在第 5 节中介绍了编码、解码对在不同范数意义下的个例最优性. 最后一节简要介绍实现 解码的算法. 2稀疏信号的恢复 为方便介绍压缩感知理论, 我们将信号的稀疏性简单理解为信号中非 0 元素数目较少. 我们所指的信号即为一向量 x RN. 我们用 s表示 s-稀疏向量集合, 即 s:= x RN: x0 s, 这里 x0表示 x 中的非 0 元素数目. 所谓对信号 x0 RN编码, 即指用一 n N 的矩阵 与 x0 RN进行乘积, 那么我们得到 y = x0. 此处, y Rn即为我们所观测到的关于 x0的信息. 所谓解码, 就是试图通过 y 反求 x0, 也 就是寻找一从 Rn到 RN的映射, 我们将该映射记为 . 我们用 (y) 表示反求结果. 一般 而言, 若 n N, 则有无数个 x RN满足 y = x. 因而, 只有借助信号稀疏性的特征, 我 们才有可能反求原始的信号 x0. 那么, 给定一编码、解码对 (,), 我们关心其性能, 即: x0 (x0)X, 此处 X 为一给定范数. 本文中, 我们通常选择 X 为 p范数, 并用下标 p 表示 p范数. 当 x0中非 0 元素数目较小的时候, 一种较为自然的解码 0(y) 是如下规划问题的解: P0:min xRN x0 s.t.x = y. 2稀疏信号的恢复3 这里, x0表示 x 中非 0 元素的数目. 我们用符号 0(y) 表示 P0的解. 也就是说, 0(y) 为在所有满足线性方程组 x = y 的向量中, 选择非 0 元素数目最少的. 如果我们对矩阵 加些许限制, 由 P0定义的解码, 可精确恢复 s-稀疏向量: 定理 2.1 假定 RnN是一个任 2s 列均线性无关的矩阵. 我们选择解码为 0, 那 么, 对任意的 x0 s, 0(x0) = x0. 根据定理 2.1, 如果我们选取观测次数 n = 2s, 那么就存在一编码、解码对 (,) 使得对 任意的 x0 s, 均有 (x0) = x0. 这意味着: 如果我们希望恢复一个嵌入在 N 维空间的 s-稀疏向量, 那么 2s 次观测次数就足够了. 但是, 问题 P0的求解是十分不平凡的. 事实上, P0是一个 NP 完全问题 14, 31. 那么, 我们能否找到一个更为有效的解码算法? 一个令人惊讶的事实是, 如果矩阵 满足一定条 件, 那么回答则是肯定的, 但我们要在观测次数上付出些许代价. 我们现在将解码 1(y) 定 义为如下问题的解: P1:min xRN x1 s.t.x = y. 如所知, P1可转化为如下的线性规划问题： P2:min tRN t1+ t2+ + tN s.t.x = y tj xj tj, j = 1,.,N tj 0, j = 1,.,N. 从一个简单的论证可看出, P1的解与 P2的解相同. 因此, 可找到有效的算法对 P1求解. 但 是, 一个自然的问题是: P1的解与 P0的解等价吗? 或者是, 对什么样的观测矩阵 , P1的解与 P0的解总一致? 为回答这一问题, 我们首先介绍矩阵的零空间性质. 零空间性质思想的主要出发点是： 解码通常是从集合 x RN: x = y. 中按一定规则挑选我们需要的元素. 由线性代数知识可知, 解集 x RN: x = y 可由 原始的信号 x0, 与矩阵的 的零空间 Ker := x RN: x = 0 2稀疏信号的恢复4 所确定. 因此, 人们考虑通过刻画矩阵 的零空间, 从而给出 P1解与 P0解一致的充 要条件. 我们首先介绍零空间性质的定义. 为描述方便, 我们介绍如下符号: 对于指标集 T 1,.,N 及向量 v RN, 我们将 v 中指标在 T 中的元素取出, 形成一个新的向量, 标记为 vT R#T. 我们用 Tc表示 T 的补集. 类似的, 我们可定义矩阵 T. 定义 2.1 我们称矩阵 满足 s-阶零空间性质, 如果对任意的 v Ker , 均有 vT1 vTc1,对任意的 T 1,.,N, #T = s. 直观上, 我们将零空间性质理解为 Ker 的非 0 元素较为均匀的分布, 不会明显的集中于 某 s 个元素上. 采用零空间性质, 我们有 定理 2.2 我们选择解码为 1. 那么, 对任意的 x s, 1(x) = x 如果和仅仅如果 满足 s-阶零空间性质. 注 2.1 用类似于零空间性质的方式, 描述 1解码可恢复 s-稀疏信号, 在人们研究 L1最佳逼近时就已经出现 (参考 33). 与定理 2.2 一致的形式首先出现在 23. 此外, 文 18, 19 也隐含了类似的结果. 虽然可以用零空间性质给出 P1的解与 P0的解一致的充要条件. 但是, 零空间性质并 不容易操作, 无论在理论还是计算方面. 也就是说, 给一个矩阵 , 难以从理论上证明其是 否满足零空间性质, 也不容易在计算机上快速验证. 因而, 人们考虑了另外一种刻画方式, 即是所谓的矩阵 RIP 性质 (Restricted Isometry Property). 我们首先介绍 RIP 性质的定义 9. 我们说矩阵 满足 s-阶 RIP 性质, 如果存在常数 s 0,1) 使得 (1 s)x2 x2 (1 + s)x2(2) 对任意的 x s成立. 实际上, (2) 等价于 Grammian 矩阵 TT 所有特征值位于区间 1 s,1 + s, 这里 #T s. 我们称 s为 RIP 常数. 我们首先看一下如何从直观上理解 RIP 矩阵. 倘若 s= 0 , 那么矩阵 为一标准正交 矩阵. 因而也是一方阵. 然而在压缩感知中, 我们希望矩阵 是“扁” 的, 也就是 n N, 同 时保留类似于正交矩阵的特征. 因而, RIP 矩阵的定义 (2), 事实上刻画了矩阵 中任取 s 列所形成的 ns 矩阵接近于正交矩阵的程度. RIP 常数 s越接近于 0, 其任取 s 列所形成 的子矩阵也就越接近于正交. 从某种意义上来说, 性质也就越好. 下面定理给出了解码 1能够精确恢复 s-稀疏信号的一个充分条件. 2稀疏信号的恢复5 定理 2.3 (6, 7) 假定编码矩阵 满足 2s 阶 RIP 性质, 且 RIP 常数 2s 2 1. 我们选择解码 1. 那么, 对任意的 x s, 均有 1(x) = x. 上述定理表明, 我们可用 RIP 矩阵编码、1解码精确恢复 s-稀疏信号. 然而, 现实世 界中的信号并非严格稀疏的, 通常仅仅是近似稀疏. 对于此类信号, 如果我们仍然用 RIP 矩阵 进行编码, 选则解码为 1, 那么我们能较好的恢复非稀疏信号吗? 令人惊讶的是, 我们仍然能较好的完成任务. 为介绍这方面的结果, 我们首先介绍最佳 s-项逼近误差的概 念. 给定范数 X, 那么信号 x RN的在范数 X意义下最佳 s-项逼近误差为 s(x)X:= min zs x zX. 对于 K RN, 我们令 s(K)X:= max xK s(x)X. 下面定理指出, 对于一般信号, 我们采用 RIP 矩阵编码与用 1作解码, 那么恢复效果可用 1范数意义下的最佳逼近误差刻画. 定理 2.4 假定编码矩阵 满足 2s 阶 RIP 性质, 且 RIP 常数 2s 21 . 我们选择 解码为 1. 那么对任意的 x RN, 我们有 1(x) x2 C0 s(x)1 s, 此处 C0为一常数. 注 2.2 定理 2.3 与定理 2.4 首先在7 中被证明. 但给出的 RIP 常数较为粗糙. 在 6 中, E. Cand es 将RIP 常数改进为 2s 21. 仍有一些论文考虑改进定理 2.3 中的 RIP 常数 2 1 4, 21. 特别是，Mo 和 Li 将该常数改进为 2s 0.4931 30. 此外, Davies 和 Gribonval 建构一个例子表明, 如果 2s 1 2, 那么 1解码不能恢复一些 s-稀疏信号. 注意到这些研究均是针对 2s, 也就是要求矩阵满足 2s 阶 RIP 条件. 在 5 中, Cai, Wang 和 Xu 考虑了矩阵满足 s-阶 RIP 条件的情况, 给出了 P1能恢复 s-稀疏信号的充分条件为 s 0.307. 此外, 我们特别指出, 借助离散几何中的多面体理论, 在文 16 中, Donoho 给 出了 1解码能精确恢复 s-稀