個(gè)人閱讀筆記

個(gè)人閱讀筆記SparseandRedundantRepresentations最近自己開始閱讀《SparseandRedundantRepresentations：FromTheorytoApplicationsinSignalandImageProcessing》這本書。覺(jué)得應(yīng)該寫點(diǎn)什么，想起了牛人們寫技術(shù)博客，我覺(jué)得可以試一試，不期望能在這能展現(xiàn)精妙的思想，卻為了度量自己的一步又一步。我誠(chéng)不敢草竄，但求在自己現(xiàn)有的水平內(nèi)平鋪直述，不違背原著宗旨地闡述自我理解，一切量力而行?？饲?，儉勉，我愿為此身體力行。下面切入正文，開始我的個(gè)人記錄。在這本書里，開篇章節(jié)便是對(duì)稀疏表示(下面簡(jiǎn)稱SR)的數(shù)學(xué)框架介紹一一欠定方程組(UnderdeterminedEquations)。這是一組未知數(shù)個(gè)數(shù)多于方程個(gè)數(shù)的線性系統(tǒng)。如何求解這個(gè)方程組，是個(gè)非常重要的問(wèn)題也是非常復(fù)雜的問(wèn)題。不過(guò)別急，要熟悉一個(gè)問(wèn)題我覺(jué)得應(yīng)先提綱挈領(lǐng)，然后得條分縷析。舉個(gè)吃貨的心態(tài)：要吃滿漢全席，總得先知道菜譜吧，然后挑著吃，這樣才吃的高雅吃的滿足。否則，從第一道菜饕餐到最后，終究是滿足了口腹的欲望，一切穿腸過(guò)，刺激了自己的植物神經(jīng)系統(tǒng)，絲毫沒(méi)有來(lái)自味覺(jué)美的升華。欠定系統(tǒng)方程組：b=Ax,AeRnxm,n<m (1.1)x是未知數(shù)向量。它的解會(huì)出現(xiàn)兩種情況：要么無(wú)解，要么有許多解(當(dāng)b不能由A的行向量線性表示)。因?yàn)闊o(wú)解對(duì)于系統(tǒng)的功能實(shí)現(xiàn)沒(méi)有意義，所以考慮有解的情況。一定有解(注意是有解，而不是唯一解)，我們這樣假設(shè)。問(wèn)題到這一步，實(shí)際上，并沒(méi)有因?yàn)檫@樣的假設(shè)而簡(jiǎn)化。需要進(jìn)一步考慮的是系統(tǒng)解價(jià)值：是否滿足原系統(tǒng)。還記得小時(shí)候，我們檢查結(jié)果正確與否就是把結(jié)果重新帶入原題(例如是否使得等號(hào)兩邊相等)。同樣的，在這我們也是這樣的思維方式，不過(guò)在SR中，這樣檢驗(yàn)過(guò)程我們稱“重構(gòu)”(reconstruction)。簡(jiǎn)單的數(shù)學(xué)表示：x=A-仍需要特別說(shuō)明的是，這樣的公式是非常特殊的，明顯的可以發(fā)現(xiàn)成立的前提是A可逆。不過(guò)為了說(shuō)明”重構(gòu)”的方式，這樣的表達(dá)只是為了滿足簡(jiǎn)單具體的要求。尤其是對(duì)于我本人，一個(gè)初學(xué)者而言。好了，上面的羅嗦到此結(jié)束?，F(xiàn)在我們可以具體的提出問(wèn)題：眾多解中，我們?cè)撊绾握业阶顑?yōu)解，即能產(chǎn)生最好的闡釋結(jié)果(Clearly,thereareinfinitelymanypossibleimagesxthatmay“explaib”amongwhichtherearesomethatmaylookbetterthanothers.Howcanwefindtheproperx?)。(不急，帶著“榔頭”慢慢敲，因?yàn)榭煲|及到內(nèi)核了人_人)% %對(duì)于多解問(wèn)題，可以引入約束條件(regularization)來(lái)從中選擇我們想要的解。這便是優(yōu)化問(wèn)題。數(shù)學(xué)表達(dá)如下：約束條件函數(shù)：J3)。優(yōu)化問(wèn)題(Pj):minJ(x)subjecttob=Ax (1.2)x(實(shí)際上對(duì)于b=Ax，我們可以看出，要求等號(hào)成立這是非常嚴(yán)格，甚至于苛刻的。等號(hào)意味著0誤差??！)基于上述公式，可以借助Lagrange算子得到這樣的一個(gè)方程：L(x)=J(x)+XT(Ax-b), (1.3)顯然，通過(guò)微分我們能夠得到一個(gè)解(局部最優(yōu)or全局最優(yōu)，現(xiàn)在我還不清楚，不過(guò)大致上的求解框架是確定下來(lái)了，等后面學(xué)習(xí)再回來(lái)思考)。引入的J(x)無(wú)疑對(duì)于求取唯一解有著不可忽視的影響力。每當(dāng)我們借助其他工具來(lái)解決問(wèn)題時(shí)，這一刻新的問(wèn)題出現(xiàn)了。我們的問(wèn)題是在一步步深入，從有解到如何確定唯一解，并且知道了如何去尋找合適的解(唯一解)。引入了J(x)，需要確定的是J(x)。問(wèn)題就這樣產(chǎn)生了:如何選擇合適的J(x)來(lái)實(shí)現(xiàn)呢(adifferent,robust-statisticsbasedchoiceofJ(x))？*作者有提到J(x)=||x|〔2的情況，并指出能夠得到唯一的解(givesthewell-knownclosed-formpseudo-inversesolution，自己不能明白這是什么樣的一個(gè)解，只記住了2范數(shù)可以求解。暫時(shí)這樣吧，自己接下慢慢看)。% %凸規(guī)劃，在這里得熟悉下凸集和凸函數(shù)的概念。這個(gè)都比較簡(jiǎn)單，就不在此贅述。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,這些都是極好理解的高數(shù)知識(shí)。只不過(guò)現(xiàn)在面對(duì)的是向量或矩陣，J(x)的二階導(dǎo)數(shù)此刻被稱為Hessianmatrix。凸規(guī)劃在求解(1.1)中的地位：當(dāng)懲罰項(xiàng)J(x)(penaltyJ(x))是嚴(yán)格凸函數(shù)(注意是嚴(yán)格凸，即上述definitions中是大于號(hào)，而不是大于等于符號(hào)。不是嚴(yán)格凸的話，就不能保證唯一解)且解集x滿足上述的條件，就可以實(shí)現(xiàn)唯一解。這下懂了吧，凸規(guī)劃是為了唯一解！，2范數(shù)就是滿足上述條件的這樣一個(gè)函數(shù)！2范數(shù)是凸函數(shù)！需要補(bǔ)充的是，上述的都不是唯一的：2范數(shù)不是唯一的函數(shù)選擇，凸規(guī)劃也不是唯一的選擇。只是因?yàn)樗麄冊(cè)诰唧w的實(shí)現(xiàn)過(guò)程中，解決起來(lái)更為方便。說(shuō)了這么多，從具體的2范數(shù)到凸規(guī)劃問(wèn)題。都是在討論一個(gè)問(wèn)題：求取唯一解！一一從一個(gè)解集里去挑選出一個(gè)解！可是，有沒(méi)有想過(guò)解集里每一個(gè)元素都可以獨(dú)立的被稱為唯一解，不同的懲罰項(xiàng)J3）產(chǎn)生不同的“唯一解”。在可行域里，我們期望的是全局最優(yōu)的唯一解！% %2范數(shù)，它既然能在一定程度上滿足我們的求解要求，那么范數(shù)系列都是值得我們考慮的。范數(shù)lk||p=￡|x.|p （i.4）i其中對(duì)于p>1,p范數(shù)都是滿足凸函數(shù)的性質(zhì)的。P=1，產(chǎn)生的是1范數(shù)。對(duì)于1范數(shù)，作者為我們做作出了詳細(xì)的分析。值得懷疑的是，1范數(shù)并不是嚴(yán)格凸的，我們?cè)诖嘶A(chǔ)上不一定能得唯一解的。天哪，說(shuō)了這么多怎么又回到多解問(wèn)題是上來(lái)了！作者是如下分析的，并且強(qiáng)調(diào)的說(shuō)：Nevertheless,evenifthereareinfinitelymanypossiblesolutionstothisproblem,wecanclaimthat（i）thesesolutionsaregatheredinasetthatisboundedandconvex,and（ii）amongthesesolutions,thereexistsatleastonewithatmostnnon-zeros（asthenumberofconstraints）.即這些解是處于同一領(lǐng)域里的，其次，解的個(gè)數(shù)不超過(guò)方程組的個(gè)數(shù)（n<m）。基于這樣的兩個(gè)性質(zhì)，我覺(jué)得可以發(fā)現(xiàn)至少能夠感性的理解:稀疏解不是要求我們只要一個(gè)解，即只用A里的某一個(gè)向量來(lái)線性表示輸入信號(hào)（專業(yè)點(diǎn)說(shuō)，就是用測(cè)度矩陣A里的一個(gè)基描述信號(hào)）。要是這樣也太不可能了，除非b就是A里的一個(gè)向量。對(duì)于上述的兩個(gè)性質(zhì)，作者有詳細(xì)的分析過(guò)程，我覺(jué)得不妨礙下面的閱讀，也就不打算過(guò)多的贅述了。言多必失啊~不過(guò)，注意作者的注意力從能獲得唯一解的2范數(shù)轉(zhuǎn)移到了1范數(shù)，這個(gè)能更好的體現(xiàn)稀疏表示特性解的特點(diǎn)的J（x）.% %1范數(shù)既然能夠在求解上表現(xiàn)稀疏表示的特點(diǎn)，那么為了更好的使用它，作者提出了將1范數(shù)轉(zhuǎn)換到線性規(guī)劃里。（具體為什么這么做，作者并沒(méi)有說(shuō)明）線性規(guī)劃后，相對(duì)于原來(lái)的式（1.2）發(fā)生了什么變化。其實(shí)，如果清楚線性規(guī)劃的含義，不難猜測(cè)：目標(biāo)函數(shù)min||x||]變成了線性目標(biāo)函數(shù)。（1范數(shù)情況）。作者假設(shè):x=u—v，u,veRn,u中一部分是x中的所有正數(shù)，剩下的為零。v相反，它是由x中所有負(fù)數(shù)和零組成。那么，經(jīng)過(guò)上述的替換，我們可以得到以下表達(dá)：|x|h=lr（u卜v）=lrzandAx=A（u-v）=[A,-A]z.式（1.2）則為：minItzsubjecttob=[A,-A]zandz>0 （1.5）z但是，這樣的變化只是使得問(wèn)題具有了線性規(guī)劃的架構(gòu)，前后是否等價(jià)還得考究。這點(diǎn)，作者說(shuō)等價(jià)的條件有兩個(gè)：（I）假設(shè)x=u—v，u,veRn必須成立（ii）uTv。0必須滿足（也就是他兩內(nèi)積為零，互相垂直，正交)。(為什么存在這樣的條件，我真不明白，不過(guò)先記住吧，以后就理解了哈~)。作者還提供了通用的X分解方案，很好理解的。,ifweassume>14thenbyreplacingtheselw。entriesbyh；= -vkand*=0wesatisfyboththepositivityandthelinearconstrain(swhilellIsoreducingthepenaltyby—%>0.contradictingtheoptimalityoftheinitialsolution.Thus,thesnpportsofu.vdonotoverlap,andLPisindeedequivalentto(Pi).至于為什么要轉(zhuǎn)換為線性規(guī)劃問(wèn)題，我在目前該書的閱讀里還不太能明白他的意義。也許是比較好實(shí)現(xiàn)吧？暫且記住，以后再解決。% %總結(jié)上述，我們發(fā)現(xiàn)作者從2范數(shù)到能體現(xiàn)稀疏解特點(diǎn)的1范數(shù)，整個(gè)過(guò)程為的是體現(xiàn)稀疏表示特性，發(fā)掘解集里的稀疏性問(wèn)題。換句話說(shuō)，稀疏表示一直是我們的宗旨。為了它，還可以有其它更有價(jià)值的發(fā)現(xiàn)，更何況整個(gè)范數(shù)領(lǐng)域I\4p，只有p=1,2得到了討論。下面P<1也不會(huì)被忽視P的。像前面，我們對(duì)凸集，凸函數(shù)，凸規(guī)劃的定義，并指出1范數(shù)并不具有嚴(yán)格凸性質(zhì)。其實(shí)，想要指出的是P<1已經(jīng)完全脫離了上述的期望，進(jìn)入了非凸領(lǐng)域?？墒且?yàn)樗谙∈杞馇蠼夥矫嫘阅芨茫砸廊恢档迷囈辉?。提個(gè)問(wèn)題：Mp,pv1能為我們帶來(lái)更為稀疏的解么(相對(duì)于1范數(shù))？為了解決這個(gè)問(wèn)題，我P們?cè)撊绾魏饬磕?？其?shí)，我最先想到的是計(jì)算解里面非零元素的個(gè)數(shù)(0范數(shù))，不過(guò)后來(lái)閱讀其他相關(guān)發(fā)現(xiàn)0范數(shù)算法實(shí)施起來(lái)沒(méi)那么容易，甚至是相對(duì)困難的。本書的作者指出采用范數(shù)值等于1。B.—Dethesenormsleadtosparsersolutions?Inordertogeta.feelingforthebehaviorofthesenorms,weconsiderthefollowingproblem:AssumethatxisknowntohaveunitlengthinLetustint!theshortestsuchvectoritiforty<p.Puttingthisasanopiimizatioiiproblem,(hisreads~—n 我們的優(yōu)化問(wè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.這是作者的詳細(xì)分析過(guò)程，一句話概括：就是對(duì)于這樣一對(duì)數(shù)P>q，且IIMIP=1,若采用q范數(shù)P求取最短長(zhǎng)度，我們能實(shí)現(xiàn)更為稀疏的結(jié)果輸出。幾何解釋則表現(xiàn)得更加透徹：對(duì)于||卻1，我們?cè)趍維的坐標(biāo)里可以構(gòu)造一個(gè)重心在原點(diǎn)，半p徑為1的這樣一個(gè)圓(稱為TheunitLp-ball)，作者用了個(gè)很形象的描述”blow”,很有意思哈。同樣的坐標(biāo)系，目標(biāo)函數(shù)min||MF可以被構(gòu)造成一個(gè)二維圖形(anLq“balloon”)，它由大到小的連續(xù)變化。在這樣的變化過(guò)程里，我們需要尋找上述兩個(gè)圖形的交點(diǎn)。交點(diǎn)的坐標(biāo)就說(shuō)明了解的稀疏情況。在簡(jiǎn)單的二維坐標(biāo)里具體的說(shuō)明，左邊的圖為p=2,q=1的情況。標(biāo)記的點(diǎn)的坐標(biāo)里零元素的個(gè)數(shù)，紅色就比黃色的要少。也就是更稀疏些。同理，右圖為p=1,q=0.5也為我們展示了一樣的結(jié)果：最大化q范數(shù)的長(zhǎng)度產(chǎn)生的是非理想稀疏表示(maximizingthe'qlengthleadstothemostnon-sparseoutcome)。上述都是為了說(shuō)明趨向稀疏的一種變化，而不是真正的稀疏結(jié)論，只是為了方便理解!那么回到式(1.2)，只不過(guò)是換個(gè)視角，問(wèn)題框架都是一模一樣的。P:min||x|psubjecttoAx=b (1.6)相對(duì)于上面的問(wèn)題，只是給乂加了個(gè)映射矩陣A，(Thelinearsetofequationsformingtheconstraintdefineafeasiblesetofsolutionsthatareonanaffinesubspace，大概是說(shuō)在一個(gè)仿射子空間上，約束線性方程組定義了一個(gè)可行域。如是這樣的話，那么應(yīng)該是說(shuō)A是一個(gè)坐標(biāo)系，將X通過(guò)A映射輸出b，b的坐標(biāo)是A中的分量?；蛘哒f(shuō)b是X在A上的投影？我自己是這么理解的，暫且如是說(shuō)吧。)

Theintersectionbetweenthe',-ballandthesetAx=bdefinesthesolutionof(Pp).Thisintersectionisdemonstratedherein3Dforp=2(topleft),p=1:5(topright),p=1(bottomleft),andp=0:7(bottomright).Whenp<=1,theintersectiontakesplaceatacorneroftheball,leadingtoasparsesolution.原理和前面是一樣的。需要指出的是他們的共同點(diǎn)：可以觀察圖中的紅色標(biāo)記，這些稀疏點(diǎn)都在軸線上。% %看了這么多，實(shí)際上發(fā)現(xiàn)作者是在引導(dǎo)我們趨向稀疏的方向上靠近，有點(diǎn)像在打太極。上述的有關(guān)范數(shù)的分析討論都具有實(shí)際意義的，至少在我個(gè)人在閱讀其他文獻(xiàn)過(guò)程中，也依然頻繁發(fā)現(xiàn)范數(shù)家族的指導(dǎo)意義。對(duì)于范數(shù)，現(xiàn)在基本上是有了個(gè)小的停頓。其實(shí)作者在很多小節(jié)的末尾都會(huì)用少量的篇幅指出：對(duì)于J()的選擇是多樣的，并不局限于提到的這些。換句話說(shuō)，只要能為我們的稀疏需求提供幫助的都是值得試一試的，盡管會(huì)有這樣或那樣的缺點(diǎn)。比如：J(x)=￡P(guān)(x) (1.7)ii其中，P(x)=1-exp(|x),p(x)=log(1+|x|),p(x)=|x(1+|x|)，他們都是具有單調(diào)非減，單調(diào)非增，對(duì)稱。% %后來(lái)看到這，發(fā)現(xiàn)作者開始提出了0范數(shù)了。0范數(shù)就和前面的范數(shù)成員不太一樣了，它的數(shù)學(xué)表達(dá)如下:m p(1.8)||x|=lim||x||p=limY|x|=#{i:x。0}

0 p—0 ppt0k '(1.8)k=1并且對(duì)于范數(shù)的齊次性和三角不等式性質(zhì)，只滿足后者。對(duì)于最小零范數(shù)問(wèn)題：(P):min|M|