前言：
稀疏肯定是好的，關鍵是怎樣稀疏，要得到什麼樣的稀疏，以及要獲得怎樣的模式 , 說到底還是專家데功勞。
引自于 計算機視覺部落格： 原文連結：http://www.cvchina.info/2010/06/01/sparse-representation-vector-matrix-tensor-1/
稀疏表達：向量、矩陣與張量（上）
2010年6月1日
稀疏表達是近年來SP, ML, PR, CV領域中的一大熱點，文章可謂是普天蓋地，令人目不暇給。老闆某門課程的課程需要大綱，我順道給擴充了下，就有了這個上中下三篇介紹性質的東西。遺憾的是，我在絕大多數情況下實在不算是一個勤快的人，這玩意可能充滿bug，更新也可能斷斷續續，盡請諸位看官見諒了。順道一提，ICCV09有一個相關的
tutorial。
據傳博文裡公式數量和其人氣是成反比例關系的，一個公式可以驅散50%的讀者，我寫完這個（上）之後點了點公式數量，覺得大約是要無人問津了。是以，在介紹稀疏表達之前，讓我們先來展示下其在computer vision中的應用，吸引下眼球。
首先是圖像恢複（以前有人貼過Obama還記得不），由左側圖像恢複出右側結果
然後是類似的圖像inpainting
然後是圖像去模糊，左上為輸入模糊圖像，右下為輸出清晰圖像及估計的相機運動（其實是PSF），中間均為疊代過程:
再然後是物體檢測（自行車），左側輸入圖像，中間為位置機率圖，右側為檢測結果
當然我個人還推薦Yi Ma的sparse face，這個在對抗噪聲的效果上很棒，比如下圖中左側的那張噪聲圖像（你能辨認是哪位不？這方法可以！）
且說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吧）
在進入現代的壓縮感覺、稀疏表示這一課題前，讓我們來首先回顧下這一系列問題的核心，即線性方程組
其中矩陣，通常而言是滿秩的。向量。現在已知，求解。學過線性代數的同學可能都會說：這個不難啊，因為，
故而這個方程組是欠定的，是以有無窮多組解啊，咱還可以算算基礎解系啥的…
但是如果我們希望其解盡可能的稀疏：比如（即中非零元個數）盡可能的小。那麼問題就會變得比較微妙了，下圖給出了問題的形象示意。
換言之給定m維空間中一組過完備的基，如何選擇最少個數的基向量，重構給定向量，其嚴格定義可以寫成
時光之輪播快到2003~2004年，Donoho & Elad做了一個很漂亮的證明，如果矩陣滿足某種條件，具體而言：
那麼上文提及的0範數優化問題具有唯一的解。這裡的是個比較詭異（請允許我使用這詞）的定義：最小的線性相關的列向量集所含的向量個數（吐槽：明白了麼，我做TA的時候就被這個問題問倒了）。本來想在這個概念上唠叨兩句，後來發現了Elad的一個talk，清晰明了。
即便是唯一性得到了證明，求解這個問題仍然是NP難的。科研的車輪滾滾向前，轉眼到了2006年，傳奇性的華裔數學家Terrence Tao登場了，Tao和Donoho的弟子Candes合作證明了在RIP條件下，0範數優化問題與以下1範數優化問題具有相同的解：
其中RIP條件，即存在滿足某種條件的（與N相關）常數:
RIP條件是對于矩陣列向量正交性的一種衡量（此處咱就不細說了）。其實早在1993年Mallat就提出過Mutual Coherence對于正交性進行度量，并提出了下文還要提及的matching pursuit方法。
實際上以上的1範數優化問題是一個凸優化，故而必然有唯一解，至此sparse representation的大坑初步成型。總結一下：
1. 如果矩陣滿足，則0範數優化問題有唯一解。
2. 進一步如果矩陣滿足RIP條件，則0範數優化問題和1範數優化問題的解一緻。
3. 1範數優化問題是凸優化，故其唯一解即為0範數優化問題的唯一解。
進一步可以考慮含噪聲情況，即
可以得到相似的結果，有興趣的同學可以查閱相關文獻。理論坑隻有大牛能挖，但一般人也能挖挖這個優化算法啊，于是SP、ML、CV鄰域裡都有做這個優化算法的，這個出招可就真是五花八門了。據我所知，大緻可以分為三大流派：
1. 直接優化
一般的方法是greedy algorithm，代表有Matching Pursuit, Orthogonal Matching Pursuit
2. 優化
還記得上面提到的LASSO麼，這就是它的模型。
3. 如果已知拉格朗日乘子，優化無限制凸優化問題
解這個的方法現在基本上soft thresholding的方法一統天下，常見的有coordinate descent, Bregman Iteration (又是Osher)等
4. 如果未知拉格朗日乘子，優化
這類方法又叫Homotopy，可以認為是3的擴充。核心出發點是objective function是的分段線性函數。
除此之外，還有利用p範數逐次逼近0範數的方法等等，此處不再贅述。順道說一句，稀疏表示在不同的領域連名稱都不同，搞信号的管這個叫basis pursuit，搞統計的叫l1 regularization….然後，讓我們把話題拉回到Nature的那篇文章：如果我們不知道矩陣，隻知道一堆向量。我們應當如何構造，使得在這一字典（矩陣）下的表示最稀疏？類比以上過程，這個問題被稱為Dictionary
Learning，可以寫成以下優化問題：
這個東西可就相對麻煩了，最關鍵的是這個優化不是凸的（優化變量相乘）。是以一般的想法是block descent：首先固定，優化（相當于多個獨立的1範數優化問題）；其次将計算出的固定，優化，這就是一個（可能帶限制）的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）之後…..
稀疏表達：向量、矩陣與張量（中）
2010年7月13日happyharry發表評論閱讀評論
在開始正文之前，咱首先得說明一下，這篇東西偏向于理論，各位看官可以自行跳過某些部分。這方面的工作創始者同樣也是compressive sensing的大牛之一E.J Candes（Donoho的得意門生），以及Candes的學生Ben
Recht，前者剛從caltech被挖到stanford，後者目前剛到wisconsin做AP。Candes大牛，stanford統計系出生，師從Donoho。Candes原來的主要工作集中在小波分析上（實際上C牛非常多産），比如著名的curvelets以及ridgelets，04年左右開始和Tao合作從事compressive
sensing的理論工作，這裡有他的簡要介紹。
繼續唠叨，上回說到借着collaborative filtering的東風，矩陣的稀疏表示受到了廣泛的關注。說到矩陣的稀疏性，大部分看官可能有所誤解。這個矩陣稀疏表示嚴格而言可以分為兩種：
1. 矩陣元素的稀疏性，即矩陣非0元個數相對較少。參照向量的範數，同樣可以定義矩陣的0範數，并将其松弛到矩陣的1範數的優化問題。
2. 矩陣奇異值的稀疏性，即矩陣奇異值中非0元的個數（即矩陣的秩）相對較少。仿照向量情況下0範數與1範數的關系，同樣可以将其松弛的到迹範數（trace norm）的優化問題。
咱下面會分别聊聊這兩個問題。首先，咱的出發點是machine learning中的collaborative filtering，這個概念并不是啥新東西了，最早大約可以追朔到1992的某篇同名文章。這玩意是做啥的呢，通俗的說，每次你在淘寶上閑逛的時候，下面都會有一行推薦商品。這些個網絡服務商（淘寶，Amazon,
Ebay）就在想了，如果這個推薦系統做的足夠好，那麼消費者（比如你我）的購物欲望就會得到刺激，這個銷量也就上去了。實際上，這和超市裡玲琅滿目的貨架是一個道理。
這裡就得提提Netflix Prize這件事了，話說netflix是家線上dvd租賃公司，這公司就抱了同樣的想法。不過這家公司想了個主意：該公司提供資料，出資100萬美刀，獎勵研發這個推薦系統算法的小組，并要求這些算法發表在學術會議或期刊之上。這可以算是現實版的百萬富翁了（學術和money兩不誤），于是collaborative
filtering着實火了一把（比如SIGKDD上的不少文章）。最終曆時兩年，由AT&T實驗室成員組成的BellKor’s Pragmatic Chaos赢得了這100萬刀。順到一提，國内也有不少家夥參與了這個Prize，比如排名第二的Ensemble組裡就能看到中科院某所學生的身影。
這個推薦系統咋做呢？我們先從簡單的模型開始。以netflix為例，netflix有個影評系統，在你租完DVD以後會讓你打分（1-5分）。當然不是所有人都會認真去打，實際上隻有少數家夥會給打分（這世界上懶人何其之多）。同樣，對每個使用者而言，他也隻可能給部分看過的DVD打分。假設現在有個使用者和部電影，如果把所有評分列成一張大表，可以得到矩陣。其中，每一行對應一個使用者的評分，每一列對應一部電影的使用者評價。可以想象，這個矩陣中隻有少部分元素是已知的（圖1）。
從現有的使用者資料，來預測未知的使用者資料，這就是collaborative filtering了。那麼這個東西怎麼實作呢？解釋起來難，做起來容易，這個模型放在在topic model裡叫做Probabilistic
latent semantic analysis （PLSA）（潛語義分析），放在代數裡叫做矩陣分解（Matrix Fatorization）或者矩陣填充（Matrix Completion），這裡就隻能形象的解釋下。雖然使用者千奇百怪、電影成千上萬，但總可以歸結為若幹類型：比如有腐女向、宅男向電影之分，再比如有悲劇也有喜劇。如果把這些latent factor畫成一個空間，那麼不同的使用者群體應當位于這個latent factor空間的不同位置，展現了不同使用者的喜好。如果可以把使用者喜好連同潛在的latent
factor一同計算出來，預測也自然水到渠成了。從某種角度來看，奇異值分解過程也就是上述的剝離latent factor和使用者喜好的過程，這其中的philosophy可以參見這篇文章。
咱首先要談的是矩陣奇異值的稀疏性，為此先來回憶下奇異值分解。
1. 奇異值非負，即
2. 奇異值非0元的個數即為矩陣的秩（rank）
如果把奇異值寫成對角矩陣的形式（比如SVD分解的标準形式），其對角元為。進一步，矩陣的迹範數（trace
norm）定義為矩陣奇異值之和，即有
現在我們可以把collaborative filtering的基本問題回顧一下，給定一張推薦資料表，已知其下标子集中的元素（也就是有評分的部分），如何恢複這個矩陣？這就是matrix
completion的問題了…
乍眼一看，這基本就是mission impossible了，即使隻有一個元素未知，這個矩陣也不可能唯一。但是如果我們加一些限制條件，這個問題就變得有趣起來了。Candes考慮的是這麼一個問題：
其中表示在子集上的投影（即隻取子集上的對應元素）。實際上，同樣的問題可以有不同的表達形式，如果把這個優化問題稍作調整，可以得到相對容易解釋的模型：
其中Frobenius範數也就是矩陣的2範數。從這個式子來看，我們希望找到這麼一個矩陣，使得其在已有的資料上和使用者評分盡可能的一緻（2範數意義下），同時具有比較低的秩（受到上限的限制）。這裡對于秩的限制，很多時候是為了降低模型自身的複雜度（比如collaborative
filtering，multiple instance learning）。當然，這裡也可以看成是一個fidelity term + regulariztion term的經典形式。
實際上矩陣的rank是一個不那麼友好的函數，rank自身是非凸、不連續的，最後的結果就是對于rank的優化問題是NP難的。類比0範數與1範數的關系，矩陣的秩（rank）相當于這個對角陣的0範數；矩陣的迹範數（trace
norm）相當于這個對角矩陣的1範數。為此，如果這個對角矩陣足夠稀疏，即矩陣的秩，那麼可參照向量的稀疏表示，利用矩陣的迹範數(trace
norm)代替矩陣的秩（rank）。
同樣，由于迹範數(trace norm)是凸的，上式是一個凸優化問題，故而必有唯一的最優解。如果這種近似是可以接受的，那麼這個問題自然也就解決了。
這種近似靠譜麼？這就是Candes和Recht回答的關鍵問題。Candes從random orthogonal model出發，證明了在此假設下從某個秩為的真實矩陣中均勻抽取個元素，且滿足(這裡不妨設，反之隻需要轉置即可)
則凸優化問題的唯一最優解至少以機率逼近原始矩陣，即有
其中均為某常數。更進一步，如果矩陣的秩足夠小，對于元素數量的要求會進一步降低。
咱來聊聊這個結果，這說明在random orthogonal model假設成立的條件下，如果相對于比較小，那麼隻需要知道這個矩陣中約個元素，就可以很高的機率恢複出這個矩陣。舉例而言，如果我們有一個秩為10的矩陣，那我們大緻隻需要從中随機抽取約270萬個元素就可以（以很高機率）恢複出原始矩陣了(當然270萬貌似也是一個很大的數，但原始矩陣約含有1700萬個元素…）。實際上，這是一個相對保守的界，Recht在此基礎上還進行了一系列的理論工作。自從出現了這個之後，under
mild condition，大家都把rank直接放成trace norm了…從實用的角度來說，Candes告訴我們用凸優化去近似一個NP問題，可能得到很好的解。從實驗結果來看（代碼見此），這種近似有時候效果一流，但有時候也根本不work（違背了假設條件），故而具體問題還得具體對待。
雖然早在04年NIPS上，就有人提出了類似的優化方法（MMMF），用trace norm代替rank，并且ML領域中也确實有不少類似的工作。但是，Candes的工作解決了根本的理論問題，并為一系列的rank minimization的問題指了一條出路。這裡有一個比較有意思的地方是，MMMF是從構造最大間隔線性分類器的角度出發來考慮matrix
factorization的問題，并且用的是low norm，但和matrix completion的模型本質上是差不多的，兩者關系大家可以自行推導下。
咱接着要讨論的是矩陣元素的稀疏性，這個工作也和Candes有着很大的關系。咱先把上面的公式照着copy一遍：
如果咱已知矩陣的全部元素，這個東西類似很常見的PCA了：
這樣問題就變成了去噪+降維。進一步把F範數（2範數）改寫為0範數：
為啥是0範數呢，這是基于這麼一種假設：誤差相對于總體樣本而言總是稀疏的。于是，我們可以引入輔助變量表示誤差，并把上式稍作改寫：
這裡的用于平衡矩陣的秩和誤差的稀疏性。同樣，rank和0範數什麼的都是相當讨厭的東西，于是咱松弛一下，就有
這就是Robust Principle Component Analysis (RPCA) 或者Principle Component Pursuit 的核心模型了。這幅圖很好的說明了RPCA和PCA的差別（轉自Yi Ma首頁）。
| PCA | RPCA |
說起RPCA，這裡岔開兩句，這個東西原來是Yi Ma的學生John Wright發在NIPS09上的一篇文章。結果接收之後，被Candes指出了一個bug（審稿人沒看出來），于是Candes對這個問題進行了考慮，進而就有了一篇叫做《Robust
Principal Component Analysis?》的文章（preprint）。Candes證明了在同matrix completion基本相同的假設下，這種近似以很高的機率恢複精确結果（詳細結果可見RPCA的論文）。特别的，此時可以簡單選擇參數。Matrix
Completion（MC）和 RPCA在Yi Ma的首頁上有一個簡單的介紹，上面列舉了相關文獻與代碼的連結。
MC和RPCA在computer vision上有啥用呢？John Wright在NIPS的文章裡做了兩個實驗：背景模組化，人臉陰影去除。大家有興趣可以查查cvpr 10的paper, 有用MC來做video denoising的，有用RPCA來做人臉對齊的…還有那篇best paper也是緊密相關。咱本來還想聊聊這些模型的優化算法，鑒于篇幅所限，就隻能留到（下）篇去了。
最後，下期預告：優化方法，模型變種，張量推廣…其實最關鍵的老天保佑咱有時間寫….