注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

being23

写给未来的自己

 
 
 

日志

 
 
关于我

真正的坚定,就是找到力量去做自己喜欢的事情,并为之努力,这样才会觉得生活是幸福的。

网易考拉推荐

Sparse Represent Introduction  

2011-08-02 20:53:25|  分类: 资源 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

转载:稀疏表达:向量、矩阵与张量(上)

据传博文里公式数量和其人气是成反比例关系的,一个公式可以驱散50%的读者,我写完这个(上)之后点了点公式数量,觉得大约是要无人问津了。所以,在介绍稀疏表达之前,让我们先来展示下其在computer vision中的应用,吸引下眼球。

且说sparse representation这个概念,早在96-97年的时候就火了一把。最著名的大约要数Nature上的某篇文章,将稀疏性加入least square的regularization,然后得到了具有方向特性图像块(basis)。这样就很好的解释了初级视皮层(V1)的工作机理,即对于线段的方向选择特性。几乎同一时期,著名的LASSO算法也被发表在 J. Royal. Statist. Soc B。Lasso比较好的解决了least square (l2 norm) error + l1 norm regularization的问题。然而,这个时候绝大多数人没有意识到(或者没法解决)这l1 norm和稀疏性之间的联系。其实早在这之前,Osher等人提出的Total Variation (TV)已经包含了l1 norm的概念了,只不过TV原本是连续域上的积分形式。(啥?你不知道Osher…想想Level Set吧)

在进入现代的压缩感知、稀疏表示这一课题前,让我们来首先回顾下这一系列问题的核心,即线性方程组clip_image001[3]
其中矩阵clip_image002[3],通常而言是满秩的。向量clip_image003[3]。现在已知clip_image004[3],求解clip_image005[9]。学过线性代数的同学可能都会说:这个不难啊,因为clip_image006[3], 故而这个方程组是欠定的,所以有无穷多组解啊,咱还可以算算基础解系啥的…

但是如果我们希望其解clip_image005[10]尽可能的稀疏:比如clip_image007[3](即clip_image005[11]中非零元个数)尽可能的小。那么问题就会变得比较微妙了,下图给出了问题的形象示意。
clip_image009[3]
换言之给定m维空间中一组过完备的基clip_image010[3],如何选择最少个数的基向量,重构给定向量clip_image011[3],其严格定义可以写成
clip_image012[3]

时光之轮播快到2003~2004年,Donoho & Elad做了一个很漂亮的证明,如果矩阵clip_image013[15]满足某种条件,具体而言:
clip_image014[3]
那么上文提及的0范数优化问题具有唯一的解。这里的clip_image015[3]是个比较诡异(请允许我使用这词)的定义:最小的线性相关的列向量集所含的向量个数(吐槽:明白了么,我做TA的时候就被这个问题问倒了)。本来想在这个概念上唠叨两句,后来发现了Elad的一个talk,清晰明了。

即便是唯一性得到了证明,求解这个问题仍然是NP难的。科研的车轮滚滚向前,转眼到了2006年,传奇性的华裔数学家Terrence Tao登场了,Tao和Donoho的弟子Candes合作证明了在RIP条件下,0范数优化问题与以下1范数优化问题具有相同的解:
clip_image016[3]
其中RIP条件,即存在满足某种条件的(与N相关)常数:clip_image017[3]
clip_image018[3]
RIP条件是对于矩阵clip_image013[16]列向量正交性的一种衡量(此处咱就不细说了)。其实早在1993年Mallat就提出过Mutual Coherence对于正交性进行度量,并提出了下文还要提及的matching pursuit方法。

实际上以上的1范数优化问题是一个凸优化,故而必然有唯一解,至此sparse representation的大坑初步成型。总结一下:
1. 如果矩阵满足clip_image019[3],则0范数优化问题有唯一解。
2.
进一步如果矩阵clip_image013[17]满足RIP条件,则0范数优化问题和1范数优化问题的解一致。
3. 1
范数优化问题是凸优化,故其唯一解即为0范数优化问题的唯一解。

进一步可以考虑含噪声情况,即
clip_image020[6]
可以得到相似的结果,有兴趣的同学可以查阅相关文献。理论坑只有大牛能挖,但一般人也能挖挖这个优化算法啊,于是SP、ML、CV邻域里都有做这个优化算法的,这个出招可就真是五花八门了。据我所知,大致可以分为三大流派:
1. 直接优化
clip_image020[7]
一般的方法是greedy algorithm,代表有Matching Pursuit, Orthogonal Matching Pursuit
2. 优化
clip_image021[3]
还记得上面提到的LASSO么,这就是它的模型。
3. 如果已知拉格朗日乘子,优化无约束凸优化问题
clip_image022[3]
解这个的方法现在基本上soft thresholding的方法一统天下,常见的有coordinate descent, Bregman Iteration (又是Osher)等
4. 如果未知拉格朗日乘子,优化
clip_image023[3]
这类方法又叫Homotopy,可以认为是3的扩展。核心出发点是objective function是clip_image024[3]的分段线性函数。

除此之外,还有利用p范数逐次逼近0范数的方法等等,此处不再赘述。顺道说一句,稀疏表示在不同的领域连名称都不同,搞信号的管这个叫basis pursuit,搞统计的叫l1 regularization….然后,让我们把话题拉回到Nature的那篇文章:如果我们不知道矩阵clip_image013[18],只知道一堆向量clip_image025[6]。我们应当如何构造clip_image013[19],使得在这一字典(矩阵)下clip_image025[7]的表示最稀疏?类比以上过程,这个问题被称为Dictionary Learning,可以写成以下优化问题:
clip_image026[3]

这个东西可就相对麻烦了,最关键的是这个优化不是凸的(优化变量相乘)。所以一般的想法是block descent:首先固定clip_image027[6],优化clip_image028[6](相当于多个独立的1范数优化问题);其次将计算出的clip_image028[7]固定,优化clip_image027[7],这就是一个(可能带约束)的least square问题。如此反复,直到算法收敛到某个(局部)极小值。实际上解这个问题的方法目前有三种:efficient sparse coding algorithm NIPS 06; K-SVD tsp 06; Online dictionary learning for sparse coding, ICML 09 & JMLR 10。前两种都是batch的方法,后一种是online的,据个人测试最后一种的方法比前两者要快很多很多….下面这个是我利用ICML09的方法从1200张彩色图像中训练出一组过完备基,具有比较好的方向特性。

最后,还记得本文开头的那些demo么?INRIA做了一个sparse representation的matlab工具包SPAMS,虽然不开源,但其效率(大部分时候)是现有公开工具包之冠(底层用了intel的MKL),利用这个工具包,几行简单的matlab代码就可以几乎实现以上提及的所有demo了….大家有兴趣的话,欢迎尝试^_^

下期预告:借着collaborative filter的东风,Candes在08年又挖出了matrix completion的新坑。于是,当向量的1范数推广到矩阵的迹范数(trace norm)之后…..

  评论这张
 
阅读(629)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017