在開始正文之前，咱首先得說明一下，這篇東西偏向于理論，各位看官可以自行跳過某些部分。這方面的工作奠基人同樣也是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也是緊密相關。咱本來還想聊聊這些模型的優化算法，鑒于篇幅所限，就只能留到（下）篇去了。

總結

以上是生活随笔為你收集整理的稀疏表达：向量、矩阵与张量（中）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。