压缩传感讲座

理查德·巴拉纽克

莱斯大学

刊登在 IEEE 信号处理杂志上，2007 年 7 月

范围

Shannon/Nyquist 采样定理告诉我们，为了在均匀采样信号时不丢失信息，我们必须以至少比其带宽快两倍的速度进行采样。在许多应用中，包括数码图像和摄像机，奈奎斯特速率可能非常高，以至于我们最终会得到太多的样本，必须压缩才能存储或传输它们。在其他应用中，包括成像系统（医疗扫描仪、雷达）和高速模数转换器，将采样率或密度提高到超出当前最先进的水平是非常昂贵的。

在本次讲座中，我们将学习一种使用压缩传感来解决这些问题的新技术 [1， 2]。我们将用更通用的线性测量方案取代传统的采样和重建操作，并结合优化，以便以明显低于奈奎斯特的速率获取某些类型的信号。

关联

这里提出的想法可用于说明从本科或研究生数字信号处理到统计学和应用数学的各种课程中的数据采集、线性代数、基扩展、逆问题、压缩、降维和优化之间的联系。

先决条件

理解和教授本材料所需的先决条件是线性代数、基本优化和基本概率。

问题陈述

奈奎斯特速率采样完全通过利用信号的频带性来描述信号。我们的目标是通过利用信号的可压缩性来减少完全描述信号所需的测量次数。转折点在于，我们的测量不是点样本，而是信号的更一般的线性泛函。

考虑一个实值、有限长度、一维、离散时间信号 x，我们将其视为 R^N 中 N × 1 列向量，元素为 x[n]，n = 12,...，N.我们通过将图像或更高维数据矢量化为长一维向量来处理图像或更高维数据。

RN 中的任何信号都可以用 N ×1 向量的基础来表示

 x

其中 s 是加权系数 s= hxψi = ψ^Tx 的 N × 1 列向量，其中 ·^T 表示 （Hermitian） 转调操作。显然，x 和 s 是同一信号的等效表示，其中 x 在时域中，s 在 Ψ 域中。

我们将重点介绍具有稀疏表示的信号，其中 x 是仅 K 个基向量的线性组合，其中

变换编码在数码相机等数据采集系统中起着核心作用，因为这些系统的样本数量很多，但信号是可压缩的。在这个框架中，我们获取完整的 N 样本信号 x;通过 s = Ψ^T x 计算完整的变换系数集 {s};找到 K 个最大的系数并丢弃 （N − K） 个最小的系数;并对 K 进行编码最大系数的值和位置。（在实践中，我们还将值和位置转换为数字位。

不幸的是，先采样后压缩框架存在三个固有的低效率问题：首先，我们必须从可能大量的样本 N 开始， 即使最终期望的 K 很小。其次，编码器必须计算所有 N 个变换系数 {s}，即使它会丢弃除 K 个之外的所有 变换系数。第三，编码器面临对大系数的位置进行编码的开销。

作为替代方案，我们将研究一种更通用的数据采集方法，该方法将信号直接压缩为压缩表示，而无需经历获取 N 个样本的中间阶段。考虑更通用的线性测量过程，该过程计算 x 之间的 M < N 内积和向量集合

测量 y放入 M ×1 向量 y 和测量向量 φTas 行放入 M ×N （a）

图 1：（a） 使用（随机高斯）测量矩阵 Φ 和离散余弦变换 （DCT） 矩阵 Ψ 的压缩传感测量过程。系数向量 s 是稀疏的，K =4。（b） 根据矩阵乘积 Θ = ΦΨ 的测量过程，突出显示对应于非零 s 的四列。测量向量 y 是这四列的线性组合。

矩阵 Φ 并代入 （1），我们可以写成

 
y = Φx= ΦΨs = Θs（2）

其中 Θ ：= ΦΨ 是 M × N 矩阵。参见图 1（a） 的图片描述 （2）。请注意，测量过程是非自适应的;也就是说，Φ 不以任何方式依赖于信号 x.

我们下面的目标是为 K 稀疏和可压缩信号设计一个测量矩阵 Φ 和一个重建算法，这些信号只需要 M ≈ K 或稍多的测量，或者大约与传统转换编码器中编码的系数数量一样多的测量。我们的方法基于最近在 [1,2] 中引入的压缩感应理论。

溶液

该解决方案包括两个步骤。第一步，我们设计了一个稳定的测量矩阵 Φ，以确保任何 K 稀疏或可压缩信号中的显著信息不会因从 x ∈ R^N 到 y ∈ R^M 的降维而受到损害。在第二步中，我们开发了一种重建算法，从测量值 y 中恢复 x。最初，我们专注于 K-稀疏信号。

稳定的测量矩阵

首先，我们设计了数据采集系统的测量侧，它基于矩阵 Φ。我们的目标是进行 M 次测量（向量 y），从中我们可以稳定地重建长度 N 信号 x，或者等效地在基 Ψ 中重建其稀疏系数向量 s。显然，如果测量过程损坏了 x 中的信息，则无法进行重建。不幸的是，一般情况是这样的：由于测量过程是线性的，并且根据矩阵 Φ 和 Ψ 定义，因此求解 （2） 中给定的 y 的 s 只是一个线性代数问题，而对于 M < N，方程数少于未知数，因此解通常是病态的。

然而，s 的 K 稀疏性拯救了我们。在这种情况下，测量矢量 y 只是 Θ 的 K 列的线性组合，其对应的 s6= 0（参见图 1（b））。因此，如果我们先验地知道 s 的哪些 K 个条目 是非零的，那么我们可以形成一个线性方程的 M × K 系统来求解这些非零条目，其中现在方程 M 的数量等于或超过未知数 K 的数量。确保这个 M × K 系统是有条件的——因此具有稳定的逆——的一个必要和充分的条件是，对于任何向量 v 与我们有的 s 共享相同的 K 非零条目

对于某些人来说

当然，在实践中，我们不会知道 k 个非零条目在 s 中的位置。有趣的是，可以证明 K 稀疏和可压缩信号的稳定逆的充分条件是 Θ 满足任意 3K 稀疏向量 v 的 （3）。 这就是所谓的受限等轴测特性 （RIP） [1]。

另一种稳定性的方法是确保测量矩阵 Φ 与稀疏基 Ψ 不一致，因为向量 {φ} 不能稀疏地表示向量 {ψ}，反之亦然 [1,2,4]。经典示例的特点是 delta 尖峰和傅里叶正弦曲线扮演 {φ} 和 {ψ} 的角色;傅里叶不确定性原理立即产生了不相干性。

那么，给定一个稀疏基 Ψ，我们如何构造一个测量矩阵 Φ，使得 Θ = ΦΨ 具有 RIP？不幸的是，仅仅验证给定的 Θ 是否具有 RIP 在组合上是复杂的;我们必须验证 （3） 对于每个

在压缩感应中，我们通过选择 Φ 作为随机矩阵来回避这个问题。例如，我们将 _j，i φ矩阵元素绘制为来自零均值、1/N 方差高斯密度（白噪声）的独立且同分布 （iid） 的随机变量 [1,2,5]。然后，测量值 y 只是 x 元素的 M 个不同的随机加权线性组合 （回想一下图 1（a） 并注意 Φ 的随机结构）。

高斯 Φ 有两个有趣且有用的属性。首先，Φ 与 delta 尖峰的基 Ψ = I 不相干，概率很高，因为需要整整 N 个尖峰来表示 Φ 的每一行。更严格地说，使用测度参数的集中度，如果 M ≥ cK log（N/K），其中 c 是一个小常数 [1,2,5]，则 M × N iid 高斯矩阵 Θ = ΦI = Φ 可以证明具有很高的 RIP。因此，我们可以期望从仅

其次，由于生成 Φ 的 iid 高斯分布的特性，无论选择（正交）稀疏基矩阵 Ψ，矩阵 Θ = ΦΨ 也是 iid 高斯矩阵。因此，随机高斯测量值 Φ 是通用的，因为 Θ = ΦΨ 对每个可能的 Ψ 都具有很高概率的 RIP.

在许多其他矩阵中，具有随机 ±1 条目的 Rademacher 矩阵也可以证明具有 RIP 和普遍性属性 [5]。

信号重建算法

RIP 提供了理论保证，即 K 稀疏或可压缩信号可以用 y 中的 M 测量值来完全描述，但它并没有告诉我们如何恢复它。信号重建步骤必须采用测量 y、随机测量矩阵 Φ （或生成它的随机种子）和稀疏基 Ψ 并重新生成长度 N 信号 x，或等效地生成其稀疏系数向量 s。我们最初再次关注 K-稀疏信号。

由于 M < N 在 （2） 中，有无限多的 s⁰ 满足 Θs⁰ = y;它们都位于 （N −M） 维超平面 H ：= N（Θ） + s 在 R^N 中对应于零空间 N（Θ） 转换为 True 稀疏解 s。这是因为如果 Θs= y，则零空间中任何向量 r 的 Θ（s + r） = y。因此，我们的目标是在转换后的零空间中找到信号的稀疏系数向量 s。

将向量 s 的 'p 范数定义为

“norm” 计算 s 中非零条目的数量;因此 K 稀疏向量具有 '0 范数 K.

最小 '₂ 范数重建：解决此类逆问题的经典方法是最小二乘法;也就是说，我们在平移的零空间H 中选择具有最小 '₂ 范数（能量）的向量：

 0 0

s = argminksk2 使得 Θs= y（4） _b

甚至还有一个方便的闭式解 s = Θ^T （ΘΘ^T ）⁻¹y。但不幸的是，当b

我们寻找的向量 s 是 K 稀疏的，'₂ 最小化几乎永远找不到它。相反，我们得到的是一个具有大量振铃的非稀疏s（更多内容见下文 6.1 节）。 乙

最小 '0 范数重建：由于 （4） 中的 '2 范数不反映信号稀疏性，因此逻辑替代方案是在平移的零空间 H 中搜索最稀疏的向量:

 0 0

 
s = argminksk0 使得 Θs= y（5）

_b

可以证明，仅通过 M = K + 1 iid 高斯测量，这种优化将以很高的概率完全恢复 K 稀疏信号 [6]。但不幸的是，求解 （5） 在数值上既不稳定，又是一个 NP 完备问题，需要穷举所有

最小 '₁ 范数重建：压缩感知的惊喜在于，从 M ≥ cKlog（N/K） iid 高斯测量中，我们可以通过 '₁ 优化 [1,2] 以高概率稳定地重建 K 稀疏向量和紧密近似的可压缩向量 [1,2]

 0 0

 
s = argminksk1 使得 Θs= y（6）

_b

这是一个凸优化问题，可以方便地简化为称为基追踪 [1,2] 的线性规划，其计算复杂度约为 O（N3）.

总而言之，压缩传感数据采集系统包括基于 Φ 的随机测量，然后进行线性规划重建以获得 x.

讨论

几何解释

R^N 中压缩感应问题的几何结构有助于我们直观地了解为什么 '₁ 重建成功，而 '₂ 重建失败。首先，请注意 R^N 中所有 K 稀疏向量 s 的集合是一个高度非线性的空间，由与坐标轴对齐的所有 K 维超平面组成（参见图 2（a））。因此，稀疏向量位于 R^N 中的坐标轴附近.

为了直观地解释 '2 重建失败的原因，请注意平移的零空间 H = N（Θ）+s 的维度为 （N −M），并且由于矩阵 Θ 中的随机性而以随机角度定向。参见图 2（b），但在实践中要注意

因此既不稀疏也不接近正确答案 s.

与 '₂ 球形成鲜明对比的是，图 2（c） 中的 '1 球是“尖的”，点沿坐标轴对齐（并且随着环境维度 N 的增长而变得更尖）。因此，当我们炸毁 '₁ 球时，它将首先在坐标轴附近的一个点接触平移的零空间 H，这正是稀疏向量 s 所在的位置。

模拟信号

虽然我们关注的是离散时间信号 x，但压缩感应也适用于模拟信号 x（t），它可以只使用来自某个连续基或字典的 N 个可能元素中的 K 来稀疏表示

 
（一）

图 2：（a） 稀疏向量 s 位于 K 维超平面上，与 RN 中的坐标轴对齐，因此靠近轴。（b） 通过 2 最小化进行压缩感应恢复不会在平移的零空间（绿色超平面）上找到正确的稀疏解 s，而是在非稀疏向量 s 上找到正确的稀疏解 s。（c） 在 b 足够多的测量中，通过 1 最小化进行恢复确实找到了正确的稀疏解 s.

实例

考虑图 3（a） 中的“单像素”压缩数码相机，它直接获取 M 个随机线性测量值，而无需先收集 N 个像素值 [9]。 与所需图像 x 对应的入射光场不是聚焦在 CCD 或 CMOS 采样阵列上，而是从由 N 个微小镜子阵列组成的数字微镜器件 （DMD） 反射。 （DMD 存在于许多计算机投影仪和投影电视中。然后，反射光由第二个透镜收集并聚焦到单个光电二极管（单个像素）上。每个反射镜可以独立地朝向光电二极管（对应于 1）或远离光电二极管（对应于 0）。每个测量 y的获取方式如下：随机数生成器 （RNG） 以伪随机 0/1 模式设置镜像方向，以创建测量矢量φ。然后，光电二极管的电压等于 y，即 φ与所需图像 x 之间的内积。该过程重复 M 次以获取 y 中的所有条目。图 3（b） 和 （c） 说明了原型单像素 b 所采用的目标对象和 ima ge x

相机 [9] 使用的随机测量值比重建像素少约 60%。在这里，重建是通过总变分优化 [1] 进行的，这与小波域中的 '₁ 重建密切相关。

单像素压缩传感方法的一个主要优点是，该相机可以适应难以或昂贵的波长进行成像，而这些波长很难或成本很高。

它还可以随着时间的推移获取数据以实现视频重建 [9]。

结论

在本次讲座中，我们了解到采样并不是获取信号的唯一方法。当感兴趣的信号是可压缩的或稀疏的时，采用随机测量和优化来仅获取我们需要的测量值可以更加高效和简化。我们 （a）

图 3：（a） 单像素压缩传感相机。（b） 足球的传统数码相机图像。（c） 从 M =1600 b 中恢复的同一球（N = 4096 像素）的 64×64 张黑白图像 x

相机在 （a） 中进行的随机测量。（b） 和 （c） 中的图像不是要对齐的。

我们还了解到，对于重建，我们的老朋友最小二乘法让我们失败了，我们需要寻找其他风格的凸优化，如线性规划（另见 [4,10]）。压缩传感仍然是一个新兴领域，许多有趣的研究问题仍然存在。关于当前研究方向的一套相当详尽的参考资料可在 dsp.rice.edu/cs.

引用

E. Candes、J. Romberg 和 T. Tao，“稳健不确定性原理： 从高度不完整的频率信息中精确重构信号”，IEEE Trans. Inform。理论，第 52 卷，第 2 期，第 489-509 页，2006 年 2 月。

D. Donoho，“压缩传感”，IEEE Trans. Inform。理论，第 52 卷，第 4 期，第 1289-1306 页，2006 年 4 月。

S. Mallat，信号处理小波之旅学术出版社，1999 年。

J. Tropp 和 A. C. Gilbert，“通过正交匹配追踪从部分信息中恢复信号”，2005 年 4 月，www-personal.umich.edu/∼jtropp/papers/TG05-Signal-Recovery.pdf.

R. G. Baraniuk、M. Davenport、R. DeVore 和 M. B. Wakin，“Johnson-Lindenstrauss 引理与压缩传感相遇”，2006 年，dsp.rice.edu/cs/jlcs-v03.pdf.

D. Baron、M. B. Wakin、M. Duarte、S. Sarvotham 和 R. G. Baraniuk，“分布式压缩传感”，2005 年，dsp.rice.edu/cs/DCS112005.pdf.

S. Kirolos、J. Laska、M. Wakin、M. Duarte、D. Baron、T. Ragheb、Y. Massoud 和 R. G. Baraniuk，“通过随机解调进行模数到信息转换”，IEEE 达拉斯电路和系统研讨会，2006 年 10 月。

M. Vetterli、P. Marziliano 和 T. Blu，“有限创新率的采样信号”，IEEE Trans. Signal Processing，第 50 卷，第 6 期，第 1417-1428 页，2002 年 6 月。

D. Takhar、V. Bansal、M. Wakin、M. Duarte、D. Baron、J. Laska、K. F. Kelly 和 RG Baraniuk，“压缩传感相机：使用数字微镜的新理论和实现”，载于 Proc. 计算。2006 年 1 月，圣何塞 SPIE 电子成像公司的成像 IV。[10] J. Haupt 和 R. Nowak，“噪声随机投影的信号重建”，IEEE Trans. Inform。理论，第 52 卷，第 9 期，第 4036-4048 页，2006 年 9 月。

致谢：这项工作得到了 NSF、DARPA、ONR、AFOSR 和德州仪器 （TI） 领导大学计划的资助。感谢 Rice DSP 小组和 Ron DeVore 的许多启发性讨论。感谢 Justin Romberg 在图 3 中重建的帮助。

作者： Richard G. Baraniuk （richb@rice.edu） 是莱斯大学电气与计算机工程专业的 Victor E. Cameron 教授。他的研究兴趣包括多尺度分析、逆问题、分布式信号处理和传感器网络。由于他的研究，他获得了美国国家科学基金会和海军研究办公室颁发的国家青年研究员奖，以及莱斯大学和伊利诺伊大学的成就奖。在他的教学方面，他曾三次获得 Eta Kappa Nu 颁发的 C. Holm es MacDonald 国家杰出教学奖 和莱斯大学的 George R. Brown 卓越教学奖。他于 2001 年当选为 IEEE 院士。