转化模型
另一种转化形式：
min Wx s.t.Φx y
xRn
1
其中，W diag{ 1 , 1 , , 1 } , 是一
| x1 | | x2 |
| xN |
个很小的正数
20
Compressive Sensing
转化模型
引入光滑函数，实现对0范数的逼近：
( xi
)
e
xi2 2 2
1
lim
新方法：干净小波系数非常稀疏，而含噪小波系数很稠密，然而两 者通过测量矩阵作用后却非常接近，因此在重建过程中通过最小化 非零小波系数的个数对原小波系数进行估计，从而将去噪问题转化 为一个最优化问题。 该方法非常适合于低信噪比信号的去噪。
29
Compressive Sensing
实验结果
30
Compressive Sensing
运行时间 /s
18.202 160.433
7.802 48.22 9.010
25
2.3 模拟实现
广义的压缩感知过程
模拟信号 AIC 数字信号
系数
x(t)
y(m)
a(n)
1
数字信号
x(n)
狭义上的压缩传感过程
稀疏重构过程
26
Compressive Sensing
实例：单像素相机
3、模拟实现
Φx = y
常用矩阵及特性
限制等距特性（Restricted Isometry Property，RIP）
(1 δ) x 2 Φx 2 (1 δ) x 2 , 0 δ 1
2
2
2
RIP特性为充分条件。
测量矩阵应满足以下特征：
其列向量满足一定的线性独立性。 其列向量体现某种类似噪声的独立随机性。
13
Compressive Sensing
在美国、英国、德国、法国、瑞士、以色列等许 多国家的知名大学(如麻省理工学院、斯坦福大学 、普林斯顿大学、莱斯大学、杜克大学、慕尼黑 工业大学、爱丁堡大学等等)成立了专门的课题组 对CS进行研究。
此外，莱斯大学还建立了专门的Compressive Sensing网站，及时报道和更新该方向的最新研 究成果。
除此之外，还有很多国内学者在压缩感知方面做了重要的 工作，如清华大学、天津大学、国防科技大学、厦门大学 、湖南大学、西南交通大学、南京邮电大学、华南理工大 学、北京理工大学、北京交通大学等等单位，在此不一一 列举。
7
学术交流与资源
“Sparse Representations and High Dimensional Geometry”
压缩感知概述
赵瑞珍
北京交通大学信息科学研究所 2011年7月5日
LOGO
目录
简介
◇理论产生背景 ◇研究现状 ◇压缩感知描述
研究内容
◇测量矩阵 ◇稀疏重建算法 ◇模拟实现 ◇应用举例
进一步研究方向
2
Compressive Sensing
1.1 理论产生背景
3
Compressive Sensing
另类算法
（1） Bayesian类的统计优化算法 （2）基于光滑l0范数最小的SL0算法（Smoothed l0 Norm） （3）最小化lp(0<p<1)范数的迭代聚焦算法(Focal Underdetermined System
Solver, FOCUSS) 等。
23
Compressive Sensing
10
Compressive Sensing
一 简介
1.1 理论产生背景 1.2 研究现状 1.3 压缩感知描述
二 研究内容
2.1 测量矩阵 2.2 稀疏重建算法 2.3 模拟实现 2.4 应用举例
三 进一步研究方向
11
Compressive Sensing
2.1 测量矩阵
12
Compressive Sensing
1.1 理论产生背景
4
Compressive Sensing
1.2 研究现状
2006《Robust Uncertainty Principles： Exact Signal Reconstruction from
Highly Incomplete Frequency Information》
Terence Tao、Emmanuel Candès
┇
14
Compressive Sensing
2.2 稀疏重建算法
重建算法
15
Compressive Sensing
算法模型
Φx = y
x arg min || x ||0 s.t. Φx = y
16
Compressive Sensing
求解思路
直接求解相当困难。以下两种解决方案：
1 不改变目标函数，寻求近似的方法求解 用近似的方法直接求解0范数问题，如贪婪算法等。
0
(
xi
)
0
xi 0 xi 0
N
(x) (xi )
i 1
x 0 N lim0 (x)
21
Compressive Sensing
常见的重建算法
贪婪算法
（1）匹配追踪系列： 匹配追踪 （Matching Pursuit, MP） 正交匹配追踪 (Orthogonal Matching Pursuit, OMP) 稀疏自适应匹配追踪 (Sparse Adaptive MP, SAMP) 正则化正交匹配追踪(Regularized OMP, ROMP)等
i{1,2, ..., N }
Θ = ΦΨ
Step 3：更新索引集 n n1 { k}及原子集合 Φn Φn1 {φk}；
Step 4：利用最小二乘求得近似解 xn (ΦTnΦn )1ΦTn y ； Step 5：更新余量 rn y Φxn ；
Step 6：判断迭代是否满足停止条件 rn - rn-1 ，满足则停止，xˆ xn ，r rn ，
输出 xˆ ， r ；否则转 Step 1。
18
Compressive Sensing
转化模型
原问题：x arg min || x ||0 s.t. Φx = y 转化后：x arg min || x ||1 s.t. Φx = y
1范数比2范数更逼近0范数
19
Compressive Sensing
目前，压缩感知理论仍处于发展阶段，有很多关键问题尚待解 决，如: （1）探索测量矩阵的必要条件，构造确定性矩阵； （2）如何硬件实现压缩感知的过程； （3）提高现有重建算法恢复质量、速度，论证算法理论基础，保 证其收敛，增强鲁棒性； （4）设计不同环境下的重建算法； （5）设计移动压缩传感器等。
33
http://to-c次集s.b讨中lo论讨g.s班论讨oh汇压论u.集缩c班o了 感m。/压知en缩理try感论//知、领算域法的及知其名应学用术等专。家，
杜克大学
8
Compressive Sensing
1.3 压缩感知描述
重建算法
9
Compressive Sensing
1.3 压缩感知描述
重建算法
6
国内研究现状
西安电子科技大学石光明教授在《电子学报》发表综述文 章，系统地阐述了压缩传感的理论框架以及其中涉及到的 关键技术问题。燕山大学练秋生教授的课题组针对压缩感 知的稀疏重建算法进行了系统深入的研究，提出一系列高 质量的图像重建算法。中科院电子所的方广有研究员等， 探索了压缩感知理论在探地雷达三维成像中的应用。
DMD：digital micromirror device RNG：random number generator
27
Compressive Sensing
2.4 应用举例
基于压缩感知的水印加密方法
由于感知矩阵的多样性及压缩比的可调节性，有效地提高了 整个加密过程的安全性，在不知道密钥的情况下，水印几乎是 不可提取的，这在实际的版权保护中能有效防止不法分子对水 印的恶意篡改、提取。
实验结果
不同去噪方法的信噪比对比
31
Compressive Sensing
一 简介
1.1 理论产生背景 1.2 研究现状 1.3 压缩感知描述
二 研究内容
2.1 测量矩阵 2.2 稀疏重建算法 2.3 模拟实现 2.4 应用举例
三 进一步研究方向
32
Compressive Sensing
进一步研究方向
改进方法举例：自适应正则化匹配追踪算法的提出
算法 OMP
特点 单原子选择
精确重建
ROMP 正则化过程，重建时间 短，精确重建
SAMP 自适应过程，无需已知 稀疏度，精确重建
不足 较长的时间代价
需已知稀疏度 需已知稀疏度
时间成本高
RAMP
自适应过程，正则化过程， 无需已知稀疏，运行时间短，精确重建
输出： x 的稀疏逼近 xˆ ，重建误差 r ；
初始化：余量 r0 y ，重建信号 x0 0 ，索引集 0 ，迭代次数 n 0 ；
Step 1：计算余量和感知矩阵 Φ 的每一列的内积 gn ΦTrn1；
Step 2：找出 gn 中最大的元素， k arg max | gn[i] | ；
Compressive Sensing
北京交通大学信息科学研究所
LOGO
2006《Compressed Sensing》David Donoho
2007《Compressive Sensing》
Richard Baraniuk
上述文章奠定了压缩感知的理论基础。国内也将其翻译成压 缩传感或压缩采样。
5
Compressive Sensing
