压缩传感介绍

1、 压缩传感原理 （compressive sening）创始人：n华裔数学家陶哲轩（Terence Tao） n斯坦福大学统计学家 ：David L. Donoho理论性的文献(1)：n“Robust uncertainty principles:exact signal reconsttruction from highly incomplete frequency information” IEEE Trans. on infromation theory Vol.52 No.2 2006 489509 理论性的文献(2)：n“compressed sinsing” IEEE Trans.

2、 on infromation theory Vol.52 No.4 2006 12891306 n矩阵分析n统计概率论n优化与运筹学n泛函分析与变分问题n时频分析（傅里叶变换、小波变换、方向性小波变换、框架小波）n信号处理与图像处理。研究、学习的基础：基本思路：n传统思路正交变换的应用 变换的能量集中特性与压缩：但能量的分布可变。变换后的总能量不变，变换后的能量：）。是正交变换（正交矩阵其中：或XXXAAXAXAXYYAXYXTTTTA)()()(EAYTY愈小。布愈集中，压缩的误差所以，变换后的能量分则压缩后的均方误差为，取，小顺序排列：的分量按其绝对值的大个时，我们将个分量压缩为当我们需

3、要将 NkiikyyyyYyyyyYYkN)(N10, 022110N210最优的正交变换：nK-L变换 它以输入图像的特征向量为变换核矩阵。因而变换核矩阵随输入图像而变化。应用于信号重建：n变换后只保留K个分量。能否重建（恢复）信号？重建条件：1. N-K个分量为零。2. N-K个分量对信号的贡献微乎其微。K “稀疏”信号或可压缩信号问题：什么信号是K稀疏的？信号在什么变换下是K稀疏的？ 信号（图像）本身可能是稀疏的； 信号（图像）在变换域是稀疏的； 信号（图像）中含有内部的相关性、规律性，当用某个数学模型描述时，只需要少量的模型系数； 信号（图像）的规则性：良好的图像具有卡通模式，噪声和干

4、扰较少,意味着具有变差稀疏性或总变差有限性 。各种形态的稀疏性：新的思路：n压缩传感A Big Idea1,NM NxRMyxR 对于信号有个线性测量怎样由y重构信号x？压缩采样： 采样是一个线性泛函作用于信号，不限于获采样是一个线性泛函作用于信号，不限于获得信号的一个瞬时电平。得信号的一个瞬时电平。 例： 信号 x Rn，将信号与随意选取的 m 个向量 vi 作内积（滤波），m n, 输出结果 y。 这种采样可以用一个 mn 代数方程描述： x = y 。 在一般情况下，重建 x 有无穷多解。 问题的数学表述：（P0）H0min,xxy且满足或H02minyxx 范数的选择：n最优化问题的分

5、析0min,x （空间的最小等值面）H xy ，（空间超平面）求两个空间面的交点求两个空间面的交点范数的选择： 在什么范数下，两个空间面相交在什么范数下，两个空间面相交的可能性最大？的可能性最大？问题的数学表述改为：（P1）H12min yxx或H1min,xxy且满足问题等价的条件问题等价的条件 : : 受限等量性质Restricted Isometry Property of Oder k (RIP) E.J. Candes, et al., 2006 定义： 假定k m 是一个整数，一个矩阵 Rmn的等量常数k 是指对所有k 稀疏向量 x Rn，满足以下不等式的最小值： (1 - k )

6、| x |l22 |x |l22 (1 - k )| x |l22 大致地说，大致地说，RIP 是要求是要求 的每个的每个 mk 子矩阵子矩阵 Sk 是近似单位正交的，即任何一个是近似单位正交的，即任何一个 SkTSk 的各个特征值不要偏离数值的各个特征值不要偏离数值 1 太远。太远。 充分条件充分条件（Candes，2006）：如果 2k 2 1, 那么对于所有 k 稀疏向量 x，（P1）问题的解等于（P0）问题的解。有噪情况有噪情况：（Candes, 2005） 去噪问题 （P1) min |x|1 : | x y |2 ，x Rn ， 设 给定，且 y x e，| e |2 . 如果2k

7、 2 1，则 | x* - x |2 C0k -1/2k(x)1 + C1,其中 x* 是 （P1）的解，而k(x)1 min z Xk | x z |1 , Xk 是全体 k 稀疏向量集合，C0 和 C1 是两个小数值常数。这个结果表明：解的误差与观测误差在同样的数量等级上解的误差与观测误差在同样的数量等级上 （稳定性）。一个有趣的例子：研究的主要方向：n理论依据 目前的主要工作n最优化算法 正交匹配跟踪算法 随机投影算法n应用问题的压缩传感表述 压缩传感雷达。n实际应用的处理方法2009年的一次国际会议征文：nCS算法。n适合于有噪声、非稀疏信号、非线性测量的CS方法。nCS的数学理论n多

8、信号或带附加信息的CS方法。n模拟信号的CS方法。n压缩测量的信号处理n非自适应信号压缩nCS系统的硬件实现nCS的应用随机投影算法n “Random Projections Imaging With Extended Space-Bandwidth Product” By Adrian Stern and Bahram Javidi JOURNAL OF DISPLAY TECHNOLOGY, VOL. 3, NO. 3, SEPTEMBER 2007 随机投影算法系统示意图压缩传感雷达n“Compressed sening ladar”，ICASSP 2008，15091512在高斯白噪声

9、下的成像比较 （15dB）1、如何更准确地估计解的如何更准确地估计解的 k k- -稀疏性和需要的最小量稀疏性和需要的最小量测数测数 m m ？2 2、如何构造观测矩阵（或称词典矩阵）、如何构造观测矩阵（或称词典矩阵） ？使用随？使用随机数构造观测矩阵已证明可行，一定条件下能保证机数构造观测矩阵已证明可行，一定条件下能保证IP IP 条件。条件。 是否存在通用和对重建计算最有效的构造方法？是否存在通用和对重建计算最有效的构造方法？ 仍然在发展中的问题：仍然在发展中的问题：3 3、如何将压缩感知的概念和方法应用于更广的图像处理、如何将压缩感知的概念和方法应用于更广的图像处理 ？ 1 1）将常规图像估计问题，改造成带稀疏性限制的估计问将常规图像估计问题，改造成带稀疏性限制的估计问题，适合于成像、图像重建、反降晰、去噪、修复、超分辨，题，适合于成像、图像重建、反降晰、去噪、修复、超分辨，以及分割、配准、识别、跟踪、分类等。以及分割、配准、识别、跟踪、分类等。 （需要考虑变换域的稀疏性和变差稀疏性。）（需要考虑变换域的稀疏性和变差稀疏性。） 2 2）压缩感知原理的物理实现技术。压缩感知原理的物理实现技术。 仍然在发展中的问题：仍然在发展中的问题：4 4、如何更有效地处理信号重建中遇到的数学规划、