压缩感知介绍PPT

2 压缩感知理论分析
E.Candes等人证明了：信号的稀疏性是CS
的必备条件。
信号是可压缩的或在某个变换域是稀疏的，
这个条件的限制等同于信号带宽对于Nyquist 采样定理的约束。
2 压缩感知理论分析
2.2 压缩感知流程介绍

长度为N的信号 在正交基 上的变换系数是稀疏的； 用一个与基 不相关的观测基 : M N (M N ) 对系数向量进行线性变换，并得到观测向量 Y : M 1 利用优化求解的方法从观测集合中精确或高概率地 重构原始信号 。


1 背景介绍
而现实生活中，随着信息技术的高速发展，信
息量的需求增加，携带信息的信号所占带宽也 越来越大
这就大大考验了数字化社会对信息处理的能力，
包括：数据存储、传输和处理速度，基于 Nyquist采样的理论遭到严峻的考验。
1 背景介绍
一个亟待解决的问题：

能否以远低于Nyquist采样定理要求的采样速率获取 信号，而保证信息不损失，并且可以完全恢复信号？ 即能否将对信号的采样转化为对信息的采样？

1 背景介绍
1.2 压缩感知理论的基本思想

一种新的理论—Compressed Sensing(CS,压缩感知， 亦称压缩传感)。 由Candes、Romberg、Tao和Donoho等人在2004年提 出，2006年才发表文献 基本思想： 1、信号是可压缩的或在某个变换域是稀疏的; 2、就可以用一个与变换基不相关的观测矩阵将变换所 得高维信号投影到一个低维空间上; 3、然后通过求解一个优化问题就可以从这些少量的投 影中以高概率重构出原信号。
压缩感知理论及应用
Compressed Sensing (CS)：Theory and Applications 南京航空航天大学电子工程学院 张 弓
1 背景介绍
1.1 传统采样理论介绍及问题提出
1.2 2.1 2.2 压缩感知理论的基本思想 压缩感知的前提 压缩感知流程介绍 第一步：信号的稀疏表示 第二步：观测矩阵的设计 第三步：信号重构
1、基函数字典下的稀疏表示： 寻找一个正交基使得信号表示的稀疏系数尽可能的少。比较 常用的稀疏基有：高斯矩阵、小波基、正（余）弦基、 Curvelet基等。Candes和Tao经研究发现光滑信号的Fourier 系数、小波系数、有界变差函数的全变差范数、振荡信号的 Gabor 系数及具有不连续边缘的图像信号的Curvelet 系数等 都具有足够的稀疏性,可以通过压缩感知理论恢复信号。 2、超完备库下的稀疏表示： 用超完备的冗余函数库来取代基函数，称之为冗余字典，字 典中的元素被称之为原子，目的是从冗余字典中找到具有最 佳线性组合的K项原子来逼近表示一个信号，称作信号的稀 疏逼近或高度非线性逼近。
3 压缩感知应用
3.4.1 CS与传统的高分辨雷达
CS雷达的三个关键点
（1）发射信号必须是充分不相关的； （2）在CS方法中，不需要使用匹配滤波器； （3）目标场景可以恢复是在假设目标满足稀疏性 约束的条件下。
3 压缩感知应用
3.4.1 CS与传统的高分辨雷达

CS技术很重要的思想是设计一个观测矩阵 ，用来表示 稀疏信号的字典集 ，并且 与 是不相关的。利用这个 思想设计出CS雷达接收机如下图所示。
的线性组合来表示，假定这些基是规范正交的， T 其中 表示矩阵 的转置，那么有
x k k
其中 k x, k ，若 x 在基 上仅有K K N 个非 零系数 k 时，称 为信号 x 的稀疏基， x 是 K稀 疏(K-Sparsity)的。
k 1
N
T
1
s.t.
Y x
T

或者：
min Y T x T x的系数，然后反变换即可以 得到时域信号。
2 压缩感知理论分析
目前出现的重构算法主要可归为三大类：

1)第一类贪婪算法：这类算法是通过每次迭代时选择一个局 部最优解来逐步逼近原始信号，典型的贪婪算法--MP算法， 贪婪算法是针对组合优化提出, 目前已发展了多种变形，例 如，OMP, OOMP, CosMP等。该类重建算法速度快, 然而需 要的测量数据多且精度低。
观测过程就是利用 M N 观测矩阵的 M 个行向量 对稀疏系数向量进行投影，得到 M 个观测值，即
Y x x
T
2 压缩感知理论分析
Y x x
T
2 压缩感知理论分析
观测矩阵要满足什么样的条件呢？

从上式中求出 是一个线性规划问题，但由于方程的个 数少于未知数的个数 M N ，这是一个病态问题
3.1 波形信号仿真分析 3.2 CS图像融合 3.3 单像素CS相机 3.4 CS雷达
3 压缩感知应用
3.1 波形信号仿真分析


基于CS理论的一个简单的信号分析。
信号长度为N=256，稀疏度为K=7，测量数M=32。信号为 三个频率叠加的正弦信号，傅里叶正交变换矩阵作为系数 矩阵，高斯矩阵来测量，并用OMP算法重构原信号。
2)第二类凸优化算法：这类方法是将非凸问题转化为凸问题 求解找到信号的逼近，如BP算法，梯度投影方法等。该类 算法速度慢，然而需要的测量数据少且精度高。 3)第三类组合算法：这类方法要求信号的采样支持通过分组 测试快速重建，如代表性方法Sparse Bayesian。该类方法 位于前两者之间。


3 压缩感知应用
0
s.t.
Y T x
2 压缩感知理论分析

对于0-范数问题的求解是个NP问题，需要列出所有非零项位 置的种组合的线性组合才能得到最优解，在多项式时间内难 以求解，而且也无法验证其可靠性。 Chen，Donoho和Saunders指出求解一个优化问题会产生同 等的解。于是问题转化为：

min x
CS重建信号的手段。
2 压缩感知理论分析
第一步：信号的稀疏表示

x ,在时域x 如图是一个稀疏度为3的稀疏变换， 基本都是非零值，
但将其变换到 域 时，非零值就只有3 个了，数目远小于 原来的非零数目，实 现了信号的稀疏表 示。

2 压缩感知理论分析
如何找到信号的最佳稀疏域呢？

这是压缩感知理论的基础和前提，也是信号精确重构的保证。 对稀疏表示研究的热点主要有两个方面：



2 压缩感知理论分析

超完备库下的稀疏表示涉及到两个问题： 一是如何构造这样一个适合某一类信号的冗余字典； 二是在已知冗余字典的前提下如何设计快速有效的分解方 法来稀疏地表示某一个信号。

右图为一些不 同的字典
2 压缩感知理论分析
第二步：观测矩阵的设计
观测器的目的是采样得到 M 个观测值，并保证从 中能够重构出原来长度为 N 的信号 x 或者稀疏基 下的系数向量 。
3 压缩感知应用
字母R的 实验结果：
3 压缩感知应用
3.4 CS雷达


在雷达目标探测中，目标相对于背景高度稀疏， 与复杂的雷达系统、海量数据呈现极度的不平 衡，这就为CS技术在雷达目标探测与识别的应 用提供了必要的条件。 3.4.1 CS与传统的高分辨雷达 3.4.2 CS与MIMO雷达 3.4.3 CS与雷达成像
2 压缩感知理论分析
第三步：信号重构

首先介绍下范数的概念。向量的p-范数为：
s
p


N i 1
si
p

1
p
当p=0时得到0-范数，它表示上式中非零项的个 数。

由于观测数量M N ，不能直接求解，在信号 x 可压缩的前提下，求解病态方程组的问题转化 为最小0-范数问题：
min T x
混频器 积分器 ADC
r t
pc t 取值1,1
3 压缩感知应用

假设空间有若干个稀疏目标，将目标所在的距离向与方位向 分割成网格形式。CS雷达可以检测的目标数量 K N 2 ， 2 K<<N 为稀疏单元数目。如果 ，则可以采用CS理论，通 K 过优化问题求解，精确分辨出空间的多个目标。
0
-0.5
-1
-1.5 0
50
100
150
200
250
300
3 压缩感知应用
3.2 CS图像融合

图像融合是对来自单一传感器不同时间、不同环境下获取 的图像或由多个传感器同一时间获取的信息进行多级别、 多层次的处理与综合，从而获得更丰富、更精确、更可靠 的有用信息。
图像融合的目的是提高图像显示的质量、实现图像的特征 提取、图像去噪、目标识别和跟踪以及图像的三维重构。 大部分图像的稀疏特性为CS的应用带来可能，同时CS的 引入为图像的融合在计算速度、融合策略上都带来了新的 飞跃。

但如果 x 具有稀疏性，则有可能求出确定解。Candes、 Tao等人提出必须保证观测矩阵不会把两个不同的K 项稀 疏信号映射到同一个采样几何中，这就要求从观测矩阵 中抽取的每个列向量构成的矩阵是非奇异的，
这跟有限等距特性(RIP)条件的要求是一致的。

R.Baraniuk将上述条件简化为如果保证观测矩阵和稀疏 基不相干，则在很大概率上满足RIP性质。不相干是指 j 不能用 i 稀疏表示，不相干性越强，互相表示时所需的 系数越多。
original signal 2 2 recovery
1.5
1.5
1
1
0.5
0.5
0
0
-0.5
-0.5
-1
-1
-1.5 0
50
100
150
200
250
300
-1.5 0