? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??稀疏表示介紹(中)

?

聲明

主要學(xué)習(xí)資料是 Coursera 上 Duke 大學(xué)的公開課——Image and video processing, by Pro.Guillermo Sapiro?第 9 課。

1. Uniqueness

假設(shè)我們已知字典矩陣 D 和稀疏向量 a， 計(jì)算出一個(gè)信號 x，即 Da = x, x?存在一個(gè)關(guān)于 D 的稀疏表示。反過來現(xiàn)在已知前面的 D 和 x，根據(jù) L0 的優(yōu)化問題，可以歸納為：

?的解是唯一的嗎？

顯然不一定。比如， D 中某些 atoms 恰好相等，或者 column1 = column2 + column3, 以前由 column2 和 column3 現(xiàn)在只用 column1 表示即可。當(dāng)然也有正面的例子，比如 DCT 變換, 基向量完全正交，解是唯一的。這與 D 中 atoms 的不相關(guān)性和數(shù)目?K 有關(guān)。

?

2. Sparse Coding

和上面一樣，現(xiàn)有字典 D 和帶有噪聲的信號 y，進(jìn)行稀疏編碼的問題可以表示的 L0 優(yōu)化問題：

這是一個(gè)組合優(yōu)化問題。假設(shè) alpha 的非零項(xiàng)數(shù)目為 L (sparse Level)， 先令 L = 1, 每一個(gè)列向量嘗試一遍，看看是否又滿足條件的，共有 K 種組合。如果沒有，再令 L = 2, 再次嘗試，共有 K(K-1)/2 中組合。還沒有滿足條件的，則令 L = 3......組合的數(shù)目呈指數(shù)增長，這是一個(gè) NP-hard 的問題。 實(shí)際應(yīng)用中的 K = 1000, L = 10, 要窮盡所有的排列組合大概需要計(jì)算幾百萬年，因此要采用近似算法, 目前主要有 relaxation methods （松弛算法）和 greedy methods（貪婪算法）。

Relaxation Methods - the Basis Pursuit (BP)
我們知道， L0 norm 可以數(shù)出向量中非零 entries 的數(shù)目，具有很好的現(xiàn)實(shí)意義，但是由于它數(shù)學(xué)特性（求導(dǎo)等）極差，非常不適合作為一個(gè)優(yōu)化模型中目標(biāo)函數(shù)。在線性分類器中，你可以把誤分點(diǎn)的數(shù)目作為目標(biāo)函數(shù)，但是沒法優(yōu)化，所以，我們看到的線性分類器的的目標(biāo)函數(shù)一般是 L1 norm（感知器算法）， L2 norm（LMS 算法和最小二乘法）以及最大熵（Logistic Regresson）等，也能達(dá)到比較好的效果。在上一篇博客中，可以看到 L1 是菱形， L2 是球體，L1 具有更好的稀疏性(解更靠近坐標(biāo)軸)，所以我們采用松弛方法將 L0 norm 轉(zhuǎn)換為 L1 norm：

雖然我們把 count number 變成了 count the magnitude， 但是在某些條件下，上式的解與松弛之前的解等價(jià)。上述方法也叫 BP，新定義的問題是一個(gè)凸優(yōu)化問題，解決的方法很多，有 Interior Point methods, Sequential shrinkage for union of ortho-bases, Iterative shrinkage 等。

?

Greedy Methods - Matching Pursuit (MP)
第一步，找到最接近(平行) y 的 atom， 等效與在 alpha 向量上僅取一個(gè)非零項(xiàng)，求出最接近的 atom， 保留下來
第二步，計(jì)算誤差是否滿足要求，如果滿足，算法停止，否則，計(jì)算出殘差信號，和第一步類似，找到最接近殘差向量的 atom， 保留下來
第三步，調(diào)整已選向量alpha?的系數(shù)，使得 D*alpha?最接近 y，重復(fù)第二步 (OMP, Orthogonal Matching Pursuit)

總結(jié)一下解決這個(gè)問題的算法有：

?

3. Dictionary Learning - K-SVD

字典學(xué)習(xí)的一個(gè)假設(shè)是——字典對于一張 good-behaved 的圖像具有稀疏表示。因此，選擇字典的原則就有能夠稀疏地表達(dá)信號。有兩種方法來設(shè)計(jì)字典，一種是從已知的變換基中選擇，或者可以稱為 beyond wavelet （超小波）變換，比如 DCT 實(shí)際上就是一個(gè)稀疏表示（高頻部分系數(shù)趨向于 0），這種方法很通用，但是不能夠 adapted to the signal。第二種方法是字典學(xué)習(xí)，即通過已有的大量圖片數(shù)據(jù)進(jìn)行訓(xùn)練和學(xué)習(xí)。

比如，現(xiàn)在有 P 個(gè)信號（張圖片）要進(jìn)行稀疏表示，如何學(xué)習(xí)一個(gè)字典？

上式字典矩陣 D 和 alpha 組成的稀疏表示 A 矩陣都是可變量，目前有幾種算法解決這個(gè)問題，下面介紹 K-SVD 算法（K-Means的一種變種），idea 非常簡單。假設(shè)現(xiàn)在有原始信號矩陣 X^T, 該矩陣的每一行表示一個(gè)信號或者一張圖片， D 矩陣是字典矩陣，右下方是 sparse coding 矩陣，紅色的點(diǎn)表示非零項(xiàng)：

算法步驟如下：

?

Step 1: Initialize。在 X^T 矩陣中隨機(jī)挑選一些行向量(一些原圖），填滿矩陣 D。（ K-means 隨機(jī)選點(diǎn)初始化)?

Step 2:?Sparse Coding. 用上一小節(jié)的方法（松弛或者貪婪法）進(jìn)行稀疏編碼，Row-by-Row 計(jì)算出稀疏矩陣。

Step 3:?Dictionary Update. 字典以列向量為基，自然要 Column-by-Column 地更新字典。比如現(xiàn)在更新某一列, 下方對應(yīng)的紅點(diǎn)，根據(jù)紅點(diǎn)找到對應(yīng)的信號（圖像），然后除掉其他不相關(guān)的圖像，得到示意圖如下：

上圖中字典的 atom 對四張圖片都有貢獻(xiàn)，我們調(diào)整 atom 的目的是使得這個(gè)貢獻(xiàn)更大，從而使稀疏性表示效果更好。當(dāng)然，一個(gè) atom 只能表示一條直線，三張圖片的信號極有可能不在這條直線上，我們要做的是將中間的誤差降到最小，這其實(shí)就是一個(gè)最小二乘（MSE）的問題。具體做法是將最右下角的矩陣進(jìn)行 SVD 分解(SVD 相關(guān)知識可參考之前我寫的博客)，找出主成分，然后回到 Step2, 迭代。

??

總結(jié)

以上是生活随笔為你收集整理的稀疏表示介绍(中)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。