壓縮感覺——SP（subspace pursuit）重構算法前言翻譯

壓縮感覺是一種采樣方法，它和變換編碼類似，後者被廣泛用于涉及到大規模資料采樣的現代通信系統中。變換編碼将高維空間中的輸入信号，轉換成非常低的低維空間中的信号。變換編碼器的例子有著名的小波變換和普遍存在的傅立葉變換。

壓縮感覺技術将變換編碼成功的用于可壓縮信号或者是稀疏信号。将一個K稀疏N維離散時間信号x進行編碼，是通過計算一個m維的測量向量y來完成的，y是x的線性投影。這可以通過下式進行簡潔表示：y=Phi*x。在這裡，Phi代表一個m*N的矩陣，通常是在實數領域中。在這個架構中，投影基被假設成是不相關的，在這個基下，信号可以有一個稀疏表示。

盡管重構信号是一個欠定問題，信号稀疏性的先驗使求解問題成為可能。CS理論中一個非常著名的結果是可以使用優化的政策進行信号重構，方法是尋找最稀疏的信号使得y=Phi*x成立。換句話說，重構問題可以歸結為L0最優化問題。在無噪的情況下，L0最優化僅僅需要m=2K個随機投影就能重構出稀疏信号。不幸的是，L0最優化問題是一個NP-hard問題。這個問題引發了大量的CS 理論研究和實踐，實踐主要是圍繞設計低計算複雜度的測量和重構算法。

Donoho和Candes等人的工作表明，CS重構确實是一個多項式時間問題，雖然是在多于2K次測量的限制條件下。這些發現表明不一定必須使用求解L0最優化問題進行重構；而且通過求解一個更簡單的L1最優化問題，這可以通過線性規劃問題。L1和L0在一定條件下是等價的，隻要測量矩陣滿足一定的RIP條件。

盡管LP技術在設計重構算法中非常重要，但是它們的計算複雜度仍然很高，很難應用到很多應用中。在這些例子中，對于快速解碼算法的需求——最好是線性時間——是很重要的，盡管不得不提高測量的個數。幾種低複雜度的重構技術最近被提了出來，包括群測方法和基于置信傳播的算法。

最近，一類疊代貪婪算法引起了人們的注意，因為這些算法的計算複雜度低，并且有較好的幾何解釋。包括OMP 、ROMP和StOMP等。這些方法的基本出發點是疊代尋找未知信号的支撐集。在每次疊代中，向量x的一個或者多個坐标被選出來進行測試，測試的方法是計算正則化的測量向量和Phi的列之間的相關系數。如果被認為是足夠好，待選列逐漸被選入到x的目前支撐集中。追蹤算法疊代進行這樣的步驟，直到正确支撐集中所有的坐标被選入到估計的支撐集中。OMP政策的計算複雜度依賴于正确重構所需要的疊代次數：标準的OMP通常運作K次疊代，是以它的重構複雜度大約為O(KmN)（更多資訊檢視Section-IV C）。這樣的計算複雜度比LP算法要低很多，尤其是當信号的稀疏度K非常小的時候。但是，追蹤算法沒有和LP算法一樣級别的重構性能保證。為了保證OMP算法能恢複成功，要求Phi的任意兩列之間的相關系數不超過1/2K，它由Gershgorin Circle定理證明，它比RIP的要求還要嚴格。ROMP算法可以重構出所有的K稀疏信号，要求Phi滿足特定參數的RIP條件(delta_{2K}<=0.06/sqrt(log(K)))，它比普通的L1線性規劃問題要求有更強的RIP條件，分母上多了一個sqrt(log(K))。

本文的主要貢獻是提出了一種新的算法，稱作子空間追蹤算法（SP）。它有和LP算法類似的可以證明的重構性能，并且計算複雜度非常低。這個算法既可以無噪和有噪的情況。在無噪情況下，假如矩陣Phi滿足帶有一定參數的RIP條件，那麼SP算法可以準确重構出原始信号。當測量不準卻，或者信号不是嚴格稀疏的，重構失真有一個上界，這個上界與測量的常數倍數和攝動能量有關。對于非常稀疏的信号，K<=const*sqrt(N)，計算複雜度的上界是O(mNK)，當信号的稀疏度更小的時候，甚至能達到O(mNlog(K))。

原文：http://dsp.rice.edu/sites/dsp.rice.edu/files/cs/SubspacePursuit.pdf

轉載請注明出處：http://blog.csdn.net/zhyoulun/article/details/41978129