在本文第一篇的時候我們介紹了 RIP 以及相關的概念，并給出了投影矩陣??滿足一定的 RIP 條件的時候通過?-norm 最小化可以求得 CS 問題的最優解，該問題是通過凸優化來進行求解。這里我們介紹另一類主要算法（Pursuit 類）的一個典型，叫做 Orthogonal Matching Pursuit (OMP)。

介紹算法之前先引入一個叫做 Coherence 的概念，對于一個矩陣?，其 coherence 定義為

其中??表示矩陣的第??列。一個特殊情況是??的列全部正交，此時 coherence 為零，當然當?overcomplete (n > m) 時這是不可能做到的，但是如果??很小的話，我們可以得到一些“近似正交”的結論。第一個有用的地方在于 Coherence 可以用于給出 spark 的一個下界。

我們在上次定義過，一個矩陣的 spark 是最小的數??使得該矩陣存在??列是線性相關的。我們上次介紹過，當矩陣??的 spark 足夠大的時候，能夠保證解的唯一性。但是 general 情況下計算一個矩陣的 spark 是 NP 難的，所以 Coherence 能給出一個下界就非常有用了。

因為對??的列進行縮放并不影響??的 Coherence 或者 spark，不失一般性，我們考慮??的列全部為 unit-norm 的情況。注意??的任意??列??是線性無關的，等價于矩陣??的任意??的子矩陣其行列式都是 full-rank 的。另一方面，注意到??的對角線元素都是?，而非對角元??都可以由??來 bound 住，由?Gershgorin Circle Theorem?知道，當??的時候，矩陣??的任意??子矩陣的特征值全都大于零，此時可以保證是 full-rank，亦即 spark?。由此可得下界：spark?。類似的方法還可以將 Coherence 和 RIP 聯系起來。

如果 sparsity?，此時我們有?，上次我們已經證明這種情況下?-稀疏解是唯一確定的。這里我們給出具體的 OMP 算法來將該解求出來。給出算法之前，我們再重復一下問題：已知??和?，求

并已知?。OMP 算法的步驟如下：

初始化：

For?

令??為?

，其中?

如果??則退出循環

求解??得出??的非零系數。

首先注意到每一次迭代都會有一個新的下標??進入集合?，因為如果??在之前的某一步中被加入到??中了的話，那么 residual??和??的內積會保持為零，所以不會選到該下標，亦即??不會進入集合兩次。所以經過??次迭代之后將會得到??個下標。接下來我們要說明這??個下標剛好對應了??的??個非零下標。令?，則我們要證明的是?。

首先我們證明第一步選中的??是屬于??的。令??是??的絕對值最大的元素下標，則

另一方面，對任意的?，我們有

當??時，顯然前者大于后者。因此??時一定不會選到??以外的下標（雖然并不一定就是選中絕對值最大的那個?）。也就是說，選中的下標會是??中的一員。

注意到第一步之后更新 residual 之后滿足?，其中?，也就是除去了第一步所得到的下標。實際上我們可以看成是重新開始一個新的問題，其中??是把??的第一步選出來的下標置零，而??則為 residual?。這樣我們可以重復剛才的證明，得到這一步選出來的下標還是屬于?。以此類推。

最后，由于我們一開始證明的 Coherence 作為 spark 下界的結果，很容易知道??的列是線性無關的，因此 OMP 最后一步的線性方程組求解也能得到 justify 了。

最后，OMP 算法雖然只需要進行??次迭代即可求解，但是每次迭代需要重新計算投影（第 2.3 步），普通的 Matching Puisuit (MP) 并不需要在每次選取新的下標之后對所有已有的下標重新做一次正交投影，所以計算量小了很多，但是由于在這里沒有了正交性，對算法的正確性等分析也相對變得更復雜了。此外，需要注意的是，這里只討論了最簡單的沒有 noise、嚴格?-sparse 的情況。

from:?http://freemind.pluskid.org/machine-learning/a-compressed-sense-of-compressive-sensing-iii/

總結

以上是生活随笔為你收集整理的压缩感知(III) A Compressed Sense of Compressive Sensing (III)的全部內容，希望文章能夠幫你解決所遇到的問題。

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