个人阅读笔记

个人阅读笔记SparseandRedundantRepresentations最近自己开始阅读《SparseandRedundantRepresentations：FromTheorytoApplicationsinSignalandImageProcessing》这本书。觉得应该写点什么，想起了牛人们写技术博客，我觉得可以试一试，不期望能在这能展现精妙的思想，却为了度量自己的一步又一步。我诚不敢草窜，但求在自己现有的水平内平铺直述，不违背原著宗旨地阐述自我理解，一切量力而行。克勤，俭勉，我愿为此身体力行。下面切入正文，开始我的个人记录。在这本书里，开篇章节便是对稀疏表示(下面简称SR)的数学框架介绍一一欠定方程组(UnderdeterminedEquations)。这是一组未知数个数多于方程个数的线性系统。如何求解这个方程组，是个非常重要的问题也是非常复杂的问题。不过别急，要熟悉一个问题我觉得应先提纲挈领，然后得条分缕析。举个吃货的心态：要吃满汉全席，总得先知道菜谱吧，然后挑着吃，这样才吃的高雅吃的满足。否则，从第一道菜饕餐到最后，终究是满足了口腹的欲望，一切穿肠过，刺激了自己的植物神经系统，丝毫没有来自味觉美的升华。欠定系统方程组：b=Ax,AeRnxm,n<m (1.1)x是未知数向量。它的解会出现两种情况：要么无解，要么有许多解(当b不能由A的行向量线性表示)。因为无解对于系统的功能实现没有意义，所以考虑有解的情况。一定有解(注意是有解，而不是唯一解)，我们这样假设。问题到这一步，实际上，并没有因为这样的假设而简化。需要进一步考虑的是系统解价值：是否满足原系统。还记得小时候，我们检查结果正确与否就是把结果重新带入原题(例如是否使得等号两边相等)。同样的，在这我们也是这样的思维方式，不过在SR中，这样检验过程我们称“重构”(reconstruction)。简单的数学表示：x=A-仍需要特别说明的是，这样的公式是非常特殊的，明显的可以发现成立的前提是A可逆。不过为了说明”重构”的方式，这样的表达只是为了满足简单具体的要求。尤其是对于我本人，一个初学者而言。好了，上面的罗嗦到此结束。现在我们可以具体的提出问题：众多解中，我们该如何找到最优解，即能产生最好的阐释结果(Clearly,thereareinfinitelymanypossibleimagesxthatmay“explaib”amongwhichtherearesomethatmaylookbetterthanothers.Howcanwefindtheproperx?)。(不急，带着“榔头”慢慢敲，因为快要触及到内核了人_人)% %对于多解问题，可以引入约束条件(regularization)来从中选择我们想要的解。这便是优化问题。数学表达如下：约束条件函数：J3)。优化问题(Pj):minJ(x)subjecttob=Ax (1.2)x(实际上对于b=Ax，我们可以看出，要求等号成立这是非常严格，甚至于苛刻的。等号意味着0误差！！)基于上述公式，可以借助Lagrange算子得到这样的一个方程：L(x)=J(x)+XT(Ax-b), (1.3)显然，通过微分我们能够得到一个解(局部最优or全局最优，现在我还不清楚，不过大致上的求解框架是确定下来了，等后面学习再回来思考)。引入的J(x)无疑对于求取唯一解有着不可忽视的影响力。每当我们借助其他工具来解决问题时，这一刻新的问题出现了。我们的问题是在一步步深入，从有解到如何确定唯一解，并且知道了如何去寻找合适的解(唯一解)。引入了J(x)，需要确定的是J(x)。问题就这样产生了:如何选择合适的J(x)来实现呢(adifferent,robust-statisticsbasedchoiceofJ(x))？*作者有提到J(x)=||x|〔2的情况，并指出能够得到唯一的解(givesthewell-knownclosed-formpseudo-inversesolution，自己不能明白这是什么样的一个解，只记住了2范数可以求解。暂时这样吧，自己接下慢慢看)。% %凸规划，在这里得熟悉下凸集和凸函数的概念。这个都比较简单，就不在此赘述。Definitionl.ZAfunctionJ(x):f?—>[RisconvexifVxHX2e痘andWe[0T1].theconvexcombinationpointx=rxi+(I—OxjsatisfiesJ(fXi+(1-Ox；)<f/fX])+(1 (L8)DetinHionI*3,Afunction:HtIRisconvexifWxj柘gQifandonlyifJ(X2)>/(%)+VJ(X|)r(X2-X]), (19)oralternatively,ifandonlyif)ispositive-definite,这些都是极好理解的高数知识。只不过现在面对的是向量或矩阵，J(x)的二阶导数此刻被称为Hessianmatrix。凸规划在求解(1.1)中的地位：当惩罚项J(x)(penaltyJ(x))是严格凸函数(注意是严格凸，即上述definitions中是大于号，而不是大于等于符号。不是严格凸的话，就不能保证唯一解)且解集x满足上述的条件，就可以实现唯一解。这下懂了吧，凸规划是为了唯一解！，2范数就是满足上述条件的这样一个函数！2范数是凸函数！需要补充的是，上述的都不是唯一的：2范数不是唯一的函数选择，凸规划也不是唯一的选择。只是因为他们在具体的实现过程中，解决起来更为方便。说了这么多，从具体的2范数到凸规划问题。都是在讨论一个问题：求取唯一解！一一从一个解集里去挑选出一个解！可是，有没有想过解集里每一个元素都可以独立的被称为唯一解，不同的惩罚项J3）产生不同的“唯一解”。在可行域里，我们期望的是全局最优的唯一解！% %2范数，它既然能在一定程度上满足我们的求解要求，那么范数系列都是值得我们考虑的。范数lk||p=£|x.|p （i.4）i其中对于p>1,p范数都是满足凸函数的性质的。P=1，产生的是1范数。对于1范数，作者为我们做作出了详细的分析。值得怀疑的是，1范数并不是严格凸的，我们在此基础上不一定能得唯一解的。天哪，说了这么多怎么又回到多解问题是上来了！作者是如下分析的，并且强调的说：Nevertheless,evenifthereareinfinitelymanypossiblesolutionstothisproblem,wecanclaimthat（i）thesesolutionsaregatheredinasetthatisboundedandconvex,and（ii）amongthesesolutions,thereexistsatleastonewithatmostnnon-zeros（asthenumberofconstraints）.即这些解是处于同一领域里的，其次，解的个数不超过方程组的个数（n<m）。基于这样的两个性质，我觉得可以发现至少能够感性的理解:稀疏解不是要求我们只要一个解，即只用A里的某一个向量来线性表示输入信号（专业点说，就是用测度矩阵A里的一个基描述信号）。要是这样也太不可能了，除非b就是A里的一个向量。对于上述的两个性质，作者有详细的分析过程，我觉得不妨碍下面的阅读，也就不打算过多的赘述了。言多必失啊~不过，注意作者的注意力从能获得唯一解的2范数转移到了1范数，这个能更好的体现稀疏表示特性解的特点的J（x）.% %1范数既然能够在求解上表现稀疏表示的特点，那么为了更好的使用它，作者提出了将1范数转换到线性规划里。（具体为什么这么做，作者并没有说明）线性规划后，相对于原来的式（1.2）发生了什么变化。其实，如果清楚线性规划的含义，不难猜测：目标函数min||x||]变成了线性目标函数。（1范数情况）。作者假设:x=u—v，u,veRn,u中一部分是x中的所有正数，剩下的为零。v相反，它是由x中所有负数和零组成。那么，经过上述的替换，我们可以得到以下表达：|x|h=lr（u卜v）=lrzandAx=A（u-v）=[A,-A]z.式（1.2）则为：minItzsubjecttob=[A,-A]zandz>0 （1.5）z但是，这样的变化只是使得问题具有了线性规划的架构，前后是否等价还得考究。这点，作者说等价的条件有两个：（I）假设x=u—v，u,veRn必须成立（ii）uTv。0必须满足（也就是他两内积为零，互相垂直，正交)。(为什么存在这样的条件，我真不明白，不过先记住吧，以后就理解了哈~)。作者还提供了通用的X分解方案，很好理解的。,ifweassume>14thenbyreplacingtheselw。entriesbyh；= -vkand*=0wesatisfyboththepositivityandthelinearconstrain(swhilellIsoreducingthepenaltyby—%>0.contradictingtheoptimalityoftheinitialsolution.Thus,thesnpportsofu.vdonotoverlap,andLPisindeedequivalentto(Pi).至于为什么要转换为线性规划问题，我在目前该书的阅读里还不太能明白他的意义。也许是比较好实现吧？暂且记住，以后再解决。% %总结上述，我们发现作者从2范数到能体现稀疏解特点的1范数，整个过程为的是体现稀疏表示特性，发掘解集里的稀疏性问题。换句话说，稀疏表示一直是我们的宗旨。为了它，还可以有其它更有价值的发现，更何况整个范数领域I\4p，只有p=1,2得到了讨论。下面P<1也不会被忽视P的。像前面，我们对凸集，凸函数，凸规划的定义，并指出1范数并不具有严格凸性质。其实，想要指出的是P<1已经完全脱离了上述的期望，进入了非凸领域。可是因为它在稀疏解求解方面性能更好，所以依然值得试一试。提个问题：Mp,pv1能为我们带来更为稀疏的解么(相对于1范数)？为了解决这个问题，我P们该如何衡量呢？其实，我最先想到的是计算解里面非零元素的个数(0范数)，不过后来阅读其他相关发现0范数算法实施起来没那么容易，甚至是相对困难的。本书的作者指出采用范数值等于1。B.—Dethesenormsleadtosparsersolutions?Inordertogeta.feelingforthebehaviorofthesenorms,weconsiderthefollowingproblem:AssumethatxisknowntohaveunitlengthinLetustint!theshortestsuchvectoritiforty<p.Puttingthisasanopiimizatioiiproblem,(hisreads~—n 我们的优化问|z唧Mfg心W—l题 L13)WeshallassumeThatxhasanon-zeros(weshallfurtherassumethatthesevaluesareallpositive,sincetheirsigndoesnotaffecttheanalysistliatfollows)astheleadingentriesinthevector,andtherestarezeros. definetheLagrangianfunctionasE(x)=闻+XIMIJ-1)=T+i . (1.14)k=lThisfiuictionisseparable,hajidlingeveryentryinxindependentlycitheothers.Theoptimalsolutionisgivenbya，*'-Constforallk：implyingthmal[thenonzeroentriesaresupposedtobethesame.TheconstrainL||x||^=Ileadst□一“=。厂"七andthe^-normforthissolutionisgivenby||x||告=a}~qfp.Sinceq<p,thismeansthattheshortestCj-normisobtainedfora=Lhavingonlyonenon-zeroentryinx.这是作者的详细分析过程，一句话概括：就是对于这样一对数P>q，且IIMIP=1,若采用q范数P求取最短长度，我们能实现更为稀疏的结果输出。几何解释则表现得更加透彻：对于||却1，我们在m维的坐标里可以构造一个重心在原点，半p径为1的这样一个圆(称为TheunitLp-ball)，作者用了个很形象的描述”blow”,很有意思哈。同样的坐标系，目标函数min||MF可以被构造成一个二维图形(anLq“balloon”)，它由大到小的连续变化。在这样的变化过程里，我们需要寻找上述两个图形的交点。交点的坐标就说明了解的稀疏情况。在简单的二维坐标里具体的说明，左边的图为p=2,q=1的情况。标记的点的坐标里零元素的个数，红色就比黄色的要少。也就是更稀疏些。同理，右图为p=1,q=0.5也为我们展示了一样的结果：最大化q范数的长度产生的是非理想稀疏表示(maximizingthe'qlengthleadstothemostnon-sparseoutcome)。上述都是为了说明趋向稀疏的一种变化，而不是真正的稀疏结论，只是为了方便理解!那么回到式(1.2)，只不过是换个视角，问题框架都是一模一样的。P:min||x|psubjecttoAx=b (1.6)相对于上面的问题，只是给乂加了个映射矩阵A，(Thelinearsetofequationsformingtheconstraintdefineafeasiblesetofsolutionsthatareonanaffinesubspace，大概是说在一个仿射子空间上，约束线性方程组定义了一个可行域。如是这样的话，那么应该是说A是一个坐标系，将X通过A映射输出b，b的坐标是A中的分量。或者说b是X在A上的投影？我自己是这么理解的，暂且如是说吧。)

Theintersectionbetweenthe',-ballandthesetAx=bdefinesthesolutionof(Pp).Thisintersectionisdemonstratedherein3Dforp=2(topleft),p=1:5(topright),p=1(bottomleft),andp=0:7(bottomright).Whenp<=1,theintersectiontakesplaceatacorneroftheball,leadingtoasparsesolution.原理和前面是一样的。需要指出的是他们的共同点：可以观察图中的红色标记，这些稀疏点都在轴线上。% %看了这么多，实际上发现作者是在引导我们趋向稀疏的方向上靠近，有点像在打太极。上述的有关范数的分析讨论都具有实际意义的，至少在我个人在阅读其他文献过程中，也依然频繁发现范数家族的指导意义。对于范数，现在基本上是有了个小的停顿。其实作者在很多小节的末尾都会用少量的篇幅指出：对于J()的选择是多样的，并不局限于提到的这些。换句话说，只要能为我们的稀疏需求提供帮助的都是值得试一试的，尽管会有这样或那样的缺点。比如：J(x)=£P(x) (1.7)ii其中，P(x)=1-exp(|x),p(x)=log(1+|x|),p(x)=|x(1+|x|)，他们都是具有单调非减，单调非增，对称。% %后来看到这，发现作者开始提出了0范数了。0范数就和前面的范数成员不太一样了，它的数学表达如下:m p(1.8)||x|=lim||x||p=limY|x|=#{i:x。0}

0 p—0 ppt0k '(1.8)k=1并且对于范数的齐次性和三角不等式性质，只满足后者。对于最小零范数问题：(P):min|M|