acosmos的个人博客分享 http://blog.sciencenet.cn/u/acosmos

博文

压缩感知有限等距性质(RIP)之理解

已有 7233 次阅读 2018-9-12 00:57 |个人分类:科研笔记|系统分类:科研笔记


RIP(Restricted Isometry Property, 有限等距性质),这是一个压缩感知绕不开的术语。今天来解释一下什么是RIP。

先定义几个符号:

Φ:称为测量基(Sensing Basis, 也称为观测矩阵

Ψ称为变换基Representation Basis),也称为稀疏矩阵

f:未经过压缩表示的原始信号,fRn

xx =Ψf,称xK稀疏的信号,

y:经过了压缩处理的信号, yRm

A=ΦΨ称为感知矩阵

压缩感知的意思是什么呢?先用一个数学表达式简洁地表示一下:

y =Af =ΦΨf,  m<<n

也就是说,一个原本很不淡定(一点儿也不稀疏)的信号f,在经过感知矩阵A的变换后,可以被表达成很简洁的y

稀疏和不稀疏是什么意思呢,这是针对于信号f的表示而言的。通常对于一个信号,都是要通过某种物理形式或者数学形式来表示的。如果这个信号的表示很复杂、麻烦,需要用到许多数据,就说这个信号的表示是不稀疏的,反之,则可以说这个信号的表示是稀疏的。打比方说,我们都玩过这样一个游戏,猜动物,比如说猜黑猩猩吧,团队成员甲只能通过拐弯抹角的语言来让另一个团队成员乙明白,但却无法直接说出这个动物就是黑猩猩。我们知道和黑猩猩类似的动物还有猴子,猿,狒狒,大猩猩等,因此如何把黑猩猩准确地表达出来就是一个难题。团队德云社拐弯抹角地说了一大推,但苦于生物学没学好,尽管肢体语言表达的很丰富,但黑猩猩就是很难表示出来。而赵忠祥领衔的央视动物世界团队,具有丰富的动物学知识,那么只需要简单地说这个动物属于灵长目人科人亚科人族,与人类染色体的相似程度为98.5%。赵忠祥团队可以很容易地赢得这场游戏。这时,我们就可说黑猩猩f在赵忠祥团队A=ΦΨ下有一个稀疏表示y。为什么把赵忠祥团队表示成ΦΨ呢,这是因为团队是由甲和乙组成的,光是甲具有丰富的动物学知识是不够的,还需要甲可以把黑猩猩的特征从自己掌握的知识中提炼出来(字典和稀疏表示),并且乙也具有同样丰富的动物学知识,可以领悟甲的间接表达(测量感知)。

那么在何种情况下可保证由y可以唯一地恢复出原始信号f呢,这时就要引入RIP的概念了。有关RIP的定义,大家可以搜一下以下几篇文献:

1.   The restricted isometry property and its implications for compressed sensing

2.      Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information

3.      Decoding by linear programming

 

这个不等式来自上面的文献1。尽管上面三篇文献都谈到了RIP,但可以发现定义还是有些不一样的,所以说压缩感知这门技术目前还处于不断发展之中,要想出成果的话,这个矿还是值得继续挖的。

上述三篇文献中有大量的数学证明和公式,可能有人不习惯看大堆的数学符号,那么我来补充一下。RIP(有限等距性质)实际是保证了观测矩阵不会把两个不同的稀疏信号映射到同一个集合中(保证原空间到稀疏空间的唯一对应映射关系)。

我们来回顾一下傅里叶时频域变换对的不相关性和物理学上的不确定性(uncertainty)原理,Φ和Ψ就好比傅里叶时频域变换对,Φ和Ψ越不相关则越适合用来作为压缩感知的测量基和变换基。此外,Φ和Ψ除了不相关性之外,还得有约束关系,这种约束关系是一种若即若离的关系。y=ΦΨfyf其实是同一个事物的不同表示,这就像量子力学不确定性原理中,ΔEΔtħ/2一样。测量基的选取要得满足上面那个不等式,不能小于不等式左边,否则测量出来的值无法恢复原始信号f,但又不能大于等式右边,否则会出现非一一对映的情况,即用一个测量值恢复原始信号,可能会出现2(乃至多个)不同信号都满足要求的情况。


先写到这里,RIP的解释差不多讲完了。休息,休息一会儿。




https://blog.sciencenet.cn/blog-3387120-1134247.html

上一篇:中国式的科研愚蠢
下一篇:也谈道德和规则---读胡适语录有感

0

该博文允许注册用户评论 请点击登录 评论 (2 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2022-7-3 19:30

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部