压缩感知概述

1、LOGO 压缩感知概述压缩感知概述 赵瑞珍赵瑞珍 北京交通大学信息科学研究所北京交通大学信息科学研究所 2011年年7月月5日日 2 目目 录录 简介简介 理论产生背景 研究现状 压缩感知描述 研究内容研究内容 测量矩阵 稀疏重建算法 模拟实现 应用举例 进一步研究方向进一步研究方向 Compressive Sensing 3 1.1 理论产生背景理论产生背景 Compressive Sensing 4 1.1 理论产生背景理论产生背景 Compressive Sensing 5 1.2 研究现状研究现状 2006Robust Uncertainty Principles： Exact Sig

2、nal Reconstruction from Highly Incomplete Frequency Information Terence Tao、Emmanuel Cand s 2006Compressed SensingDavid Donoho 2007Compressive Sensing Richard Baraniuk 上述文章奠定了压缩感知的理论基础。国内也将其翻译成压 缩传感或压缩采样。 Compressive Sensing 6 国际研究现状国际研究现状 理论一经提出，就在信息论、信号处理、图像处 理等领域受到高度关注。 在美国、英国、德国、法国、瑞士、以色列等许 多国家的

3、知名大学(如麻省理工学院、斯坦福大学 、普林斯顿大学、莱斯大学、杜克大学、慕尼黑 工业大学、爱丁堡大学等等)成立了专门的课题组 对CS进行研究。 此外，莱斯大学还建立了专门的Compressive Sensing网站，及时报道和更新该方向的最新研 究成果。 7 国内研究现状国内研究现状 西安电子科技大学石光明教授在电子学报发表综述文 章，系统地阐述了压缩传感的理论框架以及其中涉及到的 关键技术问题。燕山大学练秋生教授的课题组针对压缩感 知的稀疏重建算法进行了系统深入的研究，提出一系列高 质量的图像重建算法。中科院电子所的方广有研究员等， 探索了压缩感知理论在探地雷达三维成像中的应用。 除此之外

4、，还有很多国内学者在压缩感知方面做了重要的 工作，如清华大学、天津大学、国防科技大学、厦门大学 、湖南大学、西南交通大学、南京邮电大学、华南理工大 学、北京理工大学、北京交通大学等等单位，在此不一一 列举。 8 “Compressive Sampling and Frontiers in Signal Processing” “Sparse Representations and High Dimensional Geometry” /cs http:/to- 加州大学洛杉矶分校加州大学洛杉矶分校 美国明尼苏达大学美国明尼苏达大学 杜克大学杜

5、克大学 2007年5月30日到6月1日，加州大学洛杉矶分校开展了关于 “Sparse Representations and High Dimensional Geometry” 的短期讨论班，众多知名学者聚集，讨论压缩感知领域现有 成果和今后的发展方向 2007年6月4日到15日，美国明尼苏达大学举办了主题为 “Compressive sampling and frontiers in signal processing” 讨论班。 2009年2月25日和26日，AFRLATR中心发起的 关于压缩感知的讨论班在Duke在大学举行，本 次讨论班汇集了压缩感知领域的知名学术专家， 集中讨论压缩感

6、知理论、算法及其应用等。 学术交流与资源学术交流与资源 Compressive Sensing 9 重建算法 1.3 压缩感知描述压缩感知描述 Compressive Sensing 10 重建算法 1.3 压缩感知描述压缩感知描述 Compressive Sensing 11 一 简介简介 1.1 理论产生背景 1.2 研究现状 1.3 压缩感知描述 二 研究内容研究内容 2.1 测量矩阵 2.2 稀疏重建算法 2.3 模拟实现 2.4 应用举例 三 进一步研究方向进一步研究方向 Compressive Sensing 12 Compressive Sensing 2.1 测量矩阵测量矩阵

7、13 常用矩阵及特性常用矩阵及特性 Compressive Sensing 10,x)(1xx)(1 2 2 2 2 2 2 RIP特性为充分条件。 限制等距特性（Restricted Isometry Property，RIP） 测量矩阵应满足以下特征： 其列向量满足一定的线性独立性。 其列向量体现某种类似噪声的独立随机性。 14 随机矩阵随机矩阵确定性矩阵确定性矩阵 高斯矩阵轮换矩阵 傅里叶矩阵多项式矩阵 贝努力矩阵哈达吗矩阵 非相关测量矩阵托普利兹矩阵 结构化随机矩阵Chirp测量矩阵 常用矩阵及特性常用矩阵及特性 Compressive Sensing 常用测量矩阵： 随机矩阵重建性能

8、好，但不易于硬件实现。 确定性测量矩阵因为其占用存储空间少，硬件实现容易，是未来测 量矩阵的研究方向，但目前确定性矩阵的重建精度不如随机矩阵。 15 Compressive Sensing 重建算法 2.2 稀疏重建算法稀疏重建算法 16 算法模型算法模型 0 argmin |. .stxxx = y Compressive Sensing x = y 17 求解思路求解思路 直接求解相当困难。以下两种解决方案： 1 不改变目标函数，寻求近似的方法求解 用近似的方法直接求解0范数问题，如贪婪算法等。 2 将目标函数进行转化，变为更容易求解的问题 （1）将0范数问题转化为1范数问题 （2）采用光

9、滑函数逼近0范数，从而将0范数问题转化为光 滑函数的极值问题 Compressive Sensing 18 近似求解方法近似求解方法 Compressive Sensing 正交匹配追踪算法（OMP 算法）的迭代步骤如下： 输入：感知矩阵，测量向量y，误差阈值； 输出：x的稀疏逼近 x ，重建误差r； 初始化：余量 0 ry，重建信号 0 x0，索引集 0 ，迭代次数0n； Step 1：计算余量和感知矩阵的每一列的内积 1nTn g r； Step 2：找出 n g中最大的元素， 1,2,., argmax | n iN ik g ； Step 3：更新索引集 1 nn k 及原子集合 1

10、nn k ； Step 4：利用最小二乘求得近似解 1 () nnn nTT x y； Step 5：更新余量 nn ryx； Step 6： 判断迭代是否满足停止条件 -1 - nn rr， 满足则停止， n xx， n rr， 输出 x ，r；否则转 Step 1。 = 19 转化模型转化模型 1范数比2范数更逼近0范数 1 argmin |. .stxxx = y Compressive Sensing 0 argmin |. .stxxx = y原问题： 转化后： 20 转化模型转化模型 1 min. . n R st x Wxxy 12 111 , | N diag xxx W ,是

11、一 个很小的正数 其中，, Compressive Sensing 另一种转化形式： 21 转化模型转化模型 Compressive Sensing 2 2 2 ( ) i x i xe 0 10 lim( ) 00 i i i x x x 1 ( )( ) N i i x x 0 0 lim( )N xx 引入光滑函数，实现对0范数的逼近： 22 常见的重建算法常见的重建算法 （1）匹配追踪系列： 匹配追踪 （Matching Pursuit, MP） 正交匹配追踪 (Orthogonal Matching Pursuit, OMP) 稀疏自适应匹配追踪 (Sparse Adaptive M

12、P, SAMP) 正则化正交匹配追踪(Regularized OMP, ROMP)等 （2）方向追踪系列： 梯度追踪 (Gradient Pursuit, GP) 共轭梯度追踪 (Conjugate GP,CGP) 近似的共轭梯度追踪 (Approximation CGP, ACGP) 贪婪算法 Compressive Sensing 23 常见的重建算法常见的重建算法 凸优化算法 （1）基追踪法 (Basis Pursuit, BP) （2）最小角度回归法 (Least Angle Regression, LARS) （3）梯度投影法 (Gradient Projection for Spa

13、rse Reconstruction, GPSR) 等。 另类算法 （1） Bayesian类的统计优化算法 （2）基于光滑l0范数最小的SL0算法（Smoothed l0Norm） （3）最小化lp(0p1)范数的迭代聚焦算法(Focal Underdetermined System Solver, FOCUSS) 等。 Compressive Sensing 24 改进方法举例：自适应正则化匹配追踪算法的提出改进方法举例：自适应正则化匹配追踪算法的提出 算法算法特点特点不足不足 OMP单原子选择单原子选择 精确重建精确重建 较长的时间代价较长的时间代价 需已知稀疏度需已知稀疏度 ROMP正

14、则化过程，重建时间正则化过程，重建时间 短，精确重建短，精确重建 需已知稀疏度需已知稀疏度 SAMP自适应过程，无需已知自适应过程，无需已知 稀疏度，精确重建稀疏度，精确重建 时间成本高时间成本高 RAMPRAMP自适应过程，正则化过程，自适应过程，正则化过程， 无需已知稀疏度，运行时间短，精确重建无需已知稀疏度，运行时间短，精确重建 25 实验结果对比实验结果对比 算法名称算法名称 峰值信噪比峰值信噪比 /dB/dB 相对误差相对误差匹配度匹配度 运行时间运行时间 /s/s MP19.550.10530.947218.202 OMP26.490.09080.9548160.433 ROMP2

15、8.180.07470.96267.802 SAMP27.920.07710.961648.22 RAMP28.400.07290.96359.010 不同算法的重建质量对比（不同算法的重建质量对比（） M/N=0.5 26 2.3 模拟实现模拟实现 模拟信号 x(t) 数字信号 y(m) 系数 a(n) 数字信号 x(n) 1 AIC 狭义上的压缩传感过程稀疏重构过程 广义的压缩感知过程广义的压缩感知过程 Compressive Sensing 27 3、模拟实现、模拟实现 实例：单像素相机实例：单像素相机 DMD：digital micromirror device RNG：random

16、number generator Compressive Sensing x = y 28 基于压缩感知的水印加密方法基于压缩感知的水印加密方法 由于感知矩阵的多样性及压缩比的可调节性，有效地提高了 整个加密过程的安全性，在不知道密钥的情况下，水印几乎是 不可提取的，这在实际的版权保护中能有效防止不法分子对水 印的恶意篡改、提取。 X X X X X x (a) 原水印(b) 水印加密后(c) 含水印图像(d) 提取的水印(a) 原水印(b) 水印加密后(c) 含水印图像(d) 提取的水印(a) 原水印(b) 水印加密后(c) 含水印图像(d) 提取的水印 2.4 应用举例应用举例 29 2.

17、4 应用举例应用举例 新方法：新方法：干净小波系数非常稀疏，而含噪小波系数很稠密，然而两 者通过测量矩阵作用后却非常接近，因此在重建过程中通过最小化 非零小波系数的个数对原小波系数进行估计，从而将去噪问题转化 为一个最优化问题。 该方法非常适合于低信噪比信号的去噪。 Compressive Sensing , , , ,| 0, | j kj k j k j k ww w w , , , sign() (|),| 0, | j kj kj k j k j k www w w 小波硬阈值方法 小波软阈值方法 基于稀疏重建的小波去噪基于稀疏重建的小波去噪 30 实验结果实验结果 Compressive Sensing 31 不同去噪方法的信噪比对比 实验结果实验结果 Compressive Sensing 32 一 简介简介 1.1 理论产生背景 1.2 研究现状 1.3 压缩感知描述 二 研究内容研究内容 2.1 测量矩阵 2.2