壓縮感知和矩陣分解的異同？

01-21

因為work在web這塊，對矩陣分解比較熟悉。這裡指的是協同過濾（collaborative filtering）里常用的矩陣分解（PMF）：
minimize || X-DA ||_F^2 + lambda (||D||_F^2 + ||A||_F^2)
D, A
之前聽過壓縮感知但不了解。發現它和矩陣分解非常像。看到有文章里將它formulate成：
minimize || X-DA ||_F^2 + lambda ||A||_1,1

D, A
問題來了：這個formulation有沒有問題？如果沒有，兩者之間的差別就在於penalty不同嗎？
另外，看到有人把矩陣分解等同於壓縮感知：Compressive Sensing &<—(1)—&> Rank Minimisation &<—(2)—&> Matrix Factorisation。(2) 可以找到證明，但是大致搜了下找不到 (1) 的證明，只有說壓縮感知是某一種Rank Minimisation （correct me if I am wrong）。這裡又有另一個問題：所謂的壓縮感知和矩陣分解等價，僅僅指的是二者都可以表示成 rank minimisation 形式，即使形式不同嗎？

對協同過濾並不了解，補充一點壓縮感知的東西吧。

關於壓縮感知

在CV里，也可以稱作Sparse Coding，就是用一組「基」來得到原來信號的「稀疏表示」。也就是對於信號x，需要尋找一個字典D，使得只需要這個字典D中的幾個「基」，就可以表達原來的信號了。我們需要的是關於信號的這樣一個表述：

這裡的x就是原信號，D是字典，D=(d1,d2,...,dm)，D的列向量dj就是這個線性空間的基，而後面的係數alpha就是信號的稀疏表示。上式可以表示成:

也就是基的線性組合，而這裡的alpha_1到alpha_k，是向量alpha的元素。

最重要的一點：稀疏

我們希望只用少量的「基」就能幾乎完整的恢復原來的信號，也就是只用字典D中幾個列dj來實現信號的重建，因此對這裡的alpha要求是稀疏的，那麼如何描述alpha的稀疏性呢？零範數就可以了。

所以壓縮感知的formulation可以表示如下，加上零範數正則項後:

------以上才是壓縮感知的formulation，正則項是零範數約束------

這個formulation不是凸函數，而且是個NP-hard問題，因此沒法求得全局最優解...

然後壓縮感知從此進入了一個停滯的階段，直到十年前，Elad（具體不太記得是不是他了）把上面的零範數約束放鬆了一點，指定了在矩陣D的自相關性小於一定值的條件下，證明了以下的formulation和壓縮感知原始的formulation可以得到同樣的全局最優解：

這也就是題主關於壓縮感知的的formulation，而且是凸函數。

所以本質上，壓縮感知的formulation是用零範數作為正則項的。旨在得到信號的稀疏表示，因為要使得信號的表示稀疏，所以這裡的字典D是過完備的。補充一下：

將多個信號x堆疊成矩陣就是題主壓縮感知formulation的X了。從某種程度上說，可以將這個求解的過程看做是一種矩陣的低秩分解。

不過現在對於信號或者圖像和圖像塊，已經不太用這種原始的字典D了，一般用svd來做低秩分解，或者將圖像塊堆疊成張量做分解。

UbiComp 不是機器學習的會議。沒經過嚴格證明的就不能說他倆是等價的，雖然長得有點像。

壓縮感知是個很大的toppic，你問的這個我更願意稱之為 sparse coding。強行問兩樣東西的異同沒啥意義，因為是兩個不同的東西。

1. 矩陣填充的目標函數原本是

$min_{Y} |(X-Y)odot Omega|_{F} \ extrm{s.t.} rank(Y) leq alpha$

但是由於有 rank 的約束這個問題不是凸的，於是用 trace norm 來代替，但是還是不好算，於是用 $Y = U*V$ 以及 $min_{U,V} frac{1}{2} ( |U|_F^2 + |V|_F^2 )$ 來代替trace norm。

矩陣分解也是個很大的topic，分解之後形成的矩陣有可能有特殊某些意義。

2. spase coding 是為了從數據中學一組過完備的基來稀疏表示原先的樣本。一般要求基 $D$ 的第i列 $D_i leq 1$ 。它的目標是稀疏表示。

所以矩陣分解和sparse coding的目標並不一樣，是兩個不同的東西，彼此聯繫很少。

壓縮感知的更多情況我不是很清楚，它包含太多內容了。你所寫的第二個式子如果加上D是over-complete的條件，就是一個sparse coding，所以它是壓縮感知的一種情況。因為D over-complete，所以訓練出來的A也不見得是個低秩矩陣，因此至少sparse coding和rank minimization關係不是很大。我個人感覺它確實是一個矩陣分解，變數基於的是高斯分布（Frobenius norm的情況），但是不見得是rank minimization。

至於matrix factorization不同的類型差別也比較大(ver2:, 但是必須要說的是，把矩陣分解成乘積的形式就是矩陣分解啊，所以你說壓縮感知是矩陣分解也算部分正確啊。。)。你所舉例的PMF一般要求矩陣D和A的列數和行數為k&<&---------------------------------------------------------------------------------------------------------------------------------------

&PMF是個沒什麼理論保證的東西，因為它是bi-convex （or seperately convex） but not jointly convex.&

---------------------------------------------------------------------------------------------------------------------------------------

去年focs上有一篇關於理論分析的，在我的認知中基於分解的矩陣填充演算法有保證了。如果把k修改成rank或者min(col(X),row(X))的話，2個fro norm的和就是nuclear(trace) norm。具體細節08年Francis Bach有一篇tech report。這東西也有理論保證，具體看Candes 他們08~12年之間發在SIAM Journal的論文。

另外搞不清楚（1）和（2）分別是哪個式子,按順序來看和按你後面的描述來看感覺不太一樣啊。。。

你要真想搞懂還是老老實實一篇篇看論文吧，把所有式子的條件理清楚你自然就清楚了。

-----------------------------------------------------------------------------------------------------