压缩传感综述

压缩传感综述
李树涛1
魏 丹1
摘 要 在传统采样过程中, 为了避免信号失真, 采样频率不得低于信号最高频率的 2 倍. 然而对于数字图像、视频的获取,
依照香农(Shannon) 定理会导致海量采样数据, 大大增加了存储和传输的代价. 近年来, 一种新兴的压缩传感理论为数据采集
技术带来了革命性的突破, 得到了研究人员的广泛关注. 压缩传感采用非自适应线性投影来保持信号的原始结构, 能通过数值
最优化问题准确重构原始信号. 压缩传感以远低于奈奎斯特频率进行采样, 在压缩成像系统、模拟/信息转换、生物传感等领
域有着广阔的应用前景. 本文主要介绍了压缩传感的基本理论及相关应用, 并对其研究前景进行了展望.
关键词 压缩传感, 稀疏表示, 信号重构, 约束等距性, 压缩成像
中图分类号 TN911.7
A Survey on Compressive Sensing
LI Shu-Tao1
WEI Dan1
Abstract In the traditional signal sampling process, Shannon theorem must be satis¯ed for preventing signal distortion.
But in some practical applications (such as image and video processing systems), an increased sampling frequency will
substantially increase the data storage and transmission costs. Di®erent from the traditional signal acquisition process,
compressive sensing, which is a new theory that captures and represents compressible signals at a sampling rate signi¯cantly
below the Nyquist rate. It ¯rst employs nonadaptive linear projections that preserve the structure of the signal, and then
the signal reconstruction is conducted using an optimization process from these projections. Compressive sensing has
broad applications such as compressive imaging, analog-to-information conversion, biosensing, etc. This paper surveys the
principles of compressive sensing and its related applications. Some further work on this theory is also presented.
Key words Compressive sensing, sparse representation, signal reconstruction, restricted isometry property, compressive
imaging

传统的信号获取和处理过程主要包括采样、压
缩、传输和解压缩四个部分, 如图 1 所示. 其采样过
程必须满足香农采样定理, 即采样频率不能低于模
拟信号频谱中最高频率的2 倍. 在信号压缩中, 先对
信号进行某种变换, 如离散余弦变换或小波变换, 然
后对少数绝对值较大的系数进行压缩编码, 舍弃零
或接近于零的系数. 通过对数据进行压缩, 舍弃了采
样获得的大部分数据, 但不影响 \感知效果"[1]
. 例
如, 在运用数百万像素的数码相机对场景进行成像
时, 将会得到海量的像素信息, 但通过压缩编码后,
只对部分信息进行存储和传输, 最后通过相应的解
压缩算法对原始图像进行重构.
如果信号本身是可压缩的,那么是否可以直接获
收稿日期 2008-09-01 收修改稿日期 2009-03-13
Received September 1, 2008; in revised form March 13, 2009
国家自然科学基金 (60871096, 60835004), 高等学校博士学科点专项
科研基金 (200805320006), 教育部科学技术研究重点项目 (2009-120)
资助
Supported by National Natural Science Foundation of China
(60871096, 60835004), Specialized Research Fund for the Doc-
toral Program of Higher Education of China (200805320006),
and the Key Project of Science and Technology of Chinese Min-
istry of Education (2009-120)
1. 湖南大学电气与信息工程学院 长沙 410082
1. College of Electrical and Information Engineering, Hunan
University, Changsha 410082
DOI: 10.3724/SP.J.1004.2009.01369
图 1 传统的信息获取与处理流程
Fig. 1 The traditional information acquisition and
processing
取其压缩表示 (即压缩数据), 从而略去对大量无用
信息的采样呢? Candµes 在 2006 年从数学上证明了
可以从部分傅里叶变换系数精确重构原始信号, 为
压缩传感奠定了理论基础[2]
. Candµes 和 Donoho 在
相关研究基础上于 2006 年正式提出了压缩传感的
概念[1; 3]
. 其核心思想是将压缩与采样合并进行, 首
先采集信号的非自适应线性投影 (测量值), 然后根
据相应重构算法由测量值重构原始信号[1]
. 压缩传
感的优点在于信号的投影测量数据量远远小于传统
采样方法所获的数据量, 突破了香农采样定理的瓶
颈, 使得高分辨率信号的采集成为可能. 压缩传感理
论框架如图 2 所示.
压缩传感理论主要包括信号的稀疏表示、编码
测量和重构算法等三个方面[4]
. 信号的稀疏表示就
是将信号投影到正交变换基时, 绝大部分变换系数
的绝对值很小, 所得到的变换向量是稀疏或者近似
稀疏的, 可以将其看作原始信号的一种简洁表达[5]
,

图 2 压缩传感理论框架
Fig. 2 Theory frame of compressive sensing
这是压缩传感的先验条件, 即信号必须在某种变
换下可以稀疏表示. 通常变换基可以根据信号本
身的特点灵活选取, 常用的有离散余弦变换基、
快速傅里叶变换基、离散小波变换基[6]
、Curvelet
基[7]
、Gabor 基[8]
以及冗余字典[8¡10]
等. 在编码测
量中, 首先选择稳定的投影矩阵, 为了确保信号的线
性投影能够保持信号的原始结构, 投影矩阵必须满
足约束等距性(Restricted isometry property, RIP)
条件[11]
, 然后通过原始信号与测量矩阵的乘积获得
原始信号的线性投影测量. 最后, 运用重构算法由测
量值及投影矩阵重构原始信号. 信号重构过程一般
转换为一个最小 l0 范数的优化问题, 求解方法主要
有最小 l1 范数法[2; 12]
、匹配追踪系列算法[13]
、最小
全变分方法[2]
、迭代阈值算法[14]
等.
其中, ª = [à à Ã1jà à Ã2j ¢ ¢ ¢ jà à ÃN], à à Ãi 为列向量, N £1 的
列向量x x x是f f f 的加权系数序列, xi = hf f f;Ã Ã Ãii = Ã Ã ÃT
i f f f
可见x x x 是信号f f f 的等价表示, 如图 4 所示. 如果
只有很少的大系数, 则称信号f f f 是可压缩的; 如果
只有 K 个元素为非零, 则称x x x 为信号f f f 的 K 稀疏
(a) 原始图像
(a) Original image
(b) 图像小波变换系数
(b) Transform coe±cients

鉴于信号的稀疏表示在压缩传感理论中的重要
性, 本文第1 节对其进行了介绍; 第2 节介绍了压缩
传感基本原理; 第 3 节研究了压缩传感测量矩阵; 第
4 节讨论了信号重构算法; 第 5 节介绍压缩传感的
应用; 最后对压缩传感领域的研究前景进行展望.
1 信号稀疏表示
如果一个信号中只有少数元素是非零的, 则该
信号是稀疏的. 通常时域内的自然信号都是非稀疏
的, 但在某些变换域可能是稀疏的. 例如, 对于一幅
自然图像, 几乎所有的像素值都是非零的, 但是将其
变换到小波域时, 大多数小波系数的绝对值都接近
于零, 并且有限的大系数能够表示出原始图像的绝
大部分信息. 图 3 (a) 是大小为 512 £ 512 的灰度图
像, 其小波系数如图3 (b) 所示(为增强其可视性, 系
数的排列是随机的). 图 3 (c) 是由绝对值最大的前
10% 个系数重构出的图像, 可以看出重构图像与原
始图像差别很小, 但是需要保存的信息大大减少了.
根据调和分析理论, 一个长度为 N 的一维离散
时间信号 f f f, 可以表示为一组标准正交基的线性组
合
f f f =
N X xià à Ãi 或 f f f = ªx x x (1)
(c) 重构图像
(c) Reconstructed image
图 3 灰度图像小波基稀疏表示
Fig. 3 Sparse representation with wavelet basis
(512 £ 512)
图 4 用基 ª 进行稀疏表示 (3 稀疏)
Fig. 4 Sparse representation based on ª (3-sparse)

表示. 另外, 当信号不能用正交基稀疏表示时, 可以
采用冗余字典稀疏表示[8¡10]
.
2 压缩传感
首先考虑一般的信号重构问题, 即已知某一个
测量矩阵 © 2 RM£N (M ¿ N) 以及某未知信号x x x
在该矩阵下的线性测量值y y y 2 RM
y y y = ©x x x (2)
方程 (2) 也可以看作原信号x x x 在 © 下的线性投影,
现在考虑由 y y y 重构 x x x. 很显然, 由于 y y y 的维数远远
低于x x x 的维数, 方程 (2) 有无穷多个解, 即该问题是
不适定的, 很难重构原始信号. 然而如果原始信号x x x
是K 稀疏的, 并且y y y 与© 满足一定条件, 理论证明,
信号 x x x 可以由测量值 y y y 通过求解最优 l0 范数问题
精确重构[2]
:
^ x x x = argmin kx x xk0 s:t: ©x x x = y y y (3)
式中, k ¢ k0 为向量的 l0 范数, 表示向量x x x 中非零元
素的个数. Candµes 等指出, 如果要精确重构 K 稀
疏信号x x x, 测量次数 M (即y y y 的维数) 必须满足 M
= O(K ln(N)), 并且矩阵© 必须满足约束等距性条
件[15¡16]
. 约束等距性条件将在第 3 节中详细讨论.
然而, 常见的自然信号在时域内几乎都是不稀
疏的, 因而上述信号重构过程不能直接应用于自然
信号的重构. 第1 节中的信号稀疏表示理论指出, 自
量线性测量通过求解最优化问题 (5) 直接得到信号
f f f 的压缩表示y y y, 突破了香农采样定理的瓶颈, 降低
了对传感器件分辨率的要求, 使得超高分辨率信号
获取成为可能.
图 5 压缩传感线性测量过程
Fig. 5 The linear measurement of compressive sensing
通过上述分析可以看到, 在压缩传感中, 测量矩
阵的设计和稀疏信号的重构是两个非常重要的问题.
设计稳定的测量矩阵, 应使得表示图像特征的显著
信息不会因为维数的减少而丢失. 由于最优化问题
(5) 本质上是一个 NP-hard 问题, 通常需要对该问
题进行转换, 如将 l0 范数转化为 l1 范数问题加以解
决. 下面对测量矩阵和重构算法的相关研究进行详
细介绍.
3 测量矩阵
为了重构稀疏信号, Candµes 和Tao 给出并证明
了传感矩阵 ~ © 必须满足约束等距性条件[16]
. 对于任. 1 ,
然信号可以通过某种变换 ª 进行稀疏表示, 即f f f =
ªx x x, x x x 为信号 f f f 在 ª 变换域的稀疏表示. 考虑测
量公式y y y = ©f f f, 并且f f f 是可以稀疏表示的, 即f f f =
ªx x x, 则有
y y y = ©f f f = ©ªx x x = ~ ©x x x (4)
其中, ~ © = ©ª 为M £N 的矩阵, 被称为传感矩阵,
如图 5 所示. y y y 可以看作是稀疏信号x x x 关于测量矩
阵 ~ © 的测量值. 这时如果 ~ © 满足约束等距条件, 可
以通过求解一个类似式 (3) 的最优 l0 范数问题 (5)
来重构稀疏信号x x x, 即
^ x x x = argmin kx x xk0 s:t: ~ ©x x x = y y y (5)
由于 ª 是固定的, 要使得 ~ © = ©ª 满足约束等距条
件, 则测量矩阵 © 就必须满足一定的条件, 我们将
在第 3 节详细分析 © 的设计问题. 如果已经得到了
f f f 的稀疏表示 ^ x x x, 可以进一步由变换基 ª 通过下式
精确重构原始信号 ^ f f f
^ f f f = ª^ x x x (6)
这就是压缩传感的核心思想, 即与传统信号采样方
法对原始信号f f f 先采样后压缩不同, 压缩传感由少
了传感矩阵 ~ © 必须满足约束等距性条件[16]
. 对于任
意c c c 2 RjTj
和常数 ±K 2 (0; 1), 如果
(1 ¡ ±K)kc c ck2
2 · k~ ©Tc c ck2
2 · (1 + ±K)kc c ck2
2 (7)
成立, 其中 T ½ f1; ¢ ¢ ¢ ;Ng, jTj · K, ~ ©T 为 ~ © 中
由索引T 所指示的相关列构成的大小为K £jTj 的
子矩阵, 则称矩阵 ~ © 满足约束等距性. 通常, 对于一
个 K 稀疏信号x x x (其 K 个非零值的位置是未知的),
式 (5) 可以从y y y 精确重构出x x x 的充分条件是矩阵 ~ ©
对于任意c c c 2 RjTj
和常数 ±2K 2 (0; 1) 有 2K 阶约
束等距性, 即
(1 ¡ ±2K)kc c ck2
2 · k~ ©Tc c ck2
2 · (1 + ±2K)kc c ck2
2 (8)
成立, 其中 T ½ f1; ¢ ¢ ¢ ;Ng, jTj · 2K.
Baraniuk 在文献 [4] 中给出约束等距性的等价
条件是测量矩阵 © 和稀疏表示的基 ª 不相关, 即要
求 © 的行Á Á Áj 不能由 ª 的列Ã Ã Ãi 稀疏表示, 且 ª 的
列 Ã Ã Ãi 不能由 © 的行 Á Á Áj 稀疏表示. 直接构造一个
测量矩阵 © 使得 ~ © = ©ª 满足约束等距性, 即保证
矩阵中任意 2K 列都不相关很难做到. 由于 ª 是固
定的, 要使得 ~ © = ©ª 满足约束等距条件, 可以通
过设计测量矩阵 © 解决. 文献 [16¡17] 证明了当 ©

是高斯随机矩阵时, 传感矩阵 ~ © 能以较大概率满足
约束等距性条件. 因此可以通过选择一个大小为 M
£ N 的高斯测量矩阵得到, 其中每一个值都满足
N(0; 1=N) 的独立正态分布. 高斯测量矩阵的优点
在于它几乎与任意稀疏信号都不相关, 因而所需的
测量次数最小. 但缺点是矩阵元素所需存储空间很
大, 并且由于其非结构化的本质导致其计算复杂.
其他常见的能使传感矩阵满足约束等距性的测
量矩阵还包括一致球测量矩阵、二值随机矩阵、局
部傅里叶矩阵、局部哈达玛测量矩阵以及托普利兹
(Toeplitz) 矩阵等[15]
. 一致球测量矩阵指矩阵的列
在球 Sn¡1 上是独立同分布随机一致的, 并且当测量
次数为 M = O(K ln(N)) 时, 准确重构信号的概率
很大[1; 18¡19]
. 二值随机矩阵是指矩阵中每个值都服
从对称伯努利分布 P(©ij = §1=
p
M) = 1=2[3; 15]
,
研究表明当 K · C £ M= ln(N=M) 时, 准确重构
信号的概率极大, 并且重构速度很快. 方红等将亚
高斯随机投影引入到压缩传感理论, 给出了两种新
类型的测量矩阵: 稀疏投影矩阵和非常稀疏投影
矩阵[20]
. 局部傅里叶矩阵可以首先从傅里叶矩阵
中随机选择 M 行, 然后再对列进行单位正则化得
到[15; 21]
. 傅里叶矩阵的一个突出优点是可以利用快
速傅里叶变换快速计算, 大大降低了采样系统的复
杂性, 然而由于其通常只与时域稀疏的信号不相关,
应用范围受到了限制. 局部哈达玛测量矩阵是从 N
维哈达玛矩阵中随机选择 M 行得到[22¡23]
, 当 M
¸ K
pN=B(lnN)2 (其中 B 是块的维数) 时, 置乱
(Scrambled) 块哈达玛矩阵可以以极大概率准确重
点.
4 信号重构算法
信号重构算法是压缩传感理论的核心, 是指由
M 次测量向量 y y y 重构长度为 N (M ¿ N) 的稀
疏信号 x x x 的过程. Candµes 等证明了信号重构问题
可以通过求解最小 l0 范数问题 (3) 加以解决. 但
Donoho 指出, 最小 l0 范数问题是一个 NP-hard 问
题, 需要穷举x x x 中非零值的所有CK N 种排列可能, 因
而无法求解[27]
. 鉴于此, 研究人员提出了一系列求
得次最优解的算法, 主要包括最小 l1 范数法、匹配
追踪系列算法、迭代阈值法以及专门处理二维图像
问题的最小全变分法等.
4.1 最小l l l1 范数法
采用 l1 范数代替 l0 范数[2]
, 得到了如下问题:
^ x x x = argmin kx x xk1 s:t: ©x x x = y y y (9)
文献 [28¡29] 证明了问题 (9) 和问题 (3) 是等价的.
问题 (9) 是一个凸最优问题, 可以转化为一个线性
规划问题加以求解, 计算复杂度为O(N3), 这种方法
也称为基追踪方法 (Basis pursuit, BP)[28]
. 如果考
虑重构误差, 上述问题可以转换为如下最小 l1 范数
问题:
min kx x xk1 s:t: k©x x x ¡y y yk2 · " (10)
该问题可以利用二阶圆锥规划求解[17]
.从对称伯努利分布 P(©ij = §1=
p
M) = 1=2[3; 15]
,
研究表明当 K · C £ M= ln(N=M) 时, 准确重构
信号的概率极大, 并且重构速度很快. 方红等将亚
高斯随机投影引入到压缩传感理论, 给出了两种新
类型的测量矩阵: 稀疏投影矩阵和非常稀疏投影
矩阵[20]
. 局部傅里叶矩阵可以首先从傅里叶矩阵
中随机选择 M 行, 然后再对列进行单位正则化得
到[15; 21]
. 傅里叶矩阵的一个突出优点是可以利用快
速傅里叶变换快速计算, 大大降低了采样系统的复
杂性, 然而由于其通常只与时域稀疏的信号不相关,
应用范围受到了限制. 局部哈达玛测量矩阵是从 N
维哈达玛矩阵中随机选择 M 行得到[22¡23]
, 当 M
¸ K
pN=B(lnN)2 (其中 B 是块的维数) 时, 置乱
(Scrambled) 块哈达玛矩阵可以以极大概率准确重
构信号. Tsaig 对一致球测量矩阵、二值随机矩阵、
局部哈达玛测量矩阵以及局部傅里叶矩阵的性能进
行了比较, 发现将这几类矩阵作为测量矩阵时重构
信号的误差都比较小, 并且随着测量数目的增加进
一步减小[22]
.
文献 [24] 提出了形式固定的托普利兹矩阵以及
循环矩阵, 发现当 K · C £M3=ln(N=M) 时, 这两
种矩阵使传感矩阵以很大概率满足约束等距性, 并
且可以直接应用快速傅里叶变换得到快速的重构算
法, 能够明显减少高维问题的计算和存储复杂度, 因
而对高维问题特别有效. Sebert 等提出将块托普利
兹矩阵应用于压缩传感, 并做了大量实验, 结果表明
应用这种测量矩阵不仅有很好的重构结果, 而且可
以明显加快运算速度和减少存储空间[25]
.
此外, Do 等提出了结构化随机矩阵[26]
, 该矩阵
具有与几乎所有其他正交矩阵 (单位阵和极度稀疏
矩阵除外) 不相关的优点, 可以分解成定点、结构化
分块对角矩阵与随机置换向量或伯努利向量点积的
形式. 该矩阵可以看成是随机高斯/伯努利矩阵和部
4.1 最小l l l1 范数法
采用 l1 范数代替 l0 范数[2]
, 得到了如下问题:
^ x x x = argmin kx x xk1 s:t: ©x x x = y y y (9)
文献 [28¡29] 证明了问题 (9) 和问题 (3) 是等价的.
问题 (9) 是一个凸最优问题, 可以转化为一个线性
规划问题加以求解, 计算复杂度为O(N3), 这种方法
也称为基追踪方法 (Basis pursuit, BP)[28]
. 如果考
虑重构误差, 上述问题可以转换为如下最小 l1 范数
问题:
min kx x xk1 s:t: k©x x x ¡y y yk2 · " (10)
该问题可以利用二阶圆锥规划求解[17]
.
问题(9) 也可以用内点法[30]
、 梯度投影法[31]
以
及同伦算法[32]
求解. 比较而言, 内点法速度较慢但
非常精确, 梯度投影法则具有很好的运算速度, 而同
伦算法对小尺度问题比较实用. 此外, 为进一步减少
测量噪声对重构算法的影响, Candµes 等还提出了加
权最小 l1 范数重构算法[12]
, 这种方法通过重新设置
最小化 l1 范数问题来提高稀疏信号的重构质量.
4.2 匹配追踪算法
匹配追踪算法(Matching pursuit, MP) 是一种
贪婪迭代算法, 其基本思想是在每一次的迭代过程
中, 从过完备原子库 (即测量矩阵 ©) 里选择与信号
最匹配的原子来构建稀疏逼近, 并求出信号表示残
差, 然后继续选择与信号残差最为匹配的原子, 经过
一定次数的迭代, 信号可以由一些原子线性表示. 但
是由于信号在已选定原子 (测量矩阵的列向量) 集合
上的投影的非正交性使得每次迭代的结果可能是次
最优的, 因此为获得收敛可能需要经过较多次迭代.
正交匹配追踪算法 (Orthogonal matching pursuit,

形式. 该矩阵可以看成是随机高斯/伯努利矩阵和部
分傅里叶变换矩阵的混合模型, 并保持了各自的优
正交匹配追踪算法 (Orthogonal matching pursuit,
OMP)[13]
则有效克服了这个问题, 该算法沿用了匹
配追踪算法中的原子选择准则, 只是通过递归地对

已选择原子集合进行正交化以保证迭代的最优性,
从而减少了迭代次数. 文献 [13] 中的实验表明, 对
固定 K 稀疏 N 维离散时间信号x x x, 用一个 M £ N
的高斯矩阵测量时, 只需 M = O(KlnN). 正交匹
配追踪算法以极大概率准确重构信号, 而且比最小
l1 范数法更快. 但是, 正交匹配追踪算法精确重构的
理论保证比最小 l1 范数法弱, 并非对所有信号都能
准确重构, 而且对于测量矩阵的要求比约束等距性
更加严格[33]
.
Needell 等在 OMP 基础上提出了正则正交匹
配追踪(Regularized orthogonal matching pursuit,
ROMP) 算法, 对所有满足约束等距性条件的矩阵
和所有稀疏信号都可以准确重构[33]
. 另外, 压缩采
样匹配追踪算法 (Compressive sampling matching
pursuit, CoSaMP) 也可以用于很好地重构信号, 提
供了比 OMP、ROMP 更全面的理论保证, 并且能
在采样过程中对噪声鲁棒[34]
.
综合考虑, 匹配追踪系列算法对于维数较低的
小尺度信号问题运算速度很快, 但是对于存在噪声
的大尺度信号问题, 重构结果不是很精确, 也不具有
鲁棒性.
4.3 最小全变分法
相对于适合一维信号重构的最小 l1 范数法,
Candµes 等从大量自然图像的离散梯度都是稀疏的
角度出发, 提出了更适合二维图像重构的最小全变
分法[2]
. 图像压缩传感的全变分模型为
5 压缩传感的应用
压缩传感理论带来了信号采样理论的变革, 具
有广阔的应用前景, 包括压缩成像、模拟信息转换、
生物传感等. 本节将对这些应用作简要介绍.
5.1 压缩成像
运用压缩传感原理, 美国 RICE 大学成功研制
了 \单像素" 压缩数码照相机[38]
, 设计原理是首先
通过光路系统将成像目标投影到一个数字微镜器件
上, 其反射光由透镜聚焦到单个光敏二极管上, 光敏
二极管两端的电压值即为一个测量值y, 将此投影操
作重复 M 次, 得到测量向量y y y, 然后用最小全变分
算法构建的数字信号处理器重构原始图像 f f f. 数字
微镜器件由数字电压信号控制微镜片的机械运动以
实现对入射光线的调整, 相当于式 (4) 的 0-1 随机
测量矩阵 ©. 由于该相机直接获取的是 M 次随机
线性测量值, 而不是获取原始信号的 N (M ¿ N)
个像素值, 为低像素相机拍摄高质量图像提供了可
能. 压缩传感技术也可以应用于雷达成像领域, 与传
统雷达成像技术相比压缩传感雷达成像实现了两个
重要改进: 在接收端省去脉冲压缩匹配滤波器; 同时
由于避开了对原始信号的直接采样, 降低了接收端
对模数转换器件带宽的要求. 设计重点由传统的设
计昂贵的接收端硬件转化为设计新颖的信号恢复算
法, 从而简化了雷达成像系统[39]
. Bhattacharya 等
将压缩传感理论应用到合成孔径雷达图像数据获取

4.3 最小全变分法
相对于适合一维信号重构的最小 l1 范数法,
Candµes 等从大量自然图像的离散梯度都是稀疏的
角度出发, 提出了更适合二维图像重构的最小全变
分法[2]
. 图像压缩传感的全变分模型为
minTV(f f f) s:t: y y y = ©f f f (11)
其中, 目标函数 TV(f f f) 为图像离散梯度之和, 即
TV(f f f) = Pij
p(fi+1;j ¡ fi;j)2 + (fi;j+1 ¡ fi;j)2 .
该问题的求解可以转换为二阶锥规划问题[35]
. 最
小全变分模型可以有效地解决图像压缩重构问题,
重构结果精确而且鲁棒, 但是运算速度较慢.
4.4 迭代阈值法
最小 l1 范数法以及匹配追踪等算法可以有效地
解决压缩传感的信号重构问题, 但是这些算法都没
有对 l0 范数问题 (3) 进行直接求解. 对此, Kings-
bury 等提出了求解该问题的迭代阈值算法[36¡37]
.
然而由于问题 (3) 的非凸特性, 这些算法只能保证
收敛到局部最优解, 而且这些解有可能是非稀疏的.
因而迭代阈值算法对初值非常敏感, 很难直接应用
于信号重构. 但是如果能够找到一个合适的初值, 迭
代算法可以找到问题 (3) 的全局最优解. 因此该算
法可以与其他算法, 如MP 相结合, 由这些算法提供
初值. 实验证明这种策略能够提供比单独匹配追踪
算法更好的结果[14]
.
重要改进: 在接收端省去脉冲压缩匹配滤波器; 同时
由于避开了对原始信号的直接采样, 降低了接收端
对模数转换器件带宽的要求. 设计重点由传统的设
计昂贵的接收端硬件转化为设计新颖的信号恢复算
法, 从而简化了雷达成像系统[39]
. Bhattacharya 等
将压缩传感理论应用到合成孔径雷达图像数据获取
上[40]
, 解决了海量数据采集和存储问题, 显著降低
了卫星图像处理的计算代价.
此外, 压缩传感技术也可以应用于医学成像领
域, 如稀疏核磁共振成像[41]
、压缩传感三维磁共振
波谱成像[42]
等.
5.2 信道编码
压缩传感理论中关于稀疏性、随机性和凸最
优化的结论可以直接应用于设计快速误差校正编
码, 这种编码方式在实时传输过程中不受误差的影
响[16]
. 在压缩编码过程中, 稀疏表示所需的基对于
编码器可能是未知的. 然而在压缩传感编码过程
中, 它只在译码和重构原信号时需要, 并不需要考
虑它的结构, 所以可以用通用的编码策略进行编码.
Haupt 等通过实验表明如果图像是高度可压缩的或
者信噪比(Signal to noise ratio, SNR) 充分大, 即使
测量过程存在噪声, 压缩传感方法仍然可以准确重
构图像[43]
. Wakin 等研究了基于压缩传感理论的视
频序列表示和编码方法[44]
; Stankovic 和 Marcia 分
别发展了视频压缩采样和压缩视频编码孔径重建问
题[45¡46]
; 为解决高维图像重建算法慢的问题, Gan
提出了基于块的压缩传感技术[47]
; Cevher 等利用源

图像与背景差图像更加稀疏的性质, 进行背景抽取,
可直接对图像中的关注目标成像[48]
.
5.3 模拟/信息转换
对于带宽非常高的信号, 例如雷达和通信信号
处理系统涉及的射频信号, 根据香农采样定理, 要获
得完整的信号信息, 所采用的模数转换器必须有很
高的采样频率. 然而由于传感器及转换硬件性能的
限制, 获得的信号的带宽远远低于实际信号的带宽,
存在较大的信息丢失. 对此Kriolos 等设计了基于压
缩传感理论的模拟/信息转换器[49¡50]
, 利用压缩传
感理论中测量信息可以得到完整信号的原理, 首先
获得原始信号的线性测量, 再利用后端数字信号处
理器重构原始信号或直接计算原始信号的统计数据
等信息. Laska 等进一步发展了基于随机采样系统
的模拟/信息转换器[51]
, 并给出了随机抽样系统的两
种实现模型. 第一种模型采用多个并行低采样率的
模数转换器, 每个模数转换器之间有等间隔的位移,
通过随机控制来自不同的模数转换器的采样, 实现
随机采样. 然而这种方法需要多个模数转换芯片, 每
个芯片利用率不高. 基于此作者又设计了第二种模
型, 通过一组电容和数字控制换向器随机采样, 该系
统只需要一个模数转换芯片即可.
5.4 生物传感
是更复杂的非确定性测量矩阵在硬件实现上比较复
杂, 虽然它们在仿真实验中能够取得很好的效果, 但
是难以硬件实现, 因此有必要对确定性测量矩阵进
行深入研究. 此外, 压缩传感技术建立在非自适应线
性测量基础之上, 不具有灵活性, 因而有必要研究自
适应压缩传感技术, 即根据不同的信号类型采用不
同的数据采样和重构策略.
2) 测量矩阵的优化问题
在第 1 节中提到, 当图像不能在正交基上稀疏
表示时, 可以将其扩展到冗余字典上进行稀疏表示.
例如对于某一类型的图像, 用学习算法如K-SVD 等
得到的字典通常可以使图像信号更加稀疏. 然而在
压缩传感技术中, 利用冗余的字典代替标准正交基
虽然可以更好地重构图像, 但由于在相应传感矩阵
中会出现较多相关列, 这些相关列对于图像重构没
有任何价值, 增加了算法的存储和计算的成本, 因
此, 如何平衡冗余字典的冗余度与传感矩阵中相关
列的数量, 即找到最优的冗余字典及其对应的传感
矩阵是值得研究的.
3) 测量值的应用研究
许多图像处理的最终目的并不是重构图像, 而
是为了得到有关目标的信息. 由压缩传感理论可知,
在一定条件下, 通过少量的测量值就可以准确重构
出原始图像, 也就是说少数的测量值能够保持原始
信号的结构和足够多信息. 因此, 少量的测量值可以

生物传感中的传统 DNA 芯片能平行测量多个
有机体, 但是只能识别有限种类的有机体, Sheikh
等运用压缩传感和群组检测原理设计的压缩传感
DNA 芯片克服了这个缺点[52]
, 压缩传感DNA 芯片
中的每个探测点都能识别一组目标, 从而明显减少
了所需探测点数量. 此外, 基于生物体基因序列稀疏
特性, Sheikh 等验证了可以通过置信传播的方法实
现压缩传感 DNA 芯片中的信号重构[53]
.
压缩传感理论还应用于信号检测和分类[54¡56]
、
无线传感器网络[57]
、数据通信[58¡59]
以及地球物理
数据分析[60]
等众多领域.
6 总结与展望
压缩传感理论的提出极大地丰富了信号获取理
论, 并为其他相关领域的研究提供了新技术和新思
路, 研究前景广阔. 然而目前压缩传感理论还不是很
完善, 相应的应用研究也刚刚起步, 尚有较多问题需
要在未来研究中得到突破:
1) 测量矩阵构造研究
在压缩传感中, 测量矩阵需要满足约束等距性
条件, 目前所采用的测量矩阵大多为非确定性测量
矩阵, 即随机矩阵. 例如在 RICE 大学单像素相机
信号的结构和足够多信息. 因此, 少量的测量值可以
直接用于实现各种图像处理任务, 如图像分类、特征
提取、目标检测以及信息融合等, 并且由于测量值数
目较少, 信息密度高, 可以大大减少相关算法的时间
和存储代价.
4) 图像超分辨率重构
图像的超分辨率重构是指从一幅或者多幅低分
辨率图像产生或者构建高分辨率图像的过程, 本质
上属于维数增加的问题, 具有不适定性. 在压缩传感
中, 从测量值到原始信号也是一个从低维到高维的
维数增加问题, 与超分辨率图像重构类似. 由于低分
辨率图像通常决定了高分辨图像的结构和大部分信
息, 因此借鉴压缩传感的相关思想实现新型的超分
辨率图像重构算法也是值得研究的. 例如, 如果将低
分辨率图像看成是在某种测量矩阵 (或者字典) 下的
测量值, 则超分辨图像重构问题便转换为如何构建
测量矩阵的字典构建问题.
5) 运动目标提取
基于图像序列的运动目标提取是计算机视觉领
域的一个核心问题, 广泛应用在视频监控、视频分
析、视频检索、基于运动信息的身份识别等方面. 当
把背景看成不变量时, 运动的目标可以更加稀疏地
表示, 符合压缩传感理论对信号的稀疏性要求. 因

研制中, 采用的就是较为简单的 0-1 伪随机矩阵. 但 此, 如何在压缩传感框架内, 利用图像序列运动目标

稀疏特性, 设计测量矩阵, 然后对图像序列的背景差
进行线性测量, 最后精确重构出运动目标也是值得
注意的研究方向.
6) 实时压缩传感成像系统研制
相对于压缩传感的理论研究进展, 其硬件实现
还处于起步阶段. 目前已取得成功的例子主要有
美国 RICE 大学研制的 \单像素" 数码相机, ARI-
ZONA 大学 Baheti 和 Neifeld 设计的具有特定功
能的结构成像设备, 以及 DUCK 大学研制的单景光
谱成像装置[61]
. 然而由于压缩重构算法的计算量比
较大, 难以达到实时性要求, 因此实时高性能压缩传
感成像系统是未来重要的研究方向.
除了构建高分辨成像系统, 压缩传感还可应用
于音频采集设备、节电型音频和图像采集设备、天
文学观测、军事侦察、资源探测、超声图像以及数字
减影血管造影技术等诸多方面.
References
1 Donoho D L. Compressed sensing. IEEE Transactions on
Information Theory, 2006, 52(4): 1289¡1306
2 Candµes E, Romberg J, Tao T. Robust uncertainty princi-
ples: exact signal reconstruction from highly incomplete
frequency information. IEEE Transactions on Information
Theory, 2006, 52(2): 489¡509
3 Candµes E. Compressive sampling. In: Proceedings of In-
ternational Congress of Mathematicians. Madrid, Spain:
European Mathematical Society Publishing House, 2006.
1433¡1452
4 Baraniuk R G. Compressive sensing. IEEE Signal Processing
11 Candµes E, Romberg J. Sparsity and incoherence in compres-
sive sampling. Inverse Problems, 2007, 23(3): 969¡985
12 Candµes E, Braun N, Wakin M B. Sparse signal and image
recovery from compressive samples. In: Proceedings of the
4th IEEE International Symposium on Biomedical Imaging:
From Nano to Macro. Washington D. C., USA: IEEE, 2007.
976¡979
13 Tropp J A, Gilbert A C. Signal recovery from random mea-
surements via orthogonal matching pursuit. IEEE Transac-
tions on Information Theory, 2007, 53(12): 4655¡4666
14 Blumensath T, Davies M E. Iterative thresholding for sparse
approximations. Journal of Fourier Analysis and Applica-
tions, 2008, 14(5-6): 629¡654
15 Candµes E, Tao T. Near optimal signal recovery from random
projections: Universal encoding strategies? IEEE Transac-
tions on Information Theory, 2006, 52(12): 5406¡5425
16 Candµes E, Tao T. Decoding by linear programming.
IEEE Transactions on Information Theory, 2005, 51(12):
4203¡4215
17 Candµes E, Romberg J, Tao T. Stable signal recovery from
incomplete and inaccurate measurements. Communications
on Pure and Applied Mathematics, 2006, 59(8): 1207¡1223
18 Donoho D L. For most large underdetermined systems of lin-
ear equations the minimal l1-norm solution is also the spars-
est solution. Communications on Pure and Applied Mathe-
matics, 2006, 59(6): 797¡829
19 Donoho D L. For most large underdetermined systems of
equations, the minimal l1-norm near-solution approximates
the sparsest near-solution. Communications on Pure and
Applied Mathematics, 2006, 59(7): 907¡9344 Baraniuk R G. Compressive sensing. IEEE Signal Processing
Magazine, 2007, 24(4): 118¡121
5 Olshausen B A, Field D J. Emergence of simple-cell recep-
tive ¯eld properties by learning a sparse code for natural
images. Nature, 1996, 381(6583): 607¡609
6 Mallat S. A Wavelet Tour of Signal Processing. San Diego:
Academic Press, 1996
7 Candµes E, Donoho D L. Curvelets | A Surprisingly E®ec-
tive Nonadaptive Representation for Objects with Edges,
Technical Report 1999-28, Department of Statistics, Stan-
ford University, USA, 1999
8 Sun Yu-Bao, Xiao Liang, Wei Zhi-Hui, ShaoWen-Ze. Sparse
representations of images by a multi-component Gabor per-
ception dictionary. Acta Automatica Sinica, 2008, 34(11):
1379¡1387
(孙玉宝, 肖亮, 韦志辉, 邵文泽. 基于 Gabor 感知多成份字典的图
像稀疏表示算法研究. 自动化学报, 2008, 34(11): 1379¡1387)
9 Aharon M, Elad M, Bruckstein A M. The K-SVD: an algo-
rithm for designing of overcomplete dictionaries for sparse
representations. IEEE Transactions on Image Processing,
2006, 54(11): 4311¡4322
10 Rauhut H, Schnass K, Vandergheynst P. Compressed sens-
ing and redundant dictionaries. IEEE Transactions on In-
formation Theory, 2008, 54(5): 2210¡2219
20 Fang Hong, Zhang Quan-Bing, Wei Shui. A method of im-
age reconstruction based on sub-Gaussian random projec-
tion. Journal of Computer Research and Development, 2008,
45(8): 1402¡1407
(方红, 章权兵, 韦穗. 基于亚高斯随机投影的图像重建方法. 计算机
研究与发展, 2008, 45(8): 1402¡1407)
21 Gilbert A C, Guha S, Indyk P, Muthukrishnan S, Strauss
M. Near-optimal sparse Fourier representations via sam-
pling. In: Proceedings of the 34th Annual ACM Symposium
on Theory of Computing. Quebec, Canada: ACM, 2006.
152¡161
22 Tsaig Y, Donoho D L. Extensions of compressed sensing.
Signal Processing, 2006, 86(3): 549¡571
23 Pinkus A. N-Widths in Approximation Theory. New York:
Springer-Verlag, 1985
24 Bajwa W U, Haupt J D, Raz G M, Wright S J, Nowak R D.
Toeplitz-structured compressed sensing matrices. In: Pro-
ceedings of the IEEE Workshop on Statistical Signal Pro-
cessing. Washington D. C., USA: IEEE, 2007. 294¡298
25 Sebert F, Zou Y M, Ying L. Toeplitz block matrices in com-
pressed sensing and their applications in imaging. In: Pro-
ceedings of International Conference on Technology and Ap-
plications in Biomedicine. Washington D. C., USA: IEEE,
2008. 47¡50

26 Do T T, Trany T D, Gan L. Fast compressive sampling
with structurally random matrices. In: Proceedings of the
IEEE International Conference on Acoustics, Speech and
Signal Processing. Washington D. C., USA: IEEE, 2008.
3369¡3372
27 Donoho D L. For most large underdetermined systems of lin-
ear equations, the minimal l1-norm solution is also the spars-
est solution. Communications on Pure and Applied Mathe-
matics, 2006, 59(6): 797¡829
28 Chen S B, Donoho D L, Saunders M A. Atomic decomposi-
tion by basis pursuit. SIAM Journal on Scienti¯c Comput-
ing, 1998, 20(1): 33¡61
29 Donoho D L, Elad M, Temlyakov V N. Stable recovery of
sparse overcomplete representations in the presence of noise.
IEEE Transactions on Information Theory, 2006, 52(1):
6¡18
30 Kim S J, Koh K, Lustig M, Boyd S, Gorinevsky D. An
interior-point method for large-scale l1 regularized least
squares. IEEE Journal of Selected Topics in Signal Process-
ing, 2007, 1(4): 606¡617
31 Fiqueiredo M A T, Nowak R D, Wright S J. Gradient pro-
jection for sparse reconstruction: application to compressed
sensing and other inverse problems. IEEE Journal of Se-
lected Topics in Signal Processing, 2007, 1(4): 586¡597
32 Donoho D L, Tsaig Y. Fast Solution of l1-Norm Minimiza-
tion Problems When the Solution May Be Sparse, Technical
Report, Department of Statistics, Stanford University, USA,
2008
33 Needell D, Vershynin R. Greedy signal recovery and un-
certainty principles. In: Proceedings of the Conference on
Computational Imaging. San Jose, USA: SPIE, 2008. 1¡12
34 Needell D, Tropp J A. CoSaMP: Iterative signal recovery
from incomplete and inaccurate samples. Applied and Com-
putational Harmonic Analysis, 2008, 26(3): 301¡321
35 Lobo M S, Vandenberghe L, Boyd S, Lebret H. Applications
of second-order cone programming. Linear Algebra and Its
Applications, 1998, 284(1-3): 193¡228
41 Lustig M, Donoho D L, Pauly J M. Sparse MRI: the applica-
tion of compressed sensing for rapid MR imaging. Magnetic
Resonance in Medicine, 2007, 58(6): 1182¡1195
42 Hu S, Lustig M, Chen A P, Crane J, Kerr A, Kelley D A
C. Compressed sensing for resolution enhancement of hyper-
polarized 13C °yback 3D-MRSI. Journal of Magnetic Res-
onance, 2008, 192(2): 258¡264
43 Haupt J, Nowak R. Compressive sampling vs. conventional
imaging. In: Proceedings of the IEEE International Confer-
ence on Image Processing. Washington D. C., USA: IEEE,
2006. 1269¡1272
44 Wakin M B, Laska J N, Duarte M F, Baron D, Sarvotham S,
Takhar D. An architecture for compressive imaging. In: Pro-
ceedings of IEEE International Conference on Image Pro-
cessing. Washington D. C., USA: IEEE, 2006. 1273¡1276
45 Stankovic V, Stankovic L, Cheng S. Compressive video sam-
pling. In: Proceedings of the European Signal Processing
Conference. Lausanne, Switzerland: Elsevier, 2008. 1¡5
46 Marcia R F,Willett R M. Compressive coded aperture video
reconstruction. In: Proceedings of the European Signal Pro-
cessing Conference. Lausanne, Switzerland: 2008. 6¡10
47 Gan L. Block compressed sensing of natural images. In:
Proceedings of the 15th International Conference on Digi-
tal Signal Processing. Washington D. C., USA: IEEE, 2007.
403¡406
48 Cevher V, Sankaranarayanan A, Duarte M F, Reddy D,
Baraniuk R G, Chellappa R. Compressive sensing for back-
ground subtraction. In: Proceedings of the 10th Euro-
pean Conference on Computer Vision. Marseille, France:
Springer, 2008. 155¡168
49 Kirolos S, Laska J,Wakin M, Duarte M F, Baron D, Ragheb
T. Analog-to-information conversion via random demodula-
tion. In: Proceedings of the IEEE Dallas Circuits and Sys-
tems Workshop. Richardson, USA: IEEE, 2006. 71¡74
50 Ragheb T, Kirolos S, Laska J, Gilbert A, Strauss M, Bara-

Applications, 1998, 284(1-3): 193¡228
36 Kingsbury N. Complex wavelets for shift invariant analysis
and ¯ltering of complex wavelets for shift invariant analysis
and ¯ltering of signals. Applied and Computational Har-
monic Analysis, 2001, 10(3): 234¡253
37 Herrity K K, Gilbert A C, Tropp J A. Sparse approxima-
tion via iterative thresholding. In: Proceedings of the IEEE
International Conference on Acoustics, Speech and Signal
Processing. Washington D. C., USA: IEEE, 2006. 624¡627
38 Duarte M F, Davenport M A, Takhar D, Sun T, Kelly
K F, Baraniuk R G. Single-pixel imaging via compressive
sampling. IEEE Signal Processing Magazine, 2008, 25(2):
83¡91
39 Baraniuk R, Steeghs P. Compressive radar imaging. In: Pro-
ceedings of the Radar Conference. Washington D. C., USA:
IEEE, 2007. 128¡133
40 Bhattacharya S, Blumensath T, Mulgrew B, Davies M. Fast
encoding of synthetic aperture radar raw data using com-
pressed sensing. In: Proceedings of the 14th Workshop
on Statistical Signal Processing. Washington D. C., USA:
IEEE, 2007. 448¡452
50 Ragheb T, Kirolos S, Laska J, Gilbert A, Strauss M, Bara-
niuk R. Implementation models for analog-to-information
conversion via random sampling. In: Proceedings of the 50th
Midwest Symposium on Circuits and Systems. Washington
D. C., USA: IEEE, 2007. 325¡328
51 Laska J, Kirolos S, Massoud Y, Baraniuk R, Gilbert A,
Iwen M. Random sampling for analog-to-information con-
version of wideband signals. In: Proceedings of the IEEE
Dallas/CAS Workshop on Design, Applications, Integra-
tion and Software. Washington D. C., USA: IEEE, 2006.
119¡122
52 Sheikh M A, Milenkovic O, Baraniuk R G. Designing com-
pressive sensing DNA microarrays. In: Proceedings of the
IEEE International Workshop on Computational Advances
in Multi-Sensor Adaptive Processing. Washington D. C.,
USA: IEEE, 2007. 141¡144
53 Sheikh M A, Sarvotham S, Milenkovic O, Baraniuk R G.
DNA array decoding from nonlinear measurements by belief
propagation. In: Proceedings of the 14th Workshop on Sta-
tistical Signal Processing. Washington D. C., USA: IEEE,
2007. 215¡219

54 Haupt J, Nowak R. Compressive sampling for signal detec-
tion. In: Proceedings of the IEEE International Conference
on Acoustics, Speech and Signal Processing. Washington
D.C., USA: IEEE, 2007. 1509¡1512
55 Davenport M A, Wakin M B, Baraniuk R G. Detection
and Estimation with Compressive Measurements, Technical
Report TREE 0610, Department of Electrical Engineering,
Rice University, USA, 2006
56 Haupt J, Castro R, Nowak R, Fudge G, Yeh A. Compressive
sampling for signal classi¯cation. In: Proceedings of the For-
tieth Asilomar Conference on the Signals, Systems and Com-
puters. Washington D. C., USA: IEEE, 2006. 1430¡1434
57 Bajwa W, Haupt J, Sayeed A, Nowak R. Compressive wire-
less sensing. In: Proceedings of the International Conference
on Information Processing in Sensor Networks. Nashville,
USA: ACM, 2006. 134¡142
58 Taubock G, Hlawatsch F. A compressed sensing technique
for OFDM channel estimation in mobile environments: ex-
ploiting channel sparsity for reducing pilots. In: Proceed-
ings of the IEEE International Conference on Acoustics,
Speech, and Signal Processing. Las Vegas, USA: IEEE, 2008.
2885¡2888
59 BajwaWU, Haupt J, Raz G, Nowak R. Compressed channel
sensing. In: Proceedings of the 42nd Annual Conference on
Information Sciences and Systems. Washington D. C., USA:
IEEE, 2008. 5¡10
60 Hennenfent G, Herrmann F J. Simply denoise: wave ¯eld re-
construction via jittered undersampling. Geophysics, 2008,
73(3): 19¡28
61 Gehm M E, John R, Brady D J, Willett R M, Schulz T
disperser architecture. Optics Express, 2007, 15(21): 14013
¡14027
李树涛 湖南大学电气与信息工程学院
教授. 2001 年于湖南大学获得控制理论
与控制工程专业博士学位. 主要研究方
向为图像处理, 模式识别和信息融合. 本
文通信作者.
E-mail: shutao [e-mail]
(LI Shu-Tao Professor at the Col-
lege of Electrical and Information Engineering, Hunan Uni-
versity. He received his Ph.D. degree in control theory and
control engineering from Hunan University in 2001. His
research interest covers image processing, pattern recogni-
tion, and information fusion. Corresponding author of this
paper.)
魏 丹 湖南大学电气与信息工程学院
博士研究生. 主要研究方向为图像处理
与模式识别.
E-mail: [e-mail]
(WEI Dan Ph.D. candidate at the
College of Electrical and Information
Engineering, Hunan University. Her re-
search interest covers image processing and pattern recog-
nition.)61 Gehm M E, John R, Brady D J, Willett R M, Schulz T
J. Single-shot compressive spectral imaging with a dual-