稀疏表达：向量、矩阵与张量

《稀疏表达：向量、矩阵与张量》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、稀疏表达是近年来SP,ML,PR,CV领域中的一大热点，文章可谓是普天盖地，令人目不暇给。老板某门课程的课程需要大纲，我顺道给扩展了下，就有了这个上中下三篇介绍性质的东西。遗憾的是，我在绝大多数情况下实在不算是一个勤快的人，这玩意可能充满bug，更新也可能断断续续，尽请诸位看官见谅了。顺道一提，ICCV09有一个相关的tutorial。据传博文里公式数量和其人气是成反比例关系的，一个公式可以驱散50%的读者，我写完这个（上）之后点了点公式数量，觉得大约是要无人问津了。所以，在介绍稀疏表达之前，让我们先来展示

2、下其在computervision中的应用，吸引下眼球。首先是图像恢复（以前有人贴过Obama还记得不），由左侧图像恢复出右侧结果然后是类似的图像inpainting然后是图像去模糊，左上为输入模糊图像，右下为输出清晰图像及估计的相机运动（其实是PSF），中间均为迭代过程:再然后是物体检测（自行车），左侧输入图像，中间为位置概率图，右侧为检测结果当然我个人还推荐YiMa的sparseface，这个在对抗噪声的效果上很棒，比如下图中左侧的那张噪声图像（你能辨认是哪位不？这方法可以！）且说sparserepre

3、sentation这个概念，早在96-97年的时候就火了一把。最著名的大约要数Nature上的某篇文章，将稀疏性加入leastsquare的regularization，然后得到了具有方向特性图像块（basis）。这样就很好的解释了初级视皮层（V1）的工作机理，即对于线段的方向选择特性。几乎同一时期，著名的LASSO算法也被发表在J.Royal.Statist.SocB。Lasso比较好的解决了leastsquare(l2norm)error+l1normregularization的问题。然而，这个时候绝

4、大多数人没有意识到（或者没法解决）这l1norm和稀疏性之间的联系。其实早在这之前，Osher等人提出的TotalVariation（TV）已经包含了l1norm的概念了，只不过TV原本是连续域上的积分形式。（啥？你不知道Osher…想想LevelSet吧）在进入现代的压缩感知、稀疏表示这一课题前，让我们来首先回顾下这一系列问题的核心，即线性方程组其中矩阵，通常而言是满秩的。向量。现在已知，求解。学过线性代数的同学可能都会说：这个不难啊，因为，故而这个方程组是欠定的，所以有无穷多组解啊，咱还可以算算基础解系

5、啥的…但是如果我们希望其解尽可能的稀疏：比如（即中非零元个数）尽可能的小。那么问题就会变得比较微妙了，下图给出了问题的形象示意。换言之给定m维空间中一组过完备的基，如何选择最少个数的基向量，重构给定向量，其严格定义可以写成时光之轮播快到2003~2004年，Donoho&Elad做了一个很漂亮的证明，如果矩阵满足某种条件，具体而言：那么上文提及的0范数优化问题具有唯一的解。这里的是个比较诡异（请允许我使用这词）的定义：最小的线性相关的列向量集所含的向量个数（吐槽：明白了么，我做TA的时候就被这个问题问倒了）

6、。本来想在这个概念上唠叨两句，后来发现了Elad的一个talk，清晰明了。即便是唯一性得到了证明，求解这个问题仍然是NP难的。科研的车轮滚滚向前，转眼到了2006年，传奇性的华裔数学家TerrenceTao登场了，Tao和Donoho的弟子Candes合作证明了在RIP条件下，0范数优化问题与以下1范数优化问题具有相同的解：其中RIP条件，即存在满足某种条件的（与N相关）常数:RIP条件是对于矩阵列向量正交性的一种衡量（此处咱就不细说了）。其实早在1993年Mallat就提出过MutualCoherence

7、对于正交性进行度量，并提出了下文还要提及的matchingpursuit方法。实际上以上的1范数优化问题是一个凸优化，故而必然有唯一解，至此sparserepresentation的大坑初步成型。总结一下：1.如果矩阵满足，则0范数优化问题有唯一解。2.进一步如果矩阵满足RIP条件，则0范数优化问题和1范数优化问题的解一致。3.1范数优化问题是凸优化，故其唯一解即为0范数优化问题的唯一解。进一步可以考虑含噪声情况，即可以得到相似的结果，有兴趣的同学可以查阅相关文献。理论坑只有大牛能挖，但一般人也能挖挖这个优

8、化算法啊，于是SP、ML、CV邻域里都有做这个优化算法的，这个出招可就真是五花八门了。据我所知，大致可以分为三大流派：1.直接优化一般的方法是greedyalgorithm，代表有MatchingPursuit,OrthogonalMatchingPursuit2.优化还记得上面提到的LASSO么，这就是它的模型。3.如果已知拉格朗日乘子，优化无约束凸优化问题解这个的方法现在基本上softthresholding